Graph Traversals

Graph representations and traversal algorithms, foundational for knowledge graphs, GNNs, and any system that models relationships between entities.

Problem

Given an undirected graph, implement:

1. Adjacency list to adjacency matrix conversion
2. Breadth-first search (BFS)
3. Depth-first search (DFS)

Approach

Representation: an adjacency list maps each vertex to its neighbors. To convert to an adjacency matrix, iterate over all edges and set matrix[i][j] = 1.

BFS explores all neighbors at the current depth before moving deeper. Uses a queue. Produces the shortest path in unweighted graphs.

DFS explores as far as possible down each branch before backtracking. Uses a stack. Useful for topological sorting, cycle detection, and connected components.

Implementation

Adjacency List to Matrix

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

vertices = sorted(graph.keys())
v_index = {v: i for i, v in enumerate(vertices)}
n = len(vertices)
adj_matrix = [[0] * n for _ in range(n)]

for v in vertices:
    for neighbor in graph[v]:
        adj_matrix[v_index[v]][v_index[neighbor]] = 1

BFS

from collections import deque

def bfs(graph, root):
    visited = set()
    order = []
    queue = deque([root])
    visited.add(root)

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

DFS

def dfs(graph, root):
    visited = set()
    order = []
    stack = [root]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            order.append(node)
            for neighbor in reversed(sorted(graph[node])):
                if neighbor not in visited:
                    stack.append(neighbor)
    return order

Complexity

Algorithm	Time	Space
Adjacency matrix build	O(V + E)	O(V^2)
BFS	O(V + E)	O(V)
DFS	O(V + E)	O(V)

Takeaway

BFS and DFS are the building blocks for everything from PageRank to graph neural networks (message passing is just repeated neighborhood aggregation). Get comfortable with these and the fancier graph algorithms feel much less mysterious.

---

Back to Algorithms & Data Structures