Graph Algorithms
Traversal, ordering, shortest paths, spanning trees, connectivity, flows and special paths. BFS, DFS and Dijkstra have their own pages earlier in this subject.
This is an overview — pick a sub-topic below.
Sub-topics (16)
Topological Sort
Order the vertices of a directed acyclic graph so every edge goes forward.
Bellman-Ford Algorithm
Shortest paths with negative edge weights — relax all edges $V-1$ times, $O(VE)$.
Floyd-Warshall Algorithm
All-pairs shortest paths in $O(V^3)$ using dynamic programming over intermediate vertices.
A* Search
Dijkstra guided by a heuristic estimate of the remaining distance.
Kruskal's Algorithm
Minimum spanning tree: sort edges by weight, add each if it joins two different components (DSU).
Prim's Algorithm
Minimum spanning tree grown from one vertex, always adding the cheapest edge leaving the tree.
Strongly Connected Components
Maximal groups of vertices in a directed graph where every vertex reaches every other.
Tarjan's Algorithm
Finds SCCs in one DFS using discovery times and low-link values, $O(V+E)$.
Kosaraju's Algorithm
Finds SCCs with two DFS passes: one on the graph (finish order), one on the reversed graph.
Bridges and Articulation Points
Edges or vertices whose removal disconnects a graph.
Bipartite Checking
Can the vertices be split into two groups with edges only between groups?
Maximum Flow
The most flow that can be pushed from source to sink given edge capacities.
Minimum Cut
The cheapest set of edges whose removal separates source from sink.
Graph Matching
Pair vertices so no vertex is used twice — maximum bipartite matching via flows or Hopcroft-Karp.
Eulerian Paths
A path using every edge exactly once.
Hamiltonian Paths
A path visiting every vertex exactly once — NP-complete.
Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.
Discussion (0)
Sign in or join free to ask questions and discuss this topic.