Depth First Search DFS
Depth First Traversal or Depth First Search (DFS) algorithm traverses a Graph in a depth manner and uses a stack to store the visited nodes.
DFS traversal proceeds level by level, DFS follows a path from the starting node to an ending node, then another path from the start to the end, until all the nodes are visited.
A path is set until no unvisited nodes remain, and then the algorithm selects the last visited node that has unvisited adjacent nodes.
DFS Algorithm
- Select a node, follow the path to end.
- Select another node follow its path.
- Visit the adjacent unvisited nodes. Push it in a stack.
- If no adjacent node is found, pop up a vertex from the stack.
- Repeat the steps until the stack is empty.
DFS Example 1
The depth first traversal of the graph above is in the order 1, 2, 4, 8, 7, 3, 6.
A path is selected until no unvisited nodes remain reachable, then the traversal goes back to the last node that was visited that has unvisited adjacent nodes.
A valid result of depth first search of the graph above is 1, 3, 6, 7, 8, 2, 5, 4.
DFS Example 2
For this graph, we can start with vertex 1. Now to initiate depth first search, an adjacent vertex is selected.
Let 2, 3, 8, are adjacent vertices of vertex 1. We can select any vertex from these vertices let us select vertex 2, now all the adjacent vertices of vertex 2 are processed and visited, next vertex 3 is selected and all its adjacent vertices are visited.
The algorithm runs until all the vertices are visited. We must set a flag for all the visited nodes, in order to not traverse the vertex a second time.
Depth First Search Flowchart
See Also: Breadth First Search (BFS)