Similar Problems
Similar Problems not available
Depth First Traversal for a Graph - Leetcode Solution
LeetCode: Depth First Traversal for a Graph Leetcode Solution
Difficulty: Unknown
Topics: graphs
Depth First Search (BFS) is a recursive graph traversal algorithm that is used to traverse all the vertices of a graph in a depthward motion. In other words, it starts the graph traversal from root node and explores all the branches.
Example of Depth First Traversal for a Graph
Depth First Traversal is used to traverse all the vertices of a graph. Using this algorithm, traversal is done in a depthward motion.
Below is the example of DFS Traversal with input- output constraint and the solution for the example.
Input and Output of the Example
Given the undirected, connected and unweighted graph G, and the task is used to traverse all the vertices of a graph using DFS Traversal starting from 0.
Output:
Depth First Traversal from vertex 0 is 0 1 3 2.
Stepwise Solution of the Depth First Traversal Example
- Given the undirected, connected and unweighted graph G. Create a set Visited which is used to track on visited vertices and create stack Nxt_Vertex to store next vertices.
- Start from vertex 0, put the current vertex (0) in Visited list and put all its adjacent vertices ( 1, 3, 2 ) in the stack, left side denotes the top of the stack.
| Visited: | 0 | | :---------------: | :----: |
| Nxt_Vertex: | 1 | 3 | 2 | | :-----------------------: |----|----|----|
- Now visit next unvisited vertex from the top of Nxt_Vertex , put the current vertex (1) in Visited list. There is no new vertex.
| Visited: | 0 | 1 | | :---------------: | :----: | :----: |
| Nxt_Vertex: | 3 | 2 | | :----------------------: | ----| ----|
- Similarly, visit next unvisited vertex from the top of Nxt_Vertex, put the current vertex (3) in Visited list. There is also no new vertex.
| Visited: | 0 | 1 | 3 | | :---------------: | :----: | :----: | :----: |
| Nxt_Vertex: | 2 | | :----------------------: | -----|
- Similarly, visit next unvisited vertex from the top of Nxt_Vertex, put the current vertex (2) in Visited list. There is also no new vertex.
| Visited: | 0 | 1 | 3 | 2 | | :---------------: | :----: | :----: | :----: | :----: |
|Nxt_Vertex : | | :-----------------: |
- Since Nxt_Vertex is empty, stop the traversal. Thus the traversal is : 0 1 3 2.
Pseudocode for Depth First Traversal for a Graph
Here’s pseudocode to traverse all the vertices of a graph using DFS Traversal.
Depth_First_Traversal(G, root):
root is visited
for all edges from v to w in G.adjacentEdges(v) do
if w is not visited then
call Depth_First_Traversal(G, w)
Depth First Traversal for a Graph Solution Code
1