O(1) or O(log V)O(V + E) or O((V + E) log V)O(V^2), O(V * E) or worse
The model
A graph is nodes joined by edges. Whether the edges are directed, weighted or can form cycles decides the algorithm.
Every search runs one loop. Pop a node off the frontier, then push its unvisited neighbors. The frontier's type sets the order.
A visited mark stops loops on cycles. With it, BFS and DFS cost O(V + E), for V nodes and E edges.
Default to an adjacency list. It takes O(V + E) space. A matrix takes O(V^2), even when nearly empty.
With no weights, use BFS. With non-negative weights, use Dijkstra. With any negative edge, use Bellman-Ford.
A queue pops the oldest node, so BFS spreads out by hops. A stack pops the newest, so DFS goes deep. A min-heap pops the nearest node, and that's Dijkstra.
Graph terms & modeling
name the parts, and turn a problem into a graph
Nodes, edges and degree
Find a node's degreeCount its edges. A directed graph has in-degree and out-degree.
Tell a sparse graph from a dense oneSparse means E is near V. Dense means E is near V^2.
adj = {0: [1, 2], 1: [2], 2: []}list, directedadj[u].append(v); adj[v].append(u)undirected, both waysm = [[0] * n for _ in range(n)]matrix, n by nm[u][v] = 1edge from u to v
Pick the defaultAn adjacency list. Most real graphs are sparse.
Choose a matrix insteadWhen V is small, the graph is dense, or you check edges constantly.
Visit every edgeO(V + E) with a list. O(V^2) with a matrix.
TrapA matrix for a sparse graph is mostly zeros. A road map with millions of nodes would need terabytes.
BFSNumbers show visit order. Every node one hop away comes before any node two hops away.DFSThe same graph. DFS follows one branch to its end, then backs up to the next.
Choose BFSFor the fewest hops, the nearest match, or level-by-level work.
Choose DFSFor cycles, components, topological order and the graph's shape.
Give the running time of BFS and DFSO(V + E) for both. Each node and edge is handled once.
Search a wide, shallow graphDFS uses less memory. The BFS queue holds a whole level.
Search a long, deep graphBFS uses less memory. The DFS stack grows with the depth.
TrapPlain DFS can reach a node by a long route first, so it doesn't give the fewest hops. Use BFS for that.
dist = {}; pq = [(0, s)]while pq: d, u = heapq.heappop(pq) if u in dist: continuestale entry, skip it dist[u] = dsettled for good for v, w in adj[u]: if v not in dist: heapq.heappush(pq, (d + w, v))
Explain why a popped distance is finalAny other route passes a node at least as far, and edges only add.
Stop early for one targetReturn when the target is popped.
Swap in a Fibonacci heapO(E + V log V) on paper, but slower than a binary heap in practice.
TipSkip decrease-key. Push a duplicate entry, and drop the stale one when it's popped.
TrapA negative edge gives wrong distances with no error. Dijkstra assumes a settled node never gets cheaper.
indeg = Counter(v for u in adj for v in adj[u])q = deque(u for u in adj if indeg[u] == 0)order = []while q: u = q.popleft(); order.append(u) for v in adj[u]: indeg[v] -= 1 if indeg[v] == 0: q.append(v)
Order tasks so every edge points forwardTopological sort, O(V + E). It needs a DAG, which has no cycles.
Tell whether the sort hit a cyclelen(order)<len(adj)A cycle blocked the nodes left over.
Sort with DFS insteadRecord each node as its DFS call finishes, then reverse.
Choose Kahn's over DFSNo recursion, a free cycle check, a queue you can prioritize.
TrapA partial order is not a shorter valid answer. It proves the input has a cycle.
no cycleFilled means in progress, dashed means done. C reaches D, but D is done, so no cycle.cycleD reaches A while A is still in progress. That back edge closes a cycle.
Detect a cycle in an undirected graphDFS. A visited neighbor that isn't your parent closes a cycle.
Detect it with union-find insteadAn edge whose ends share a root closes a loop. Undirected only.
Detect a cycle in a directed graphDFS with three states. Reaching an in-progress node means a cycle.
TrapChecking only the visited flag reports false cycles in a directed graph. Reaching a node that is done is safe.
def find(x):p[x] is x's parent if p[x] != x: p[x] = find(p[x])path compression return p[x]def union(a, b): a, b = find(a), find(b) if a == b: returnalready joined if size[a] < size[b]: a, b = b, asmaller tree goes under p[b] = a; size[a] += size[b]
Join two sets, or ask whether two nodes connectunion(a,b)find(a)==find(b)Amortized O(α(n)), under 5 for any real input.
Explain path compressionEach find points its whole path straight at the root.
Explain union by rankHang the shorter tree under the taller. The code above uses size.
Choose union-find over DFSWhen edges keep arriving and you keep asking who connects.
Remove an edge from union-findYou can't. Deletions need link-cut or Euler-tour trees.
TrapUnion-find says two nodes connect, not how. For a path or a component's members, use DFS.
