Breadth First Search
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
D - and the second contains remaining
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:
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.
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
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:
queueand mark it as
queueand call it
currentnode which are not yet marked as
queueand mark them all as
Usually we perform some additional actions along with these core steps. For example:
queuewe may print its name out - this will give us a list of the vertices of the graph (or its connected component) in the order of visiting by BFS;
seenwe can store here not only the fact that the node was seen, but also the id of the vertex from which it was seen - as the result the hashtable will describe the tree of the shortest paths at the end;
You also can read wikipedia article to get more clear idea.
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
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 lines will follow each containing ids of two nodes connected by an edge. Node ids are integers between
Answer should contain the
seen array as described above. It should have
-1 for the initial node.
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