Depth First Search (DFS) Notes

Depth First Search (DFS) Overview

  • DFS is an algorithm used for searching a graph.
  • Operates primarily by exploring one vertex to the maximum depth before backtracking (vertical then horizontal search).

Key Concepts

  • Data Structure Used: Stack
    • The stack keeps track of which vertices to visit next during the search.
  • Color Coding: To visualize the search process:
    • Black: Nodes that have been visited.
    • Gray: Nodes that are currently in the stack and in line to be visited.

Example Walkthrough

  • Start from root node A and follow these steps:
    1. Push A onto the stack and mark it as visited (color black).
    2. Add adjacent nodes of A into the stack, ensuring to add the rightmost node first for ease of traversal.
    3. Pop B from the stack, mark it as visited.
    4. G is the only node in the stack after B is processed.
    5. Pop C from the stack, which has no adjacent nodes, so continue.
    6. Next, pop D, with no children, continue.
    7. Reach node E and push its child F into the stack.
    8. Continue the process until the stack is empty, indicating all reachable nodes from A have been visited.

Code Implementation

  • The Python implementation of DFS is akin to the Breadth First Search (BFS) but utilizes a stack instead of a queue.
  • Graph representation is done using an adjacency list.
Key Steps in the Code:
  1. Add the root node to both visited list and stack.
  2. Loop as long as the stack is not empty:
    • Pop the top element from the stack.
    • Iterate through adjacent nodes:
      • Use reversed() to prioritize visiting the rightmost nodes last.
      • If an adjacent node hasn’t been visited, add it to visited and stack.
  3. Both iterative and recursive solutions exist; however, the iterative approach is used in this case for simplicity.

Time Complexity

  • The time complexity for DFS shares similarities with BFS:
    • In the worst case, every vertex and edge will be explored.
    • Therefore, the formula for time complexity is:
      O(V+E)O(V + E)
      Where:
    • VV = number of vertices
    • EE = number of edges

Conclusion

  • DFS is a fundamental algorithm useful in various applications and scenarios involving graph traversal.
  • It is essential for understanding more complex algorithms and problems concerning graphs.