Graph Algorithms Reference

Graph Representation

Adjacency Matrix

Space: $O(V^2)$ | Edge Check: $O(1)$ | Add Edge: $O(1)$

# Good for: Dense graphs, frequent edge queries
class GraphMatrix:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0] * vertices for _ in range(vertices)]

    def add_edge(self, u, v, weight=1):
        self.graph[u][v] = weight
        self.graph[v][u] = weight  # For undirected

Adjacency List

Space: $O(V + E)$ | Edge Check: $O(V)$ | Add Edge: $O(1)$

# Good for: Sparse graphs, memory efficiency
from collections import defaultdict

class GraphList:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v, weight=1):
        self.graph[u].append((v, weight))
        self.graph[v].append((u, weight))  # For undirected

Graph Traversal

Breadth-First Search (BFS)

Time: $O(V + E)$ | Space: $O(V)$ Use: Shortest path in unweighted graphs, level-order traversal

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    result = []

    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)

            # Add unvisited neighbors
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)

    return result

def bfs_shortest_path(graph, start, end):
    if start == end:
        return [start]

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

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

        for neighbor in graph[vertex]:
            if neighbor == end:
                return path + [neighbor]

            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None  # No path found

Depth-First Search (DFS)

Time: $O(V + E)$ | Space: $O(V)$ Use: Cycle detection, topological sort, connected components

def dfs_recursive(graph, start, visited=None):
    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):
    visited = set()
    stack = [start]
    result = []

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)

            # Add neighbors in reverse order for consistent traversal
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)

    return result

Shortest Path Algorithms

Dijkstra's Algorithm

Time: $O((V + E) \log V)$ | Space: $O(V)$ Use: Single-source shortest path with non-negative weights

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    pq = [(0, start)]

    while pq:
        current_distance, current_vertex = heapq.heappop(pq)

        # Skip if we've already found a better path
        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

def dijkstra_with_path(graph, start, end):
    distances = {vertex: float('infinity') for vertex in graph}
    previous = {vertex: None for vertex in graph}
    distances[start] = 0
    pq = [(0, start)]

    while pq:
        current_distance, current_vertex = heapq.heappop(pq)

        if current_vertex == end:
            break

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous[neighbor] = current_vertex
                heapq.heappush(pq, (distance, neighbor))

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

    return distances[end], path[::-1] if path[0] == end else None

Bellman-Ford Algorithm

Time: $O(VE)$ | Space: $O(V)$ Use: Single-source shortest path with negative weights, cycle detection

def bellman_ford(graph, start):
    # Step 1: Initialize distances
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0

    # Step 2: Relax edges V-1 times
    vertices = list(graph.keys())
    for _ in range(len(vertices) - 1):
        for vertex in vertices:
            for neighbor, weight in graph[vertex]:
                if distances[vertex] + weight < distances[neighbor]:
                    distances[neighbor] = distances[vertex] + weight

    # Step 3: Check for negative cycles
    for vertex in vertices:
        for neighbor, weight in graph[vertex]:
            if distances[vertex] + weight < distances[neighbor]:
                raise ValueError("Graph contains negative cycle")

    return distances

Floyd-Warshall Algorithm

Time: $O(V^3)$ | Space: $O(V^2)$ Use: All-pairs shortest paths

def floyd_warshall(graph):
    vertices = list(graph.keys())
    n = len(vertices)

    # Initialize distance matrix
    dist = {}
    for i in vertices:
        dist[i] = {}
        for j in vertices:
            if i == j:
                dist[i][j] = 0
            else:
                dist[i][j] = float('infinity')

    # Add edge weights
    for vertex in vertices:
        for neighbor, weight in graph[vertex]:
            dist[vertex][neighbor] = weight

    # Floyd-Warshall algorithm
    for k in vertices:
        for i in vertices:
            for j in vertices:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

Minimum Spanning Tree

Kruskal's Algorithm

Time: $O(E \log E)$ | Space: $O(V)$ Use: Find MST using edge-based approach

class UnionFind:
    def __init__(self, vertices):
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}

    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_mst(vertices, edges):
    # Sort edges by weight
    edges.sort(key=lambda x: x[2])

    uf = UnionFind(vertices)
    mst = []
    total_weight = 0

    for u, v, weight in edges:
        if uf.union(u, v):
            mst.append((u, v, weight))
            total_weight += weight

            if len(mst) == len(vertices) - 1:
                break

    return mst, total_weight

Prim's Algorithm

Time: $O((V + E) \log V)$ | Space: $O(V)$ Use: Find MST using vertex-based approach

def prim_mst(graph, start):
    mst = []
    visited = {start}
    edges = [(weight, start, neighbor) for neighbor, weight in graph[start]]
    heapq.heapify(edges)
    total_weight = 0

    while edges and len(visited) < len(graph):
        weight, u, v = heapq.heappop(edges)

        if v not in visited:
            visited.add(v)
            mst.append((u, v, weight))
            total_weight += weight

            # Add new edges from v
            for neighbor, edge_weight in graph[v]:
                if neighbor not in visited:
                    heapq.heappush(edges, (edge_weight, v, neighbor))

    return mst, total_weight

Topological Sorting

Kahn's Algorithm (BFS-based)

Time: $O(V + E)$ | Space: $O(V)$

from collections import deque, defaultdict

def topological_sort_kahn(graph):
    # Calculate in-degrees
    in_degree = defaultdict(int)
    for vertex in graph:
        for neighbor in graph[vertex]:
            in_degree[neighbor] += 1

    # Initialize queue with vertices having 0 in-degree
    queue = deque([v for v in graph if in_degree[v] == 0])
    result = []

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

        # Reduce in-degree of neighbors
        for neighbor in graph[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # Check for cycles
    if len(result) != len(graph):
        raise ValueError("Graph has a cycle")

    return result

DFS-based Topological Sort

Time: $O(V + E)$ | Space: $O(V)$

def topological_sort_dfs(graph):
    visited = set()
    stack = []

    def dfs(vertex):
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(vertex)

    for vertex in graph:
        if vertex not in visited:
            dfs(vertex)

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

Strongly Connected Components

Kosaraju's Algorithm

Time: $O(V + E)$ | Space: $O(V)$

def kosaraju_scc(graph):
    # Step 1: Get finish times with DFS
    visited = set()
    finish_order = []

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

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

    # Step 2: Create transpose graph
    transpose = defaultdict(list)
    for vertex in graph:
        for neighbor in graph[vertex]:
            transpose[neighbor].append(vertex)

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

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

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

    return sccs

Algorithm Selection Guide

Common Graph Problems

Cycle Detection

def has_cycle_undirected(graph):
    visited = set()

    def dfs(vertex, parent):
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor == parent:
                continue
            if neighbor in visited or dfs(neighbor, vertex):
                return True
        return False

    for vertex in graph:
        if vertex not in visited:
            if dfs(vertex, -1):
                return True
    return False

def has_cycle_directed(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {vertex: WHITE for vertex in graph}

    def dfs(vertex):
        color[vertex] = GRAY
        for neighbor in graph[vertex]:
            if color[neighbor] == GRAY:  # Back edge
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[vertex] = BLACK
        return False

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

Bipartite Check

def is_bipartite(graph):
    color = {}

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

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

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