Module 4: Graphs IV

Advanced graph traversal techniques with depth-first traversal

Module Objectives

Upon completion of this module you will be able to:

Understand advanced graph traversal techniques including Depth-First Traversal (DFT)
Implement DFT in both recursive and iterative forms
Apply DFT to solve graph-based problems
Compare DFT with other graph traversal algorithms
Analyze the time and space complexity of graph traversal methods

Depth-First Traversal (DFT)

Understanding Depth-First Traversal

Depth-First Traversal (DFT) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses the principle of recursion and backtracking or a stack data structure for its implementation.

Key Characteristics of DFT:

Explores deeply into the graph before backtracking
Uses a stack data structure (either explicitly or via recursion)
Visits all nodes connected from a starting node
Can detect cycles when implemented with proper tracking
Often simpler to implement than breadth-first traversal for recursive problems

Graph Representation

Before implementing DFT, we need a way to represent our graph. Common representations include:

        # Adjacency List representation
        class Graph:
        def __init__(self):
        self.adjacency_list = {}

        def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
        self.adjacency_list[vertex] = []

        def add_edge(self, vertex1, vertex2):
        self.adjacency_list[vertex1].append(vertex2)
        # For undirected graph, add the reverse edge too
        # self.adjacency_list[vertex2].append(vertex1)
      

Recursive DFT Implementation

The recursive approach to DFT leverages the call stack to keep track of vertices to visit:

        # Recursive DFT implementation
        class Graph:
        # ... previous methods from above ...

        def depth_first_traversal_recursive(self, start_vertex):
        result = []
        visited = set()
        adjacency_list = self.adjacency_list

        def dfs(vertex):
        if not vertex:
        return None
        visited.add(vertex)
        result.append(vertex)
        for neighbor in adjacency_list[vertex]:
        if neighbor not in visited:
        dfs(neighbor)
        dfs(start_vertex)
        return result

        # Example usage
        g = Graph()
        g.add_vertex("A")
        g.add_vertex("B")
        g.add_vertex("C")
        g.add_vertex("D")
        g.add_vertex("E")
        g.add_vertex("F")
        g.add_edge("A", "B")
        g.add_edge("A", "C")
        g.add_edge("B", "D")
        g.add_edge("C", "E")
        g.add_edge("D", "E")
        g.add_edge("D", "F")
        g.add_edge("E", "F")
        print(g.depth_first_traversal_recursive("A")) # ["A", "B", "D", "E", "F", "C"]
      

Iterative DFT Implementation

The iterative approach uses an explicit stack to keep track of vertices to visit:

        # Iterative DFT implementation
        class Graph:
        # ... previous methods ...

        def depth_first_traversal_iterative(self, start_vertex):
        stack = [start_vertex]
        result = []
        visited = set()
        visited.add(start_vertex)
        while stack:
        current_vertex = stack.pop()
        result.append(current_vertex)
        for neighbor in self.adjacency_list[current_vertex]:
        if neighbor not in visited:
        visited.add(neighbor)
        stack.append(neighbor)
        return result

        # Example usage
        print(g.depth_first_traversal_iterative("A")) # May produce different order than recursive version
      

Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges

Space Complexity: O(V) for the visited set and stack/recursion call stack

Applications of DFT

Cycle Detection: Detect if a graph contains a cycle
Path Finding: Find a path between two nodes
Topological Sorting: Linear ordering of vertices in a directed acyclic graph
Connected Components: Find connected components in an undirected graph
Solving Puzzles: Maze solving, Sudoku solving, etc.

DFT vs. BFT Comparison

Aspect	Depth-First Traversal	Breadth-First Traversal
Data Structure	Stack (explicit or call stack)	Queue
Traversal Pattern	Deep exploration before backtracking	Level by level exploration
Best For	Path finding, maze solving, topological sort	Shortest path, social networks, level-order tasks
Memory Usage	Lower for deep graphs	Lower for wide graphs
Implementation	Simpler recursive solution	Usually implemented iteratively

Practice with LeetCode Problems

Note: Previously, this course referenced the CodeSignal Arcade for practice, which is no longer available. The LeetCode problems below follow the same principles and are an excellent alternative for practicing graph traversal.

Number of Islands - Classic DFT/DFS problem
Clone Graph - Deep copy a graph using DFT
Course Schedule - Cycle detection with DFT
Pacific Atlantic Water Flow - DFT with multiple starting points
Flood Fill - Simple application of DFT