Graph Fundamentals
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) |
Every tree so far has had two rules built in: exactly one root with nothing that points at it, and exactly one path between any two nodes. A graph is what is left when you drop both rules. Nodes (usually called vertices) connect to each other through edges. But there is no single start point that everything hangs off. A node can connect to many other nodes. 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 connect to each other. A whole group of people can know each other with no single person that everyone traces back to. Someone can even belong to two separate friend groups that have no connection to each other.
That last part matters more than it sounds. A tree is always one connected piece by definition. Every node is reachable from the root. A graph has no such rule. It might be one connected piece, or it might be several separate pieces in the same data structure with no edges between them. Nothing about the graph itself tells you which one you have.
Representing a graph
structure Graph (adjacency list):
adj: map from node -> list of the neighbors of that node
structure Graph (adjacency matrix):
matrix: n x n grid
matrix[i][j] = 1 if an edge connects i and j, else 0DFS — 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)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 as visited at enqueue time
enqueue(queue, neighbor)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 one fully explores one component
return countCycle 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 you just came from
return true
return falseCycle detection — directed: track the current recursion path
function hasCycleDirected(node, adj, visited, onPath):
visited.add(node)
onPath.add(node) // the nodes on THIS call's path, right now
for neighbor in adj[node]:
if neighbor in onPath: // still inside the call for this node: a 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 falseBoth representations store the same graph. They only trade space for lookup speed in different ways. An adjacency list stores only the edges that 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 one time and each edge one time (two times on an undirected graph, one time per direction it is stored). So they all share the same O(V+E) time bound, for any one that you run.
| Operation | Time | Space | Why |
|---|---|---|---|
| Adjacency list — space | — | O(V + E) | One entry per node, plus one entry per edge in the neighbor list of that node. Nothing is stored for pairs that are not connected. |
| Adjacency matrix — space | — | O(V²) | A cell for every possible pair of nodes, whether an edge exists there or not. This wastes space on a sparse graph, but it is O(1) to check if two specific nodes are connected. |
| DFS / BFS traversal | O(V + E) | O(V) | Every node is visited one time. Every edge is examined one time from each endpoint that stores it. The visited set (and the DFS call stack, or the BFS queue) holds at most every node one time. |
| 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 in total, split across the number of components that exist. |
| Cycle detection (directed or undirected) | O(V + E) | O(V) | This is the same traversal shape as plain DFS, with one extra set (parent tracking, or onPath) that never holds more than one entry per node. |
Forgetting the visited set entirely
Without a visited check, dfs() or bfs() walks back onto a node that it already processed, follows the edges of that node again, and never runs out of places to go. This is 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 is not a bug to detect. It is a normal input to survive.
Using the undirected cycle check on a directed graph, or the reverse
These are genuinely different algorithms, not one algorithm with a small change. On a directed graph, a check of "visited and not the parent" gives false positives often. Two separate edges that point into the same node from different, unrelated branches 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 is not a cycle. Match the check to the edge direction of the graph, every time.
A disconnected graph — one traversal from one start node
dfs or bfs from a single node explores exactly the component that the node lives in, and nothing else. Every node in a separate component is never visited, never counted, never processed, with no error. There is no crash, only a wrong answer that looks complete, because the traversal ran to the end without a failure. The fix from Build It (loop over every node and restart the traversal on anything still unvisited) is not an optimization. It is the difference between a correct answer and a quietly wrong one.
Self-loops and multi-edges
Neither one is invalid input for a graph, even though neither one can happen in a tree. A self-loop (a node connects to itself) means that the node appears in its own neighbor list. A naive undirected cycle check can misfire on it, because the neighbor-equals-parent exclusion does not apply to a self-edge. Multi-edges (the same pair connected two times) mean that a node might appear more than once in the adjacency list of another node. The traversal still visits it only one time, thanks to the visited set. But a naive edge count (for example, to count components or validate a tree) can count too many if it does not remove duplicates.
Sign in to mark problems done — progress syncs across devices.