Graph Algorithms

Introduction

Graphs model relationships and connections. Graph algorithms solve problems like finding shortest paths, detecting cycles, and discovering connected components. They're essential for networking, social media, maps, and countless other applications.

Learning Objectives

By the end of this reading, you will be able to:

• Implement BFS and DFS
• Find shortest paths with Dijkstra and Bellman-Ford
• Compute minimum spanning trees
• Perform topological sorting
• Detect cycles and find connected components

1. Graph Traversals

Breadth-First Search (BFS)

Explore level by level, closest nodes first.

from collections import deque

def bfs(graph, start):
    """
    Time: O(V + E), Space: O(V)
    Returns nodes in BFS order
    """
    visited = {start}
    queue = deque([start])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

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

    return result


def bfs_shortest_path(graph, start, end):
    """Find shortest path (unweighted) using BFS"""
    if start == end:
        return [start]

    visited = {start}
    queue = deque([(start, [start])])

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

        for neighbor in graph[node]:
            if neighbor == end:
                return path + [neighbor]
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return []  # No path exists

Depth-First Search (DFS)

Explore as deep as possible before backtracking.

def dfs_recursive(graph, start, visited=None):
    """
    Time: O(V + E), Space: O(V)
    """
    if visited is None:
        visited = set()

    visited.add(start)
    result = [start]

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

    return result


def dfs_iterative(graph, start):
    """Iterative DFS using explicit stack"""
    visited = set()
    stack = [start]
    result = []

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            result.append(node)
            # Add neighbors (reversed to match recursive order)
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

    return result

BFS vs DFS

2. Shortest Path Algorithms

Dijkstra's Algorithm

Single-source shortest paths for non-negative weights.

import heapq

def dijkstra(graph, start):
    """
    graph: {node: [(neighbor, weight), ...]}
    Returns: distances dict, predecessors dict

    Time: O((V + E) log V) with binary heap
    """
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    predecessors = {node: None for node in graph}

    heap = [(0, start)]

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

        if current_dist > distances[current]:
            continue

        for neighbor, weight in graph[current]:
            distance = current_dist + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                predecessors[neighbor] = current
                heapq.heappush(heap, (distance, neighbor))

    return distances, predecessors


def get_path(predecessors, start, end):
    """Reconstruct path from predecessors"""
    path = []
    current = end

    while current is not None:
        path.append(current)
        current = predecessors[current]

    path.reverse()
    return path if path[0] == start else []

Bellman-Ford Algorithm

Handles negative weights, detects negative cycles.

def bellman_ford(vertices, edges, start):
    """
    vertices: list of vertex ids
    edges: list of (u, v, weight)
    Returns: distances dict, or None if negative cycle

    Time: O(V × E)
    """
    distances = {v: float('inf') for v in vertices}
    distances[start] = 0
    predecessors = {v: None for v in vertices}

    # Relax all edges V-1 times
    for _ in range(len(vertices) - 1):
        for u, v, weight in edges:
            if distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
                predecessors[v] = u

    # Check for negative cycles
    for u, v, weight in edges:
        if distances[u] + weight < distances[v]:
            return None  # Negative cycle detected

    return distances, predecessors

Floyd-Warshall Algorithm

All-pairs shortest paths.

def floyd_warshall(graph):
    """
    graph: adjacency matrix (2D array)
    Returns: distance matrix

    Time: O(V³), Space: O(V²)
    """
    n = len(graph)
    dist = [row[:] for row in graph]  # Copy

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

3. Minimum Spanning Tree

Kruskal's Algorithm

Greedy by edge weight.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True


def kruskal(n, edges):
    """
    n: number of vertices
    edges: list of (weight, u, v)

    Time: O(E log E)
    """
    edges.sort()
    uf = UnionFind(n)
    mst = []
    total_weight = 0

    for weight, u, v in edges:
        if uf.union(u, v):
            mst.append((u, v, weight))
            total_weight += weight
            if len(mst) == n - 1:
                break

    return total_weight, mst

Prim's Algorithm

Grow tree from starting vertex.

import heapq

def prim(graph, start=0):
    """
    graph: {node: [(neighbor, weight), ...]}

    Time: O(E log V)
    """
    visited = set()
    mst = []
    total_weight = 0

    # (weight, from_node, to_node)
    heap = [(0, -1, start)]

    while heap and len(visited) < len(graph):
        weight, from_node, to_node = heapq.heappop(heap)

        if to_node in visited:
            continue

        visited.add(to_node)
        if from_node != -1:
            mst.append((from_node, to_node, weight))
            total_weight += weight

        for neighbor, edge_weight in graph[to_node]:
            if neighbor not in visited:
                heapq.heappush(heap, (edge_weight, to_node, neighbor))

    return total_weight, mst

4. Topological Sort

Order vertices so all edges go from earlier to later.

Kahn's Algorithm (BFS-based)

from collections import deque

def topological_sort_kahn(graph):
    """
    graph: {node: [neighbors]}
    Returns: topological order, or empty if cycle exists

    Time: O(V + E)
    """
    # Calculate in-degrees
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] = in_degree.get(neighbor, 0) + 1

    # Start with nodes having no dependencies
    queue = deque([node for node in graph if in_degree[node] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # Check for cycle
    if len(result) != len(graph):
        return []  # Cycle detected

    return result

DFS-based Topological Sort

def topological_sort_dfs(graph):
    """
    Time: O(V + E)
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    result = []

    def dfs(node):
        color[node] = GRAY

        for neighbor in graph[node]:
            if color[neighbor] == GRAY:
                return False  # Cycle detected
            if color[neighbor] == WHITE:
                if not dfs(neighbor):
                    return False

        color[node] = BLACK
        result.append(node)
        return True

    for node in graph:
        if color[node] == WHITE:
            if not dfs(node):
                return []  # Cycle

    result.reverse()
    return result

5. Cycle Detection

Undirected Graph

def has_cycle_undirected(graph):
    """Using DFS"""
    visited = set()

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

        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True

        return False

    for node in graph:
        if node not in visited:
            if dfs(node, None):
                return True

    return False

Directed Graph

def has_cycle_directed(graph):
    """Using DFS with three colors"""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def dfs(node):
        color[node] = GRAY

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

        color[node] = BLACK
        return False

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

    return False

6. Connected Components

Undirected Graph

def connected_components(graph):
    """Find all connected components"""
    visited = set()
    components = []

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

    for node in graph:
        if node not in visited:
            component = []
            dfs(node, component)
            components.append(component)

    return components

Strongly Connected Components (Directed)

Kosaraju's Algorithm:

def strongly_connected_components(graph):
    """
    Kosaraju's Algorithm
    Time: O(V + E)
    """
    # Step 1: Get finish order from DFS
    visited = set()
    finish_order = []

    def dfs1(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs1(neighbor)
        finish_order.append(node)

    for node in graph:
        if node not in visited:
            dfs1(node)

    # Step 2: Build transposed graph
    transposed = {node: [] for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            transposed[neighbor].append(node)

    # Step 3: DFS on transposed in reverse finish order
    visited = set()
    sccs = []

    def dfs2(node, component):
        visited.add(node)
        component.append(node)
        for neighbor in transposed[node]:
            if neighbor not in visited:
                dfs2(neighbor, component)

    for node in reversed(finish_order):
        if node not in visited:
            component = []
            dfs2(node, component)
            sccs.append(component)

    return sccs

7. Bipartite Check

def is_bipartite(graph):
    """Check if graph can be 2-colored"""
    color = {}

    def bfs(start):
        queue = deque([start])
        color[start] = 0

        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in color:
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False
        return True

    for node in graph:
        if node not in color:
            if not bfs(node):
                return False

    return True

8. Advanced Algorithms

A* Search

Informed search with heuristic.

import heapq

def astar(graph, start, goal, heuristic):
    """
    heuristic: function(node) -> estimated distance to goal
    """
    open_set = [(heuristic(start), 0, start, [start])]
    closed_set = set()

    while open_set:
        f, g, current, path = heapq.heappop(open_set)

        if current == goal:
            return path

        if current in closed_set:
            continue
        closed_set.add(current)

        for neighbor, weight in graph[current]:
            if neighbor not in closed_set:
                new_g = g + weight
                new_f = new_g + heuristic(neighbor)
                heapq.heappush(open_set, (new_f, new_g, neighbor, path + [neighbor]))

    return []  # No path

Tarjan's Bridge Finding

def find_bridges(graph):
    """Find all bridges (edges whose removal disconnects the graph)"""
    n = len(graph)
    disc = [0] * n
    low = [0] * n
    visited = [False] * n
    bridges = []
    time = [0]

    def dfs(u, parent):
        visited[u] = True
        disc[u] = low[u] = time[0]
        time[0] += 1

        for v in graph[u]:
            if not visited[v]:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append((u, v))
            elif v != parent:
                low[u] = min(low[u], disc[v])

    for i in range(n):
        if not visited[i]:
            dfs(i, -1)

    return bridges

9. Algorithm Summary

Exercises

Basic

1. Implement BFS to find if a path exists between two nodes.

2. Count the number of connected components in an undirected graph.

3. Check if a directed graph is a DAG.

Intermediate

4. Find the shortest path between all pairs of cities using appropriate algorithm.

5. Detect if a course schedule is possible (prerequisite dependencies).

6. Find all bridges in an undirected graph.

Advanced

7. Implement A* for pathfinding on a grid with obstacles.

8. Find the minimum cost to connect all cities with roads (MST).

9. Find strongly connected components and build the condensation graph.

Summary

• BFS: Level-by-level, shortest path in unweighted graphs
• DFS: Deep exploration, useful for many problems
• Dijkstra: Shortest paths with non-negative weights
• Bellman-Ford: Handles negative weights, detects negative cycles
• MST: Kruskal (edge-based) vs Prim (vertex-based)
• Topological sort: Order for DAGs
• Cycle detection: Colors for directed, parent tracking for undirected

Next Module

Number Systems and Binary →