Now that we’ve learnt about graphs and some graph traversal algorithms like breadth-first search and depth-first search, it’s time to implement them. You can work in any programming language of your choice - Python, C++, Java, or anything else you want. Let’s get started!

Problem Statement

You are given an undirected graph with $n$ nodes and $m$ edges. The nodes are numbered from $0$ to $n-1$. Find the shortest distance from the source (node $0$) to all other nodes. If there is no path from the source to a particular node, output INF instead (for infinity).

Constraints: $n \leq 10^5$ and $m \leq 10^6$.

IO description

Input description: The input file contains multiple test cases. Each test case begins with “Test case: X”. This is followed by a line which has two numbers, $n$ (the number of nodes) and $m$ (the number of edges). The next $m$ each contain 2 numbers $u$ and $v$, denoting that there is an an edge $(u, v)$.

Sample input:

Test case: 1
3 1
1 2
Test case: 2
3 1
0 1
Test case: 3
3 2
0 1
2 1

Output description: Output should contain one line per test case. The line should have $n$ numbers, where the $i$th number = $d(0, i)$ = distance between node $0$ and node $i$. If there is no path from the source to a particular vertex, output INF instead (for infinity).

Sample output:

0 INF INF
0 1 INF
0 1 2

In the first test case, there is no edge from node $0$. Hence, the distance to node $1$ and node $2$ is infinity. In the second test case, there is a direct edge from node $0$ to node $1$. In the third test case, there is an edge from node $0$ to node 1, and node $1$ to node $2$.

Note that the distance from the source to itself is always 0.

Notes

1. Start by creating an adjacency list from input. Make sure to add edges in both directions.
2. When performing breadth-first search, keep track of distance[i] = distance from node 0 to node i. When a new node is marked visited, also calculate its distance.

Grading your solution

You’ll find all the files required to check your solution here: Breadth-first Search. In particular, the folder includes 3 files - input, answer and grader.py.

Do the following to check your solution.

{COMMAND TO RUN C++/JAVA/PYTHON CODE} < input > output 
python grader.py output answer

Solution

The solution for this assignment can be found here: bfs.py. The code takes about 5 seconds to run for all test cases combined. Note that if you implemented the solution in C++ / Java, your code should be executing about > 5x faster.