Graphs

A graph is nodes connected by edges. Trees are a special case — a graph with no cycles and one path between any two nodes — so everything here generalises what you already know about trees, with one addition: you must track visited nodes, because a graph can lead you in circles.

Representing a Graph

The adjacency list is the default. Matrices only pay off on dense graphs or when you constantly ask about specific pairs.

from collections import defaultdict


def build_graph(n: int, edges: list[list[int]]) -> dict[int, list[int]]:
    """Adjacency list for an undirected graph with nodes 0..n-1."""
    graph: defaultdict[int, list[int]] = defaultdict(list)

    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)   # drop this line for a directed graph

    return graph

Traversal

Both DFS and BFS work exactly as they do on trees, plus a visited set.

• BFS finds the shortest path in an unweighted graph, because it explores in order of distance
• DFS is the tool for connectivity, cycle detection and topological ordering

Not Every Graph Problem Needs a Traversal

Some problems are stated in graph language but answered by counting degrees — how many edges enter or leave each node.

• Find the Town Judge — the judge is the unique node with in-degree n-1 and out-degree 0, found by one pass over the edges

Recognising this saves you from writing a traversal you did not need. When a problem describes a property in terms of "everyone trusts…", "nobody points to…", or "exactly one node has…", check whether degree counting settles it first.

All Problems

Related Elsewhere

• Binary Tree Level Order Traversal — BFS in its simplest setting
• N-ary Tree Preorder Traversal — DFS, recursive and iterative
• Jump Game II — BFS levels computed implicitly, with no queue at all