DFS Traversal in Graphs

Overview

• Depth First Search (DFS) is the second graph traversal technique, following Breadth First Search (BFS).
• DFS explores as far as possible along each branch before backing up.

Key Concepts

• Starting Node: Example starting node is 1.
• Traversal Order: Can choose any neighboring node to explore.

Traversal Steps

Example Traversal

1. Start at 1.
2. Move to a neighbor (e.g., 2).
3. Continue to depth:
   • Go from 2 to 5 (no further nodes).
4. Backtrack to 2, then to 6.
5. Backtrack to 1 and proceed to next neighbor, 3.
6. From 3, navigate to 7 and further to 8, then to 4.
7. Backtrack once all possible nodes are visited.

Alternative Traversal Path

• Various paths are valid as long as depth traversal is maintained (e.g., can start with 3):
  • 3 -> 4 -> 8 -> 7 -> backtrack to 3, then to 1, and explore 2.

Recursive Nature of DFS

• DFS can be implemented using recursion.
• Importance of visited nodes: Once visited in traversal, nodes should not be revisited.
• Store the graph using an adjacency list.

Implementation Details

Initial Setup

1. Create a visited array (e.g., for 1-based indexing, size = number of nodes + 1).
2. Mark the starting node as visited.

Recursive DFS Function

• Define the recursive function DFS(node):
  1. Mark the node as visited.
  2. Traverse each neighbor (check if it is unvisited before exploring).

Example Paths in Code

• Use adjacency list to run loops for neighbors of each node.
• Ensure that the recursive calls account for previously visited nodes.
• The depth traversal order may vary depending on the adjacency list's order.

Space Complexity

• Space Complexity: O(n)
  • Storing visited status for nodes and recursive call stack (worst case O(n) for skewed graphs).

Time Complexity

• Time Complexity: O(n + e)
  • For undirected graphs, where n is the number of nodes and e is the number of edges.
• For directed graphs, complexity will depend on the number of edges.

Conclusion

• DFS traversal is an effective graph exploration method, utilizing recursion and maintaining depth-first strategy.
• Ensure familiarity with recursion to comprehend graph traversal intricacies.