Graphs & Graph Algorithms

Graph Representations & Terminology

A graph G = (V, E) consists of vertices (nodes) and edges (connections). Graphs can be directed (edges have direction) or undirected, and weighted (edges carry a cost) or unweighted. A DAG (Directed Acyclic Graph) is a directed graph with no cycles -- critical for dependency resolution.

Degree

In an undirected graph, the degree of a vertex is the number of edges incident to it. In directed graphs, we distinguish in-degree (incoming edges) and out-degree (outgoing edges). The sum of all degrees always equals 2|E|.

# Adjacency List (dict of lists)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D', 'E'],
    'D': ['B', 'C'],
    'E': ['C']
}

# Adjacency Matrix (2D array)
#     A  B  C  D  E
# A [ 0, 1, 1, 0, 0 ]
# B [ 1, 0, 0, 1, 0 ]
# C [ 1, 0, 0, 1, 1 ]
# D [ 0, 1, 1, 0, 0 ]
# E [ 0, 0, 1, 0, 0 ]

# Edge List
edges = [('A','B'), ('A','C'), ('B','D'), ('C','D'), ('C','E')]

Breadth-First Search

BFS explores a graph level by level using a queue. It visits all neighbors of the current node before moving deeper. Time complexity is O(V + E).

Shortest Path in Unweighted Graphs

BFS naturally finds the shortest path (fewest edges) from a source to any reachable vertex. The first time BFS reaches a node, that path is guaranteed to be shortest.

from collections import deque

def bfs_shortest_path(graph, start, target):
    queue = deque([(start, [start])])
    visited = {start}

    while queue:
        node, path = queue.popleft()
        if node == target:
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None  # no path exists

Depth-First Search

DFS explores as deep as possible along each branch before backtracking. It uses a stack (or recursion). Time complexity is O(V + E), same as BFS, but the traversal order and applications differ significantly.

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

Cycle Detection

In a directed graph, a cycle exists if DFS encounters a node that is currently on the recursion stack (a "back edge"). In undirected graphs, a cycle exists if DFS visits an already-visited node that is not the parent.

Connected Components

Run DFS (or BFS) from each unvisited node. Each run discovers one connected component. For directed graphs, finding strongly connected components requires Tarjan's or Kosaraju's algorithm.

Dijkstra & Bellman-Ford

Dijkstra's Algorithm

Single-source shortest path for graphs with non-negative edge weights. Uses a min-heap (priority queue) to greedily select the next closest unvisited vertex. Time complexity: O((V + E) log V) with a binary heap.

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # stale entry
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(heap, (dist[v], v))
    return dist

Bellman-Ford Algorithm

Handles negative edge weights and can detect negative-weight cycles. Relaxes all edges V-1 times. Time complexity: O(V * E), slower than Dijkstra but more general.

def bellman_ford(vertices, edges, start):
    dist = {v: float('inf') for v in vertices}
    dist[start] = 0

    for _ in range(len(vertices) - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Detect negative-weight cycles
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("Negative-weight cycle detected")
    return dist

Kruskal's & Prim's

A Minimum Spanning Tree (MST) connects all vertices in an undirected weighted graph with the minimum total edge weight, using exactly V-1 edges and no cycles.

Kruskal's Algorithm (Union-Find)

Sort all edges by weight. Greedily add the cheapest edge that does not form a cycle (checked via Union-Find / Disjoint Set). Time: O(E log E).

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])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already connected
        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):
    edges.sort(key=lambda e: e[2])  # sort by weight
    uf = UnionFind(n)
    mst = []
    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            if len(mst) == n - 1:
                break
    return mst

Prim's Algorithm (Min-Heap)

Start from any vertex, greedily add the cheapest edge connecting the MST to a non-MST vertex. Uses a min-heap. Time: O((V + E) log V).

Topological Sort & Beyond

Topological Sort

A linear ordering of vertices in a DAG such that for every directed edge u → v, u comes before v. Used in build systems, task scheduling, course prerequisites, and dependency resolution. Two approaches: DFS-based (reverse post-order) and Kahn's algorithm (BFS with in-degree tracking).

# Kahn's Algorithm (BFS-based)
from collections import deque

def topological_sort(graph, in_degree):
    queue = deque([v for v in graph if in_degree[v] == 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)

    if len(result) != len(graph):
        raise ValueError("Cycle detected -- not a DAG")
    return result

Advanced Algorithms