In my previous articles , we have discussed the representations of graph data structure through adjacency matrix and adjacency list.
Traversal techniques are crucial in graph data structures as they enable in exploration of nodes and edges, facilitating tasks like finding paths, detecting cycles, and analyzing connectivity.
In this article we would be discussing breadth first search traversal technique , an important algorithm used in various graph problems.
Cycles in graph:
- A graph may contain cycles , ie starting from one node, you follow a path and again reach the same node.
- For example :
- Starting from node = 0 , and following the path [0 -> 3 -> 2 -> 1 ->0], we end up again at node = 0, which means the given graph has cycle (a graph can have multiple cycles).
- A graph which does not contain cycles is known as acyclic graph. Below is an acyclic graph :
- Starting from any vertex/node in the graph, and following any path, we do not end up at the same vertex.
- The above graph is known as directed acyclic graph (DAG).
BFS :
- BFS uses queue data structure for traversing through the graph.
- It also uses a boolean visited array, which is used to for marking visited nodes/vertices.
- We start traversal from a node.
- The nodes at this particular level are all visited first.
- Then, the nodes of the next level are traversed till all nodes have been visited.
- To avoid visiting the same node again and again, the boolean visited array is used to mark visited nodes.
- Consider the below graph :
- For simplicity of understanding BFS algorithm, we are taking an undirected graph where every vertex/node can be reached from every other vertex/node.
- We initialize the queue data structure, initially empty.
- We also initialize a boolean visited array of size 5, since there are 5 nodes , where each index denotes whether the particular node has been visited or not.
- Initially, since no node has been visited, all the indices of the visited array is false.
- We can apply BFS algorithm from any node of the graph. For this example, we will apply BFS from node = 0.
- We start our traversal from node = 0.
- So, we visit node = 0 and mark it as visited in the visited array ie 1.
- Since now we have visited it, we push node = 0 into the queue data structure now.
- Since we have visited all the nodes at this level, we pop out the node from the front of the queue ie node = 0.
- We traverse all the neigbour nodes of node = 0, ie {2,1}.
- If they are not visited yet, then we mark them as visited and push them into queue.
- Since node = 1 and node = 2 have not been visited yet, we mark them as visited, and push into queue.
- Since we have visited all the nodes at this level, we pop out the node at the front of the queue ie node = 2.
- We traverse the neighbour nodes of node = 2 ie { 0 , 1 , 4}. Since, node = 0 and node = 1 have already been visited, we do not push them into the queue.
- Node = 4, has not been visited yet, so we mark 4 as visited in the visited array and push into queue.
- Since we have already visited all the nodes at this level, we pop out the node at the front of the queue ie node = 1.
- The neighbour nodes of 1 is { 0 , 2 , 3}. Node = 0 and node = 2 have already been visited ; node = 3 would be visited and pushed into the queue.
- Now, node = 4 is popped out from the front. The neighbour nodes of node = 4 , which are { 2 , 3} have already been visited. So we do not need to push anything into the queue.
- Similarly, node = 3 would be popped out and its neighbour nodes {1 , 4} have already been visited, so no need to push anything into the queue.
- The queue becomes empty and hence the BFS traversal is complete.
Code:
Below is the C++ code for performing a breadth first search traversal in a graph :
- Time Complexity : O(V+E) , V → number of vertices/nodes , E → number of edges
- Space Complexity : O(V)
Thank you for reading!! I would love to hear your feedback in the comments.