Implementation (Part 2)

Lesson 6 of 9 in Coddy's Breadth-First Search - Graph Algorithms course.

Now we traverse the graph in layers with a queue.

Challenge

Medium

Now build the full traversal.

Write a function named bfs that takes n, the flat edges array (undirected), and a start vertex, and returns the order in which BFS visits vertices from start.

Build the adjacency list (neighbors sorted ascending), then use a queue: mark and enqueue the start, and repeatedly dequeue a vertex, record it, and enqueue its unvisited neighbors. Only vertices reachable from start are visited.

Try it yourself

#include <stdlib.h>

int* bfs(int n, int* edges, int edges_size, int start, int* returnSize) {
    // Write code here
    *returnSize = 0;
    return edges;
}

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

All lessons in Breadth-First Search - Graph Algorithms

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo Code Implementation (Part 1)Implementation (Part 2) Project lesson

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2