BFS
Lesson 10 of 14 in Coddy's Graphs - Data Structures Series #9 course.
The next challenges are designed to use the Graph class you just built.
Each challenge ships you a locked graph file (the final Graph from the previous chapter) and a fresh solution file where you write a function that USES the Graph.
Our first algorithm: Breadth-First Search. Starting from a vertex, BFS visits all reachable vertices in waves: first the start, then everything one edge away, then everything two edges away, and so on. The classic implementation uses a queue: enqueue the start, then repeatedly dequeue, record the vertex as visited, and enqueue any unvisited neighbors.
Because neighbor lists do not have a fixed order, two correct BFS runs can produce different traversal orders. To make the answer deterministic in this challenge, sort each vertex's neighbors ascending before enqueueing them.
Challenge
EasyWrite a function bfs that gets a 2D int array adjacency (each row is a [u, v] edge) and an int start, and returns the BFS visit order from start as a list of ints.
Build the graph: for each [u, v] in adjacency, call g.addEdge(u, v). Then BFS from start using a queue. When processing a vertex's neighbors, sort them ascending so the output is deterministic.
You must use the Graph class (provided in graph) - do not use language built-ins (maps, sets) to model the adjacency. Auxiliary data for the algorithm (visited sets, queues) may use stdlib types.
Try it yourself
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = bfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}