Graph Fundamentals

On this page

The Idea
Build It
Know It
Break It
Use It

Quick reference

Adjacency list — space	—
Adjacency matrix — space	—
DFS / BFS traversal	O(V + E)
Connected components	O(V + E)
Cycle detection (directed or undirected)	O(V + E)

The Idea

Every tree so far has had two rules baked in: exactly one root with nothing pointing at it, and exactly one path between any two nodes. A graph is what's left when both rules get dropped. Nodes — usually called vertices — connect to each other via edges, but there's no single starting point everything hangs off of, a node can connect to many others, and two nodes can even point back and forth at each other. A tree is a graph; most graphs are not trees.

The everyday version of this shape is a friendship map, not a family tree. A family tree has one ancestor at the top and a strict direction — parent to child, never child to parent. A friendship map has no top: Alice and Bob can be mutually connected, a whole cluster of people can know each other with no single person everyone traces back to, and someone can even belong to two separate friend groups that have no connection to each other at all.

That last part matters more than it sounds like it should. A tree is always one connected piece by definition — every node is reachable from the root. A graph is under no such obligation. It might be one connected blob, or it might be several separate blobs sitting in the same data structure with no edges between them, and nothing about the graph itself will warn you which one you have.

A tree is a graph with two extra promises: no cycles, and exactly one path between any two nodes. Drop both promises and you get a graph — everything below is about what breaks once those guarantees are gone, and what has to be added back by hand to compensate.

Build It

Representing a graph

structure Graph (adjacency list):
    adj: map from node -> list of that node's neighbors

structure Graph (adjacency matrix):
    matrix: n x n grid
    matrix[i][j] = 1 if an edge connects i and j, else 0

DFS — recursive, with a visited set

function dfs(node, adj, visited):
    if node in visited:            // already explored from here — stop
        return
    visited.add(node)
    process(node)
    for neighbor in adj[node]:
        dfs(neighbor, adj, visited)

This is Linked List Cycle again, generalized. There, only a bug could put a cycle in your chain. Here, a cycle is a completely ordinary, valid graph — two nodes pointing at each other is not a mistake, it's just what a graph is allowed to do. Skip the visited check and dfs() calls itself on the same handful of nodes forever, exactly like walking a cyclic linked list with no slow/fast pointers.

BFS — queue-based, with a visited set

function bfs(start, adj):
    visited = {start}
    queue = Queue()
    enqueue(queue, start)
    while queue is not empty:
        node = dequeue(queue)
        process(node)
        for neighbor in adj[node]:
            if neighbor not in visited:
                visited.add(neighbor)     // mark visited at enqueue time
                enqueue(queue, neighbor)

Same queue idea as Phase 3, same level-by-level spirit as Binary Trees' level-order traversal — just no longer limited to two children per node, any number of neighbors works. One detail that trips people up: mark a node visited the moment it's enqueued, not when it's dequeued. Wait until dequeue and the same neighbor can get enqueued by several different nodes before any of them process it, wasting work and — on some graphs — never terminating.

Connected components — restart DFS/BFS from every unvisited node

function countComponents(nodes, adj):
    visited = {}
    count = 0
    for node in nodes:
        if node not in visited:
            count += 1
            dfs(node, adj, visited)    // or bfs — either fully explores one component
    return count

A single dfs(start) only ever sees the component start belongs to — the disconnected-friend-group case from The Idea. Looping over every node and only starting a fresh traversal when you hit one visited hasn't touched yet is what guarantees every component gets found, not just the first one.

Cycle detection — undirected: track the parent

function hasCycleUndirected(node, parent, adj, visited):
    visited.add(node)
    for neighbor in adj[node]:
        if neighbor not in visited:
            if hasCycleUndirected(neighbor, node, adj, visited):
                return true
        elif neighbor != parent:      // visited, and NOT where we just came from
            return true
    return false

In an undirected graph, the edge you just walked in always points back at you — A connects to B means B connects to A, so B will always see A sitting in its visited set. That's not a cycle, that's just the edge you arrived on. Passing parent along and excluding it is what tells apart 'I'm looking at where I came from' from 'I found a real second way back to a node I've already seen.'

Cycle detection — directed: track the current recursion path

function hasCycleDirected(node, adj, visited, onPath):
    visited.add(node)
    onPath.add(node)                  // nodes on THIS call's path, right now
    for neighbor in adj[node]:
        if neighbor in onPath:        // still inside the call for this node — cycle
            return true
        if neighbor not in visited:
            if hasCycleDirected(neighbor, adj, visited, onPath):
                return true
    onPath.remove(node)                // backtracking out — no longer on the path
    return false

The undirected trick doesn't carry over. In a directed graph, an edge only points one way, so seeing a 'visited' neighbor doesn't mean you just walked in from there — it might be a completely different, already-finished branch that shares no relationship with the current one. onPath tracks only the nodes the recursion hasn't returned from yet; a node stays on it from the moment dfs enters it until the moment that call returns. Hitting a neighbor still on that list means the graph looped back into its own in-progress path — a real cycle, not a coincidence of ordering.

Know It

Both representations store the same graph, just trading space for lookup speed differently: an adjacency list only stores edges that actually exist, an adjacency matrix reserves a cell for every possible pair whether an edge is there or not. Every traversal below — DFS, BFS, components, both cycle checks — visits each node once and each edge once (twice on an undirected graph, once per direction it's stored), so they all share the same O(V+E) time bound regardless of which one you're running.

Operation	Time	Space	Why
Adjacency list — space	—	O(V + E)	One entry per node, plus one entry per edge in that node's neighbor list — nothing stored for pairs that aren't connected.
Adjacency matrix — space	—	O(V²)	A cell for every possible pair of nodes, whether an edge exists there or not — wasteful on a sparse graph, but O(1) to check if two specific nodes are connected.
DFS / BFS traversal	O(V + E)	O(V)	Every node is visited once, every edge is examined once from each endpoint that stores it. The visited set (and DFS's call stack, or BFS's queue) holds at most every node once.
Connected components	O(V + E)	O(V)	The outer loop over every node adds only O(V) — the real traversal work is still one DFS/BFS pass total, split across however many components exist.
Cycle detection (directed or undirected)	O(V + E)	O(V)	Same traversal shape as plain DFS, with one extra set (parent tracking, or onPath) that never holds more than one entry per node.

Break It

Forgetting the visited set entirely

the graph has any cycle at all

Without a visited check, dfs() or bfs() will walk back onto a node it already processed, follow that node's edges again, and never run out of somewhere to go — an infinite loop, not a slow answer. A tree traversal never needed this because a tree structurally cannot cycle back on itself. A graph can, and unlike the linked-list case, a cycle here isn't a bug to detect — it's a normal input to survive.

Using the undirected cycle check on a directed graph, or vice versa

the parent-exclusion trick gets applied to a directed graph, or the onPath trick gets applied to an undirected one

These are genuinely different algorithms, not one algorithm with a minor tweak. On a directed graph, checking 'visited and not the parent' gives false positives constantly — two separate edges pointing into the same node from different, unrelated branches will trip it even with zero real cycle. On an undirected graph, onPath alone gives false positives too, because the edge back to the immediate parent is always technically 'on the path' and isn't a cycle. Match the check to the graph's edge direction, every time.

A disconnected graph — one traversal from one start node

the graph has more than one component and code only ever calls dfs(someStartNode) once

dfs/bfs from a single node explores exactly the component that node lives in and nothing else — every node in a separate component is silently never visited, never counted, never processed. There's no error, no crash, just a wrong answer that looks complete because the traversal ran to the end without failing. The fix from Build It — loop over every node and restart the traversal on anything still unvisited — is not an optimization, it's the difference between a correct answer and a quietly wrong one.

Self-loops and multi-edges

a node has an edge to itself, or two nodes are connected by more than one edge

Neither is invalid input for a graph, even though neither can happen in a tree. A self-loop (node connects to itself) means node shows up in its own neighbor list — a naive undirected cycle check can misfire on it, since the neighbor-equals-parent exclusion doesn't apply to a self-edge. Multi-edges (the same pair connected twice) mean a node might appear more than once in another node's adjacency list; traversal still visits it only once thanks to the visited set, but a naive edge-count (for counting components or validating a tree, say) can overcount if it isn't deduplicating.

Use It

Number of Islands

The grid is the graph — each land cell is a node, adjacent land cells are edges. countComponents(), but neighbors come from grid coordinates instead of an adjacency list.

Medium

Flood Fill

dfs() from Build It on a grid: visit a cell, recurse into its 4 neighbors that match the starting color, use the color change itself as the visited marker.

Easy

Max Area of Island

Same traversal as Number of Islands, but have dfs() return a count of cells visited instead of nothing, and track the largest count seen.

Medium

Find if Path Exists in Graph

dfs() or bfs() from Build It, starting at source — return true the moment destination is reached or found in visited.

Easy

Pacific Atlantic Water Flow

Multi-source BFS/DFS: start a traversal from every border cell touching each ocean simultaneously, walking uphill instead of downhill, then intersect the two visited sets.

Medium

Clone Graph

dfs() from Build It, but visited maps each original node to its clone instead of just marking true/false — check the map before recursing to avoid cloning the same node twice.

Medium

Keys and Rooms

Rooms are nodes, keys found in a room are edges to other rooms. dfs()/bfs() from room 0, then check whether visited covers every room.

Medium

Is Graph Bipartite?

bfs()/dfs() from Build It, but instead of a visited set alone, assign each node one of two colors, alternating with every edge crossed — a conflict (both endpoints of an edge share a color) means no valid split exists.

Medium

Course Schedule

A prerequisite is a directed edge. hasCycleDirected() from Build It, verbatim: a cycle means the schedule is impossible.

Medium

Employee Importance

Each employee's subordinates are their neighbors. dfs()/bfs() from the target employee, summing importance across everyone visited.

Medium