Graphs

Intro

A graph is a set of nodes (vertices) connected by edges. Edges can be directed or undirected, weighted or unweighted. Graphs generalize trees (a tree is a connected acyclic graph) and linked lists (a linear graph). Many real-world modeling problems, social networks, dependency resolution, routing, pipelines, reduce to graph problems. Graphs are the most general and the hardest data structure category in interviews. The effort pays off.

In-depth description

Representations

Adjacency list: map from node to list of neighbors. defaultdict(list) in Python. $O(V + E)$ space, efficient for sparse graphs (most real-world graphs).
Adjacency matrix: V × V boolean or weight matrix. $O(V²)$ space, $O(1)$ edge lookup. Good for dense graphs or where you need fast edge queries.
Edge list: list of (u, v, weight) tuples. Compact; used by Kruskal’s MST and Bellman-Ford.

Core algorithms

BFS: $O(V + E)$ . Shortest path in an unweighted graph, level-based exploration. Uses a queue.
DFS: $O(V + E)$ . Cycle detection, topological sort, connected components, path existence. Uses recursion or an explicit stack.
Dijkstra’s algorithm: $O((V + E)$ log V) with a binary heap. Single-source shortest path with non-negative weights.
Bellman-Ford: $O(V · E)$ . Single-source shortest path allowing negative weights; detects negative cycles.
Floyd-Warshall: $O(V³)$ . All-pairs shortest paths via DP over intermediate nodes.
Union-Find (Disjoint Set Union): nearly $O(1)$ per op with path compression and union by rank. Connectivity, cycle detection in undirected graphs, Kruskal’s MST.
Topological sort: $O(V + E)$ . Kahn’s algorithm (BFS on zero-in-degree nodes) or DFS post-order reversed. Only defined on DAGs.
Kruskal’s / Prim’s MST: minimum spanning tree. Kruskal’s uses edge list + union-find; Prim’s uses a priority queue.

Directed vs. undirected, a trap

Many algorithms behave differently on directed graphs. Topological sort requires a DAG. Cycle detection in a directed graph needs three-color marking (white/gray/black). In an undirected graph, union-find or a “don’t revisit parent” trick works.

Time complexity (adjacency list)

Algorithm	Time	Space
BFS / DFS	$O(V + E)$	$O(V)$
Dijkstra (binary heap)	$O((V + E)$ log V)	$O(V)$
Bellman-Ford	$O(V · E)$	$O(V)$
Floyd-Warshall	$O(V³)$	$O(V²)$
Topological sort	$O(V + E)$	$O(V)$
Union-Find (ops)	near $O(1)$ per op, $O(α(n)$ ) amortized	$O(V)$
Kruskal’s / Prim’s MST	$O(E log V)$	$O(V + E)$

Common uses in DSA

Connected components and connectivity: Number of Islands, Friend Circles / Number of Provinces, Accounts Merge, Graph Valid Tree.
Shortest path: unweighted via BFS (Word Ladder, Shortest Path in Binary Matrix), weighted via Dijkstra (Network Delay Time, Cheapest Flights), negative via Bellman-Ford.
Topological ordering: Course Schedule I and II, Alien Dictionary, Parallel Courses.
Cycle detection: directed (via white/gray/black DFS), undirected (via union-find or DFS with parent tracking).
Minimum spanning tree and network design: Kruskal’s (edge list + union-find), Prim’s (priority queue).

Canonical LeetCode problems: #127 Word Ladder, #133 Clone Graph, #200 Number of Islands, #207 Course Schedule, #210 Course Schedule II, #261 Graph Valid Tree, #269 Alien Dictionary, #417 Pacific Atlantic Water Flow, #743 Network Delay Time.

Python example

from collections import defaultdict, deque
import heapq

# Build an adjacency list from an edge list
def build_graph(edges, directed=False):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph

# BFS: shortest path (unweighted)
def bfs_shortest_path(graph, start, target):
    if start == target:
        return 0
    visited = {start}
    q = deque([(start, 0)])
    while q:
        node, dist = q.popleft()
        for neighbor in graph[node]:
            if neighbor == target:
                return dist + 1
            if neighbor not in visited:
                visited.add(neighbor)
                q.append((neighbor, dist + 1))
    return -1

# DFS (iterative) with visited set
def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)
    return visited

# Dijkstra's (non-negative weights); graph: {node: [(neighbor, weight), ...]}
def dijkstra(graph, start):
    dist = {start: 0}
    pq = [(0, start)]
    while pq:
        d, node = heapq.heappop(pq)
        if d > dist.get(node, float('inf')):
            continue
        for neighbor, weight in graph[node]:
            nd = d + weight
            if nd < dist.get(neighbor, float('inf')):
                dist[neighbor] = nd
                heapq.heappush(pq, (nd, neighbor))
    return dist

# Topological sort (Kahn's / BFS on in-degree)
def topo_sort(num_nodes, edges):
    graph = defaultdict(list)
    in_degree = [0] * num_nodes
    for u, v in edges:           # edge u -> v
        graph[u].append(v)
        in_degree[v] += 1
    q = deque([i for i in range(num_nodes) if in_degree[i] == 0])
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                q.append(neighbor)
    return order if len(order) == num_nodes else []   # empty -> cycle

# Union-Find (for Kruskal's / connectivity)
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path compression
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

LeetCode problems

Graphs appear in 18 NeetCode 150 problems across 2 categories (13 Graphs + 5 Advanced Graphs).

Graphs:

200. Number of Islands, DFS/BFS/Union-Find
695. Max Area of Island
133. Clone Graph
994. Rotting Oranges, multi-source BFS
417. Pacific Atlantic Water Flow, reverse DFS from borders
130. Surrounded Regions
207. Course Schedule, cycle detection
210. Course Schedule II, topological sort
684. Redundant Connection, Union-Find
261. Graph Valid Tree
323. Number of Connected Components
127. Word Ladder, bidirectional BFS
269. Alien Dictionary, topological sort from word-pair constraints

Advanced Graphs:

743. Network Delay Time, Dijkstra’s algorithm over weighted directed edges
787. Cheapest Flights Within K Stops, constrained shortest path with stop count as part of the state
1514. Path with Maximum Probability, maximum-probability path using a priority queue
1584. Min Cost to Connect All Points, minimum spanning tree with Manhattan distances
1489. Critical and Pseudo-Critical Edges in MST, MST sensitivity analysis
1192. Critical Connections in a Network, bridge detection with DFS low-link values
332. Reconstruct Itinerary, Eulerian path construction with lexical tie-breaking
778. Swim in Rising Water, path search over a rising threshold

Graph theory deep dive, full coverage of terminology, graph types, components, SCCs, DAGs, bipartite graphs, and problem modeling with weighted edges
Named algorithms: BFS, level-by-level traversal and shortest path in unweighted graphs
Named algorithms: DFS, commit-and-backtrack traversal, cycle detection, topological sort
Named algorithms: Dijkstra’s, single-source shortest paths on non-negative weighted graphs
Named algorithms: Bellman-Ford, shortest paths with negative weights
Named algorithms: Kahn’s, topological sort via BFS
Named algorithms: Tarjan’s, strongly connected components in one DFS pass
LeetCode graphs category