Given an adjacency list representation of a directed graph, the task is to find the path from source to every other node in the graph using BFS.
Input: Output: 0 <- 2 1 <- 0 <- 2 2 3 <- 1 <- 0 <- 2 4 <- 5 <- 2 5 <- 2 6 <- 2
Approach: In the images shown below:
- que array stores the vertices reached and we will enqueue a vertex only if it has not been visited and dequeue it once all its child node have been considered.
- In order to distinguish whether the node has been visited or not we will put 1 in visited array at the respective index to signify it has been visited and if at given index 0 is present it will signify that it has not been visited.
- Parent array is to store the parent node of each vertex. For ex. In case of 0 connected to 2, 2 will be the parent node of 0 and we will put 2 at the index 0 in the parent array.
Below is the implementation of the above approach:
0 <- 2 1 <- 0 <- 2 2 3 <- 1 <- 0 <- 2 4 <- 5 <- 2 5 <- 2 6 <- 2
Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.