BFS and DFS Of A Directed Graph

Lets assume we have a directed graph like the below image. Now we need to traverse the graph from a starting index. 

We can do it either by usinf BFS or by using DFS.

Directed Graph

Implementation of BFS traversal For Directed Graph:

Follow the below method to implement BFS traversal.

• Declare a queue and insert the starting vertex.
• Initialize a visited array and mark the starting vertex as visited.
• Follow the below process till the queue becomes empty:
• Remove the first vertex of the queue.
• Mark that vertex as visited.
• Insert all the unvisited neighbours of the vertex into the queue.

Output

Following is Breadth First Traversal (starting from vertex 2) 
2 0 3 1 

Time Complexity: O(V+E), where V is the number of nodes and E is the number of edges.
Auxiliary Space: O(V)

Implementation of DFS traversal For Directed Graph:

Follow the below steps to solve the problem:

• Create a recursive function that takes the index of the node and a visited array.
• Mark the current node as visited and print the node.
• Traverse all the adjacent and unmarked nodes and call the recursive function with the index of the adjacent node.

Output

Following is Depth First Traversal (starting from vertex 2) 
2 0 1 3 

Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Auxiliary Space: O(V), since an extra visited array of size V is required.