Breadth First Search

Problem #154

Tags: graphs data-structures

Who solved this?

breadth first search demo
Breadth-First Search builds a short and divergent spanning tree

Breadth-First Search with its complement Depth-First Search are two popular methods of searching in the graph. They are building blocks for many other more special algorithms. At the same time each of them may be implemented in several different ways.

The words Breadth-First in the name reflect the manner of search - from any vertex we are trying to investigate all neighbors as soon as possible. Because of this the search process looks as following:

And so on with the general rule that at level K+1 we visit all neighbors of all nodes of level K, of course except ones already visited on previous steps. At the picture above initial node is A, while the first level consists of B, C, and D - and the second contains remaining E, F and G.

The manner in which the algorithm visits vertices resembles the spreading of the wave when it floods the shore. Due to this fact particular implementation of the BFS on a rectangular grid is sometimes called Wave Algorithm - see the following picture to decide whether this name is correct:

wave algorithm demo
Wave algorithm is just another incarnation of the BFS

Typical application

If the graph is connected, BFS will visit all of its nodes. If for each node we will remember where we got to it from - then the resulting set of edges will represent a tree connecting all nodes (so-called spanning tree).

The tree built by BFS at the same time represents the shortests paths from initial vertex to any other (for the graph with the edges of equal weights - otherwise more special algorithm, like Dijkstra should be used).

The puzzle Word Ladders gives an example of a problem when BFS is most suitable.

Other popular usage is for discovering if the graph is connected or consists of several izolated parts. It also allows to mark which vertex belongs to which part. However this task could be by DFS also.

Algorithm implementation

Usually we prefer to use a Queue to keep the track of the nodes which we are going to visit soon. This data structure provides two operations, let us call them add and remove for putting new elements to it and fetching them later. The core property is that elements are removed in the same order in which they were stored - this is often called FIFO, i.e. first in, first out. For example if you add elements to the end of the list and remove them from the beginning - it will work as a queue.

We also need some way to mark vertices as seen - it could be array of flags or set to which we will add ids of vertices or something like this.

That's how algorithm works:

  1. We add the initial node to queue and mark it as seen.
  2. Remove the next element from the queue and call it current.
  3. Get all neighbors of the current node which are not yet marked as seen.
  4. Store all these neighbors into the queue and mark them all as seen.
  5. Repeat from the step 2 until the queue becomes empty.

Usually we perform some additional actions along with these core steps. For example:

You also can read wikipedia article to get more clear idea.


Problem statement

You are given an undirected and unweighted graph with vertices identifided by integers. The goal is to run BFS over it as described above, starting from the node 0.

As output you should produce the seen array which shows where each vertex was visited from.

To avoid ambiguosity please at the step 3 sort all fetched neighbors in order of increasing their id numbers.

Input data will contain the amount of nodes N and the amount of edges M.
Then M lines will follow each containing ids of two nodes connected by an edge. Node ids are integers between 0 and N-1.
Answer should contain the seen array as described above. It should have -1 for the initial node.

Example:

input data:
7 10
0 1
2 0
0 3
1 4
4 3
2 3
5 2
6 3
4 6
6 5

answer:
-1 0 0 0 1 2 3

This example is from the picture above, only vertices are labeled with 0...6 instead of A...F.

You need to login to get test data and submit solution.