Breadth First Search

Breadth first search is used in graph algorithms for traversing through graph. It can be used to sort the graph, find cycles, solve mazes and sudokus. In this algorithm we traverse the neighbours of the nodes first and mark them down. We go on like this until we reach the end. To understand this, lets take an example. Suppose we have 5 nodes A,B,C,D,E. Say A has two neighbours B and C and D and E are the neighbours of B. And that C is the last node in its path. Lets put BFS into this situation, lets take A as the starting node. Now A is a visited node, so lets mark it has visited. Now we have to take A and look into its neighbours. We have a set now being [B,C]. Now we remove B and mark it as visited and check its neighbours. So the set now becomes [C, D, E]. Then we take C. Since C is the last node it is simply removed from the set. Same case for both D and E, hence they are simply removed. So the way we get the result is the way we removed from the set, which is; A, B, C, D, E. So this is how BFS work. Keep in mind that every time we encounter we mark it as repeated so that the nodes are not repeated , this also helps in determining if the graph has a cycle in it.

Now lets try to write a pesudocode for BFS.

Needed elements;

visited array: to keep track of the visited nodes, type boolean

a queue(Q); to keep adding the neighbouring nodes and poping the first to traverse

adjacency list or a matrix; to represent the graphs

no. Of nodes

Suppose we start from index 0.

visited[start] = true;

Q.add(start);

while(!q.empty) {

char temp = Q.poll();

for(int neighbour: adjlist[temp]){

if(!visited[neighbour]){

visited[neighbour] = true;

Q.add(neighbour);

}

}

}

Q.poll() removes the first element of the queue.

Adjlist is an array of LinkedList of integer type.

Each index of the array has its associated list of neighbours.

So the traversing of the neighbours of a specified node will be as given in the for loop.

Let us discuss the TC and SC.

So the TC would be the no of nodes to traverse + the no of edges. Because thats how many no of nodes are actually there in the adjacency list. After all we travell whole of the adjacency list which is nothing but yhe no of edges + no of nodes.

The SC would be no of nodes.

Means both TC and SC are linear.

Hope this made it a bit easy for you!

Thanks!