Depth-First Search (DFS) — Algorithm & Applications

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

def dfs_with_operation_count(graph, start):
    """
    DFS with detailed operation counting to verify O(V + E).
    """
    visited = set()
    
    # Counters for different operation types
    vertex_visits = 0        # Should equal V (reachable vertices)
    edge_examinations = 0    # Should equal E (or 2E for undirected)
    constant_ops = 0         # Miscellaneous O(1) work
    
    def dfs(v):
        nonlocal vertex_visits, edge_examinations, constant_ops
        
        # === VERTEX OPERATIONS ===
        vertex_visits += 1
        visited.add(v)           # O(1) hash set insertion
        constant_ops += 1
        
        # === EDGE OPERATIONS ===
        for neighbor in graph.get(v, []):
            edge_examinations += 1  # Each edge examined once
            constant_ops += 1       # visited check is O(1)
            
            if neighbor not in visited:
                dfs(neighbor)
    
    dfs(start)
    
    return {
        'vertex_operations': vertex_visits,
        'edge_operations': edge_examinations,
        'constant_operations': constant_ops,
        'total': vertex_visits + edge_examinations,
        'vertices_visited': len(visited)
    }
 
 
def verify_complexity(graph, all_vertices, start):
    """
    Verify O(V + E) complexity empirically.
    """
    # Count graph size
    V = len(all_vertices)
    E = sum(len(neighbors) for neighbors in graph.values())  # Directed edges
    
    # Run DFS with counting
    counts = dfs_with_operation_count(graph, start)
    
    print(f"Graph size: V = {V}, E = {E}")
    print(f"Expected total operations: O(V + E) ≈ {V + E}")
    print()
    print(f"Actual counts:")
    print(f"  Vertex operations: {counts['vertex_operations']}")
    print(f"  Edge operations:   {counts['edge_operations']}")
    print(f"  Total:             {counts['total']}")
    print()
    
    # Verify the relationship
    assert counts['vertex_operations'] == counts['vertices_visited']
    assert counts['edge_operations'] <= E  # May be less if graph disconnected
    print(f"✓ Verified: Operations scale as O(V + E)")
 
 
# Example: Create various graph sizes
def make_graph(n, edge_density=0.3):
    """Create a random directed graph with n vertices."""
    import random
    graph = {i: [] for i in range(n)}
    edges = 0
    for i in range(n):
        for j in range(n):
            if i != j and random.random() < edge_density:
                graph[i].append(j)
                edges += 1
    return graph, edges
 
 
# Test with different sizes
print("=" * 60)
print("VERIFYING O(V + E) COMPLEXITY")
print("=" * 60)
 
# Small example for clarity
small_graph = {
    0: [1, 2],
    1: [3],
    2: [3, 4],
    3: [4],
    4: []
}
verify_complexity(small_graph, list(range(5)), 0)
 
# Output shows operations = V + E

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

def analyze_dfs_space(graph, start):
    """
    Analyze actual space usage during DFS.
    """
    max_stack_depth = 0
    current_stack_depth = 0
    visited = set()
    
    def dfs(v):
        nonlocal max_stack_depth, current_stack_depth
        
        current_stack_depth += 1
        max_stack_depth = max(max_stack_depth, current_stack_depth)
        
        visited.add(v)
        
        for neighbor in graph.get(v, []):
            if neighbor not in visited:
                dfs(neighbor)
        
        current_stack_depth -= 1
    
    dfs(start)
    
    return {
        'max_stack_depth': max_stack_depth,
        'visited_set_size': len(visited),
        'total_auxiliary_space': max_stack_depth + len(visited)
    }
 
 
# Compare different graph shapes
def linear_chain(n):
    """Worst case for stack depth: 0 -> 1 -> 2 -> ... -> n-1"""
    return {i: [i + 1] for i in range(n - 1)} | {n - 1: []}
 
 
def complete_graph(n):
    """Best case for stack depth: everyone connected"""
    return {i: [j for j in range(n) if j != i] for i in range(n)}
 
 
def balanced_tree(depth):
    """Moderate case: binary tree"""
    graph = {}
    def build(node, d):
        if d >= depth:
            graph[node] = []
            return
        left = 2 * node + 1
        right = 2 * node + 2
        graph[node] = [left, right]
        build(left, d + 1)
        build(right, d + 1)
    build(0, 0)
    return graph
 
 
n = 100
print("Space Analysis for n =", n)
print("-" * 50)
 
# Linear chain
space = analyze_dfs_space(linear_chain(n), 0)
print(f"Linear chain: stack depth = {space['max_stack_depth']} (worst: O(n))")
 
# Complete graph
space = analyze_dfs_space(complete_graph(n), 0)
print(f"Complete graph: stack depth = {space['max_stack_depth']} (best: O(1)-ish)")
 
# Balanced tree
depth = 6  # About 127 nodes
tree = balanced_tree(depth)
space = analyze_dfs_space(tree, 0)
print(f"Balanced tree (depth={depth}): stack depth = {space['max_stack_depth']} (O(log n))")
 
# Output:
# Linear chain: stack depth = 100 (worst: O(n))
# Complete graph: stack depth = 100 (best: O(1)-ish) <- Still 100 because we visit all
# Balanced tree (depth=6): stack depth = 7 (O(log n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

import time
 
def benchmark_representations(n, edge_probability=0.1):
    """
    Compare DFS performance on different graph representations.
    """
    import random
    
    # Generate random edges
    edges = []
    adj_list = {i: [] for i in range(n)}
    adj_matrix = [[0] * n for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            if i != j and random.random() < edge_probability:
                edges.append((i, j))
                adj_list[i].append(j)
                adj_matrix[i][j] = 1
    
    E = len(edges)
    print(f"Graph: V = {n}, E = {E}")
    print(f"Density: {E / (n * (n-1)):.2%}")
    print("-" * 50)
    
    # DFS on adjacency list
    def dfs_adj_list(start):
        visited = set()
        def dfs(v):
            visited.add(v)
            for neighbor in adj_list[v]:
                if neighbor not in visited:
                    dfs(neighbor)
        dfs(start)
        return len(visited)
    
    # DFS on adjacency matrix
    def dfs_adj_matrix(start):
        visited = [False] * n
        def dfs(v):
            visited[v] = True
            for neighbor in range(n):  # Must check ALL vertices
                if adj_matrix[v][neighbor] and not visited[neighbor]:
                    dfs(neighbor)
        dfs(start)
        return sum(visited)
    
    # DFS on edge list (naive - scanning all edges each time)
    def dfs_edge_list_naive(start):
        visited = set()
        def dfs(v):
            visited.add(v)
            for u, w in edges:
                if u == v and w not in visited:
                    dfs(w)
        dfs(start)
        return len(visited)
    
    # Set high recursion limit
    import sys
    sys.setrecursionlimit(max(1000, n + 100))
    
    # Benchmark each
    results = {}
    
    start_time = time.perf_counter()
    reachable = dfs_adj_list(0)
    results['adj_list'] = time.perf_counter() - start_time
    
    start_time = time.perf_counter()
    dfs_adj_matrix(0)
    results['adj_matrix'] = time.perf_counter() - start_time
    
    if n <= 500:  # Edge list is too slow for larger graphs
        start_time = time.perf_counter()
        dfs_edge_list_naive(0)
        results['edge_list'] = time.perf_counter() - start_time
    
    print(f"Adjacency List:   {results['adj_list']:.6f}s  (O(V + E) = {n + E})")
    print(f"Adjacency Matrix: {results['adj_matrix']:.6f}s  (O(V²) = {n * n})")
    if 'edge_list' in results:
        print(f"Edge List:        {results['edge_list']:.6f}s  (O(V × E) = {n * E})")
    
    # Show ratio
    if results['adj_list'] > 0:
        print(f"\nMatrix is {results['adj_matrix'] / results['adj_list']:.1f}x slower than list")
 
 
# Run benchmarks
for n in [100, 500, 1000]:
    benchmark_representations(n, edge_probability=0.1)
    print()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

def dfs_search_target(graph, start, target):
    """
    Search for a target vertex. Can terminate early.
    Returns (found, vertices_visited) for analysis.
    """
    visited = set()
    vertices_visited = 0
    
    def dfs(v):
        nonlocal vertices_visited
        vertices_visited += 1
        
        if v == target:
            return True
        
        visited.add(v)
        
        for neighbor in graph.get(v, []):
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
        
        return False
    
    found = dfs(start)
    return found, vertices_visited
 
 
def dfs_has_cycle(graph, all_vertices):
    """
    Check for cycle. Can terminate early.
    Returns (has_cycle, operations_performed) for analysis.
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in all_vertices}
    operations = 0
    
    def dfs(v):
        nonlocal operations
        operations += 1
        color[v] = GRAY
        
        for neighbor in graph.get(v, []):
            operations += 1
            if color[neighbor] == GRAY:
                return True  # Found cycle!
            if color[neighbor] == WHITE:
                if dfs(neighbor):
                    return True
        
        color[v] = BLACK
        return False
    
    for v in all_vertices:
        if color[v] == WHITE:
            if dfs(v):
                return True, operations
    
    return False, operations
 
 
# Example: Best vs worst case for cycle detection
print("Cycle Detection Performance")
print("-" * 50)
 
# Best case: Cycle at the start
early_cycle = {
    0: [1],
    1: [2],
    2: [0],  # Cycle! Will be found quickly
    3: [4],
    4: [5],
    5: []
}
 
has_cycle, ops = dfs_has_cycle(early_cycle, list(range(6)))
print(f"Early cycle: found={has_cycle}, operations={ops}")
 
# Worst case: No cycle (acyclic)
no_cycle = {
    0: [1, 2],
    1: [3, 4],
    2: [5],
    3: [],
    4: [],
    5: []
}
 
has_cycle, ops = dfs_has_cycle(no_cycle, list(range(6)))
print(f"No cycle: found={has_cycle}, operations={ops}")
 
# With cycle at the very end
late_cycle = {
    0: [1],
    1: [2],
    2: [3],
    3: [4],
    4: [5],
    5: [0]  # Cycle only detected after traversing everything
}
 
has_cycle, ops = dfs_has_cycle(late_cycle, list(range(6)))
print(f"Late cycle: found={has_cycle}, operations={ops}")
 
# Output shows operations vary based on when cycle is found

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

def connected_components_complexity(graph, all_vertices):
    """
    Finding connected components is O(V + E).
    
    We do one complete DFS, visiting each vertex once
    and examining each edge once (twice for undirected).
    """
    visited = set()
    components = []
    vertex_ops = 0
    edge_ops = 0
    
    def dfs(v, component):
        nonlocal vertex_ops, edge_ops
        vertex_ops += 1  # O(1) per vertex
        
        visited.add(v)
        component.append(v)
        
        for neighbor in graph.get(v, []):
            edge_ops += 1  # O(1) per edge examination
            if neighbor not in visited:
                dfs(neighbor, component)
    
    for v in all_vertices:
        if v not in visited:
            component = []
            dfs(v, component)
            components.append(component)
    
    V = len(all_vertices)
    E = sum(len(adj) for adj in graph.values())
    
    print(f"Graph: V={V}, E={E}")
    print(f"Vertex operations: {vertex_ops} (expected: {V})")
    print(f"Edge operations: {edge_ops} (expected: {E})")
    print(f"Components found: {len(components)}")
    
    return components
 
 
def kosaraju_complexity(graph, all_vertices):
    """
    Kosaraju's SCC algorithm is O(V + E) despite doing two DFS passes.
    
    Pass 1: DFS on original graph for post-order: O(V + E)
    Transpose graph: O(V + E)
    Pass 2: DFS on transpose in reverse post-order: O(V + E)
    Total: 3 × O(V + E) = O(V + E)
    """
    v_ops = [0, 0]
    e_ops = [0, 0]
    
    # Pass 1: Get finish order
    visited = set()
    finish_stack = []
    
    def dfs1(v):
        v_ops[0] += 1
        visited.add(v)
        for neighbor in graph.get(v, []):
            e_ops[0] += 1
            if neighbor not in visited:
                dfs1(neighbor)
        finish_stack.append(v)
    
    for v in all_vertices:
        if v not in visited:
            dfs1(v)
    
    # Transpose graph: O(V + E)
    transpose = {v: [] for v in all_vertices}
    for v in graph:
        for neighbor in graph[v]:
            transpose[neighbor].append(v)
    
    # Pass 2: DFS in reverse finish order
    visited = set()
    sccs = []
    
    def dfs2(v, component):
        v_ops[1] += 1
        visited.add(v)
        component.append(v)
        for neighbor in transpose.get(v, []):
            e_ops[1] += 1
            if neighbor not in visited:
                dfs2(neighbor, component)
    
    while finish_stack:
        v = finish_stack.pop()
        if v not in visited:
            component = []
            dfs2(v, component)
            sccs.append(component)
    
    V = len(all_vertices)
    E = sum(len(adj) for adj in graph.values())
    
    print(f"Kosaraju's Algorithm Complexity")
    print(f"Graph: V={V}, E={E}")
    print(f"Pass 1 - Vertex ops: {v_ops[0]}, Edge ops: {e_ops[0]}")
    print(f"Pass 2 - Vertex ops: {v_ops[1]}, Edge ops: {e_ops[1]}")
    print(f"Total operations: {sum(v_ops) + sum(e_ops)} ≈ 2(V + E) = {2 * (V + E)}")
    print(f"SCCs found: {len(sccs)}")
    
    return sccs
 
 
# Example
graph = {
    'A': ['B'],
    'B': ['C', 'E'],
    'C': ['A', 'D'],
    'D': [],
    'E': ['F'],
    'F': ['E']
}
 
kosaraju_complexity(graph, list(graph.keys()))