# Hands-on: Implementing Breadth-first search

July 04, 2018

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

- Start by creating an adjacency list from input. Make sure to add edges in both directions.
- 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.