Graph Algorithms
Traversal, shortest paths, spanning trees, connectivity and DAG ordering.
Explore a graph layer by layer from a source using a FIFO queue, visiting every node at distance d before any node at distance d + 1.
Explore a graph by following one path as deep as possible before backtracking, using recursion or an explicit stack.
Shortest path in an unweighted graph: BFS from the source, record parents, then walk parents back from the target to reconstruct the path.
Single-source shortest paths on graphs with non-negative edge weights, greedily settling the closest unsettled node using a min-priority queue.
Single-source shortest paths that tolerate negative edge weights: relax every edge V - 1 times, then one more pass to detect negative cycles.
All-pairs shortest paths by dynamic programming over the set of allowed intermediate nodes: three nested loops, O(V³), handles negative edges.
Shortest paths when every edge weighs 0 or 1: a deque replaces the heap — weight-0 edges push to the front, weight-1 edges to the back — giving O(V + E).
Point-to-point shortest path that steers Dijkstra toward the goal with a heuristic h(v): pop by f = g + h; optimal when h never overestimates.
Minimum spanning tree by growing one tree from a start node, always adding the cheapest edge that crosses from the tree to a new node.
Minimum spanning tree by sorting all edges and greedily adding each edge that joins two different components, tracked with union-find.
Partition an undirected graph into maximal groups of mutually reachable vertices with one traversal per group.
Maximal vertex sets of a directed graph in which every vertex can reach every other; computed in linear time by Tarjan or Kosaraju.
Find all strongly connected components in one DFS using discovery indices, low-link values and an explicit stack.
Find strongly connected components with two DFS passes: record finish order, then DFS the reversed graph in decreasing finish time.
Order the vertices of a directed acyclic graph so that every edge points forward; exists iff the graph has no cycle.
Topologically sort a DAG by repeatedly emitting vertices whose in-degree has dropped to zero; leftover vertices reveal a cycle.
Run DFS, record vertices as they finish, and reverse that list; a grey-to-grey edge during the search means a cycle.
Decide whether a graph has a cycle: three-colour DFS for directed graphs; DFS with parent tracking or union-find for undirected graphs.
Colour vertices with two colours so every edge joins different colours; succeeds iff the graph has no odd cycle.
Find every edge of an undirected graph whose removal disconnects it, using DFS discovery times and low-link values.
Find every vertex of an undirected graph whose removal disconnects it, via DFS low-link values with a special rule for the root.
A walk that uses every edge exactly once; exists under simple degree conditions and is built greedily by Hierholzer's algorithm in O(E).
A closed walk using every edge exactly once; exists iff the graph is connected on its edges and every vertex is balanced.