Depth First Search

Depth First Search is a graph traversal algorithm.

The search starts on any node and explores further nodes going deeper and deeper until the specified node is found, or until a node with no children is found. If a node is found with no children, the algorithm backtracks and returns to the most recent node that has not been explored. This process continues until all the nodes have been traversed.

A stack is used as an auxiliary data structure to keep track of traversed nodes to help it backtrack when required.

Properties

Time Complexity

The worst case occurs when the algorithm has to traverse through all the nodes in the graph. Therefore the sum of the vertices(V) and the edges(E) is the worst-case scenario. This can be expressed as O( |E| + |V| ).

Space Complexity

The space complexity of a depth-first search is lower than that of a breadth first search.

Completeness

This is a complete algorithm because if there exists a solution, it will be found regardless of the type of graph provided.

Algorithm

1. Define a Stack of size total number of vertices in the graph.
2. Select any vertex as the starting point for traversal. Visit that vertex and push it on to the Stack.
3. Visit any one of the adjacent vertices of the vertex which is at top of the stack which is not visited and push it on to the stack.
4. Repeat step 3 until there is no new vertex to visit from the vertex on top of the stack.
5. When there is no new vertex to visit then use backtracking and pop one vertex from the stack.
6. Repeat steps 3, 4 and 5 until stack becomes Empty.
7. When stack becomes Empty, then produce final spanning tree by removing unused edges from the graph

Applications

1. Topological Sorting: Topological sorting is used in scheduling jobs where the jobs dependent on each other and can be represented in a graph. This can be implemented using Depth First Search.
2. Finding Minimum Spanning Tee: Depth First Search can be used to find the minimum spanning tree and all pair shortest path tree of an unweighted graph.
3. Solving Mazes: Depth First Search can be used in puzzles like that of mazes to find the solution.

Visualisations

• Depth First Search: Excellent visualization from cs.usfca.edu

Videos

• Depth First Search: Excellent explanation from MIT OCW

Additional Resources

• Full Code For Depth First Search: See the full working code at tutorialspoint