Graph

Graph Code Labs

Mental Model

A graph separates entities (vertices) from relationships (edges). Unlike a tree, a vertex may have multiple incoming paths, and cycles may return to already discovered state. Direction, weight, parallel edges, and self-loops are contract decisions, not implementation details.

Vertices, Edges, and Direction

For an undirected edge, record both directions; for a directed edge, record only source to target. Degree, reachability, and cycle meaning change with direction. Normalize duplicate-edge policy before building storage so traversal and complexity claims match the logical graph.

Choose an Adjacency Representation

An adjacency list uses O(V + E) space and enumerates actual neighbors efficiently. An adjacency matrix uses O(V squared) space but tests a particular edge in O(1). Compare density and query type rather than choosing by habit. Sets deduplicate neighbors; lists preserve repeated edges and input order.

def build_graph_representations(node_count, edges):
    adjacency = [set() for _ in range(node_count)]
    matrix = [[0 for _ in range(node_count)] for _ in range(node_count)]
    for left, right in edges:
        adjacency[left].add(right)
        adjacency[right].add(left)
        matrix[left][right] = 1
        matrix[right][left] = 1
    return [[sorted(neighbors) for neighbors in adjacency], matrix]

Traverse with Explicit Visited State

DFS and BFS need visited state because a graph can contain cycles and converging paths. Mark when an item is discovered to prevent duplicate frontier entries. To find components, begin a traversal from each still-unvisited vertex; one traversal consumes exactly one connected component.

def component_sizes(node_count, edges):
    adjacency = [[] for _ in range(node_count)]
    for left, right in edges:
        adjacency[left].append(right)
        adjacency[right].append(left)
    visited = set()
    sizes = []
    for start in range(node_count):
        if start in visited:
            continue
        visited.add(start)
        stack = [start]
        size = 0
        while stack:
            node = stack.pop()
            size += 1
            for neighbor in adjacency[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
        sizes.append(size)
    return sizes

The deque reference(opens in a new tab) supports the BFS frontier; a list supports iterative DFS as a stack. Both traversals are O(V + E) with adjacency lists because each vertex and stored edge is examined a bounded number of times.

Choose Graph or Grid or Tree

Choose a graph for arbitrary relationships, multiple paths, cycles, or dependencies. Choose an implicit grid when neighbors derive from coordinates instead of stored edges. Choose a rooted tree when every non-root node has one parent and there is a unique root path; then parent state can replace a general visited set. Compare BFS, DFS, topological order, and shortest-path algorithms only after the edge contract is known.

Common Pitfalls

• Adding only one direction for an undirected edge loses reachability.
• Marking visited at removal permits duplicate enqueues and inflated work.
• Omitting isolated vertices because they never appear in the edge list loses components.
• Using a V×V matrix for a sparse graph wastes memory.
• Treating any repeated vertex as a directed-cycle proof ignores active versus completed state.

Explain It in an Interview

State V, E, direction, weight, and duplicate policy before coding. Define what visited means and when it changes. Give O(V + E) for adjacency-list traversal, noting that undirected edges are stored twice, and distinguish frontier space from representation space.

Build Graph Representations(opens in a new tab) forces a storage decision. Course Schedule(opens in a new tab) adds direction and cycle detection to model prerequisites.