Graph Algorithms

How DFS Works

Idea: Explore as far as possible along each branch before backtracking.

Analogy: Maze exploration - keep going straight until you hit a dead end, then backtrack.

DFS Traversal Order

Visit order: A → B → D → E → C → F (go deep first!)

DFS Implementation (Recursive)

def dfs_recursive(graph, start, visited=None):
    """
    Depth-First Search using recursion

    How it works:
    1. Mark current node as visited
    2. Process current node (print, add to result, etc.)
    3. For each unvisited neighbor, recursively call DFS
    4. Recursion call stack handles backtracking automatically

    Time: O(V + E) - visit each vertex once, explore each edge once
    Space: O(V) - visited set + recursion stack depth
    """
    if visited is None:
        visited = set()

    visited.add(start)
    print(start, end=' ')  # Process node

    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

    return visited


# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}

dfs_recursive(graph, 'A')  # Output: A B D E C F

DFS Implementation (Iterative with Stack)

def dfs_iterative(graph, start):
    """
    Depth-First Search using explicit stack

    How it works:
    1. Push start node onto stack
    2. While stack not empty:
       - Pop node from stack
       - If not visited, mark visited and process
       - Push all unvisited neighbors onto stack
    3. Stack (LIFO) ensures we go deep before wide

    Time: O(V + E)
    Space: O(V) - visited set + stack
    """
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()  # LIFO - Last In First Out

        if node not in visited:
            visited.add(node)
            print(node, end=' ')  # Process node

            # Add neighbors to stack (in reverse for same order as recursive)
            for neighbor in reversed(graph.get(node, [])):
                if neighbor not in visited:
                    stack.append(neighbor)

    return visited


dfs_iterative(graph, 'A')  # Output: A B D E C F

DFS Applications

Application 1: Cycle Detection (Directed Graph)

def has_cycle_directed(graph):
    """
    Detect cycle in directed graph using DFS

    How it works:
    - White (0): Not visited yet
    - Gray (1): Currently in recursion stack (visiting)
    - Black (2): Completely processed

    If we encounter a GRAY node, there's a cycle (back edge)

    Example cycle: A → B → C → A
    When visiting C, we see A is gray (still in stack) = cycle!
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def dfs(node):
        if color[node] == GRAY:  # Back edge = cycle
            return True
        if color[node] == BLACK:  # Already processed
            return False

        color[node] = GRAY  # Mark as visiting

        for neighbor in graph.get(node, []):
            if dfs(neighbor):
                return True

        color[node] = BLACK  # Mark as processed
        return False

    for node in graph:
        if color[node] == WHITE:
            if dfs(node):
                return True
    return False


# Example: Graph with cycle
graph_with_cycle = {
    'A': ['B'],
    'B': ['C'],
    'C': ['A'],  # Back edge to A = cycle!
}

print(has_cycle_directed(graph_with_cycle))  # True

Application 2: Topological Sort

def topological_sort(graph):
    """
    Topological Sort using DFS

    Definition: Linear ordering of vertices such that for every
    directed edge u→v, u comes before v in the ordering.

    Use cases:
    - Task scheduling with dependencies
    - Course prerequisites (take A before B)
    - Build systems (compile X before Y)

    How it works:
    1. Do DFS from each unvisited node
    2. After visiting all descendants, add node to result
    3. Reverse the result (post-order DFS reversed)

    Note: Only works for DAGs (Directed Acyclic Graphs)
    If cycle exists, topological sort is impossible!
    """
    visited = set()
    stack = []  # Store result in reverse post-order

    def dfs(node):
        visited.add(node)

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)

        stack.append(node)  # Add AFTER visiting all descendants

    # Visit all nodes
    for node in graph:
        if node not in visited:
            dfs(node)

    return stack[::-1]  # Reverse to get topological order


# Example: Course prerequisites
# Must take A before B, A before C, B before D, C before D
courses = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

print(topological_sort(courses))  # ['A', 'C', 'B', 'D'] or ['A', 'B', 'C', 'D']
# Both valid! A must be first, D must be last

Application 3: Connected Components (Undirected Graph)

def count_connected_components(graph):
    """
    Count number of connected components using DFS

    Connected component: Set of vertices where each vertex
    is reachable from every other vertex in the set

    How it works:
    1. For each unvisited node, do DFS (finds one component)
    2. Count how many times we start a new DFS

    Example:
    A—B—C    D—E    F  →  3 components
    """
    visited = set()
    count = 0

    def dfs(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)

    for node in graph:
        if node not in visited:
            dfs(node)  # Explore one component
            count += 1  # Found a new component

    return count


# Example: 3 separate components
components_graph = {
    'A': ['B'], 'B': ['A', 'C'], 'C': ['B'],  # Component 1
    'D': ['E'], 'E': ['D'],                    # Component 2
    'F': []                                    # Component 3
}

print(count_connected_components(components_graph))  # 3

DFS Complexity Summary

How BFS Works

Idea: Explore all neighbors at current depth before going deeper.

Analogy: Ripple in water - spread outward in concentric circles.

BFS Traversal Order

Visit order: A (level 0) → B, C (level 1) → D, E, F (level 2)

BFS Implementation (Iterative with Queue)

from collections import deque

def bfs(graph, start):
    """
    Breadth-First Search using queue

    How it works:
    1. Add start node to queue
    2. While queue not empty:
       - Dequeue node (FIFO - First In First Out)
       - If not visited, mark visited and process
       - Enqueue all unvisited neighbors
    3. Queue (FIFO) ensures we explore level by level

    Key difference from DFS:
    - DFS uses stack (LIFO) → go deep
    - BFS uses queue (FIFO) → go wide

    Time: O(V + E)
    Space: O(V) - visited + queue
    """
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()  # FIFO - First In First Out
        print(node, end=' ')  # Process node

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return visited


graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}

bfs(graph, 'A')  # Output: A B C D E F

BFS Application 1: Shortest Path (Unweighted Graph)

from collections import deque

def shortest_path_bfs(graph, start, end):
    """
    Find shortest path in UNWEIGHTED graph using BFS

    Why BFS works for shortest path:
    - BFS explores nodes level by level
    - First time we reach target = shortest path
    - All paths at distance d are explored before distance d+1

    Note: For WEIGHTED graphs, use Dijkstra's algorithm!

    Returns: (distance, path)
    """
    if start == end:
        return (0, [start])

    visited = set([start])
    queue = deque([(start, [start])])  # (node, path_to_node)

    while queue:
        node, path = queue.popleft()

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                new_path = path + [neighbor]

                if neighbor == end:
                    return (len(new_path) - 1, new_path)

                visited.add(neighbor)
                queue.append((neighbor, new_path))

    return (float('inf'), [])  # No path exists


# Example: Social network (6 degrees of separation)
social_network = {
    'Alice': ['Bob', 'Carol'],
    'Bob': ['Alice', 'David'],
    'Carol': ['Alice', 'Eve'],
    'David': ['Bob', 'Frank'],
    'Eve': ['Carol'],
    'Frank': ['David']
}

distance, path = shortest_path_bfs(social_network, 'Alice', 'Frank')
print(f"Distance: {distance}")  # 3
print(f"Path: {' → '.join(path)}")  # Alice → Bob → David → Frank

BFS Application 2: Level-Order Traversal

from collections import deque

def level_order_traversal(graph, start):
    """
    Return nodes grouped by level (distance from start)

    Use case: Organizational hierarchy, family tree levels, etc.

    How it works:
    - Track level for each node
    - Group nodes by level

    Returns: [[level 0 nodes], [level 1 nodes], [level 2 nodes], ...]
    """
    if start not in graph:
        return []

    visited = set([start])
    queue = deque([(start, 0)])  # (node, level)
    levels = [[]]  # levels[i] = nodes at level i

    while queue:
        node, level = queue.popleft()

        # Extend levels list if needed
        if level >= len(levels):
            levels.append([])

        levels[level].append(node)

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, level + 1))

    return levels


result = level_order_traversal(graph, 'A')
print(result)  # [['A'], ['B', 'C'], ['D', 'E', 'F']]

BFS Application 3: 0-1 BFS (Weighted Graph with 0/1 Edges)

from collections import deque

def bfs_01(graph, start, end):
    """
    Shortest path for graph with edge weights 0 or 1

    Optimization over Dijkstra for this special case:
    - Use deque instead of priority queue
    - Weight 0 edges: Add to front (addFirst)
    - Weight 1 edges: Add to back (addLast)

    Why it works: Maintains distance-sorted order in deque

    Time: O(V + E) - faster than Dijkstra's O((V+E) log V)
    """
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    dq = deque([start])

    while dq:
        node = dq.popleft()

        if node == end:
            return dist[end]

        for neighbor, weight in graph.get(node, []):
            new_dist = dist[node] + weight

            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist

                if weight == 0:
                    dq.appendleft(neighbor)  # Add to front
                else:  # weight == 1
                    dq.append(neighbor)  # Add to back

    return dist[end]


# Example: Maze with teleporters (0 cost) and normal moves (1 cost)
maze = {
    'A': [('B', 1), ('C', 0)],  # Teleporter to C (free)
    'B': [('D', 1)],
    'C': [('D', 1), ('E', 0)],  # Teleporter to E
    'D': [('F', 1)],
    'E': [('F', 0)],  # Teleporter to F
    'F': []
}

print(bfs_01(maze, 'A', 'F'))  # 1 (A→C→E→F via teleporters, then 1 normal step)

DFS vs BFS Comparison

How Dijkstra Works

Problem: Find shortest path from source to all vertices in weighted graph (non-negative weights).

Idea: Greedily select closest unvisited vertex, update distances to neighbors.

Dijkstra Visualization

Shortest distances from A: A=0, C=2, B=3 (via C), D=9, E=11

Dijkstra Implementation (Priority Queue)

import heapq

def dijkstra(graph, start):
    """
    Dijkstra's Algorithm for shortest path

    How it works:
    1. Initialize distances: start=0, others=∞
    2. Use min-heap (priority queue) to always process closest vertex
    3. For each vertex:
       - Pop closest unvisited vertex from heap
       - For each neighbor, try to relax (update distance if shorter path found)
       - If distance improved, add to heap

    Why it works:
    - Greedy: Always expand closest vertex (optimal choice)
    - When we pop a vertex from heap, we've found shortest path to it
    - Once vertex is visited, its distance is final (can't improve)

    Limitation: ONLY works with NON-NEGATIVE edge weights
    (Use Bellman-Ford for negative weights)

    Time: O((V + E) log V) with min-heap
    Space: O(V)
    """
    # Initialize distances
    dist = {node: float('inf') for node in graph}
    dist[start] = 0

    # Min-heap: (distance, node)
    heap = [(0, start)]
    visited = set()

    while heap:
        current_dist, node = heapq.heappop(heap)

        # Skip if already visited (duplicate in heap)
        if node in visited:
            continue

        visited.add(node)

        # Relax edges (try to find shorter paths)
        for neighbor, weight in graph.get(node, []):
            new_dist = current_dist + weight

            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))

    return dist


# Example: Road network with distances
roads = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 5)],
    'C': [('B', 1), ('D', 8), ('E', 10)],
    'D': [('E', 2)],
    'E': []
}

distances = dijkstra(roads, 'A')
print(distances)  # {'A': 0, 'C': 2, 'B': 3, 'D': 8, 'E': 10}

Dijkstra with Path Reconstruction

import heapq

def dijkstra_with_path(graph, start, end):
    """
    Dijkstra with path reconstruction

    Returns: (distance, path)
    """
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    parent = {node: None for node in graph}

    heap = [(0, start)]
    visited = set()

    while heap:
        current_dist, node = heapq.heappop(heap)

        if node in visited:
            continue

        visited.add(node)

        # Early exit if we reached target
        if node == end:
            break

        for neighbor, weight in graph.get(node, []):
            new_dist = current_dist + weight

            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                parent[neighbor] = node  # Track path
                heapq.heappush(heap, (new_dist, neighbor))

    # Reconstruct path
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = parent[current]
    path.reverse()

    return (dist[end], path)


distance, path = dijkstra_with_path(roads, 'A', 'E')
print(f"Distance: {distance}")  # 10
print(f"Path: {' → '.join(path)}")  # A → C → D → E

When to Use Dijkstra

• ✅ Single-source shortest path with non-negative weights
• ✅ GPS navigation, network routing protocols (OSPF)
• ✅ Game AI pathfinding (with A* heuristic enhancement)
• ❌ Negative edge weights (use Bellman-Ford instead)
• ❌ All-pairs shortest path (use Floyd-Warshall instead)

Union-Find Data Structure

Purpose: Efficiently track disjoint sets and merge them.

Operations: Find (which set?), Union (merge sets)

Use cases: Kruskal's MST, cycle detection, connected components

class UnionFind:
    """
    Union-Find with path compression and union by rank

    Time Complexity: O(α(n)) ≈ O(1) amortized
    where α is inverse Ackermann function (practically constant)
    """

    def __init__(self, n):
        """Initialize n disjoint sets"""
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        """
        Find representative of set containing x

        Path compression: Make all nodes point directly to root
        """
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x, y):
        """
        Merge sets containing x and y

        Union by rank: Attach smaller tree under larger tree
        Returns: True if sets were different (merge happened)
        """
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return False  # Already in same set

        # Union by rank
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

        return True

    def connected(self, x, y):
        """Check if x and y are in same set"""
        return self.find(x) == self.find(y)


# Example: Detect cycle in undirected graph
def has_cycle_undirected(n, edges):
    """
    Detect cycle in undirected graph using Union-Find

    How it works:
    - For each edge (u, v):
      - If u and v already in same set → cycle!
      - Else: union them
    """
    uf = UnionFind(n)

    for u, v in edges:
        if uf.connected(u, v):
            return True  # Cycle detected
        uf.union(u, v)

    return False


edges = [(0, 1), (1, 2), (2, 0)]  # Triangle = cycle
print(has_cycle_undirected(3, edges))  # True