Graph Traversal
Algorithms that visit nodes and edges in a graph.
Graph traversal algorithms explore connected data such as networks, dependency maps, trees, and state spaces.
Breadth-First Search
Explores a graph from a start node in increasing number of edges.
Depth-First Search
Explores a graph by following one path as far as possible before backtracking.
Topological Sort
Orders the nodes of a directed acyclic graph so every prerequisite appears before its dependents.
Articulation Point Detection
Finds graph nodes whose removal would split a connected graph.
Bidirectional Search
Searches from both the start and goal until the frontiers meet.
Connected Components
Groups graph nodes by which nodes can reach each other.
Cycle Detection
Determines whether a graph contains a cycle.
Iterative Deepening DFS
Runs depth-first search repeatedly with increasing depth limits.
Kosaraju's Algorithm
Finds strongly connected components using two passes of depth-first search.
Tarjan's Strongly Connected Components
Finds strongly connected components in one depth-first search pass.
Minimum Spanning Tree
Connects all nodes in a weighted graph with the lowest total edge cost and no cycles.
Kruskal's Algorithm
Builds a minimum spanning tree by adding the cheapest edges that do not create cycles.
Prim's Algorithm
Builds a minimum spanning tree by repeatedly attaching the cheapest edge from the tree to a new node.
Dynamic Programming on DAGs
Solves graph problems by processing directed acyclic graph nodes in dependency order.
Kahn's Algorithm
Produces a topological ordering by repeatedly removing nodes with no incoming edges.
Bridge Detection
Finds edges whose removal would disconnect an undirected graph.
Hierholzer's Algorithm
Builds an Eulerian path or circuit by splicing cycles that consume every edge once.
Euler Tour
Records entry and exit order while traversing a tree or graph.
Tarjan's Offline LCA
Answers lowest-common-ancestor queries in a tree using DFS and union-find.
Binary Lifting LCA
Answers tree ancestor queries by precomputing powers-of-two jumps.
Ford-Fulkerson
Computes maximum flow by repeatedly augmenting along residual paths.
Edmonds-Karp
Computes maximum flow by choosing shortest augmenting paths with BFS.
Dinic's Algorithm
Computes maximum flow using level graphs and blocking flows.
Hopcroft-Karp
Finds maximum bipartite matching by augmenting many shortest paths per phase.
Bron-Kerbosch Algorithm
Bron-Kerbosch Algorithm extracts structure such as components, tours, rankings, or closures from a graph.
PageRank
PageRank scores graph nodes by repeatedly propagating rank through directed links.
HITS Algorithm
HITS Algorithm scores or groups graph nodes by link structure.
Label Propagation Community Detection
Label Propagation Community Detection scores or groups graph nodes by link structure.
Louvain Method
Louvain Method extracts structure such as components, tours, rankings, or closures from a graph.
Girvan-Newman Algorithm
Girvan-Newman Algorithm extracts structure such as components, tours, rankings, or closures from a graph.
Tarjan Bridge-Finding Algorithm
Tarjan Bridge-Finding Algorithm extracts structure such as components, tours, rankings, or closures from a graph.
Chu-Liu-Edmonds Algorithm
Chu-Liu-Edmonds Algorithm extracts structure such as components, tours, rankings, or closures from a graph.
Gabow SCC Algorithm
Gabow SCC Algorithm extracts structure such as components, tours, rankings, or closures from a graph.
Lexicographic Breadth-First Search
Lexicographic Breadth-First Search extracts structure such as components, tours, rankings, or closures from a graph.
Maximum Cardinality Search
Maximum Cardinality Search extracts structure such as components, tours, rankings, or closures from a graph.
Transitive Closure
Transitive Closure extracts structure such as components, tours, rankings, or closures from a graph.
Boruvka's Algorithm
Builds a minimum spanning tree by repeatedly adding each component's cheapest outgoing edge.
Reverse-Delete Algorithm
Builds a minimum spanning tree by deleting expensive edges that are not needed for connectivity.
Transitive Reduction
Removes directed edges that are implied by alternate paths while preserving reachability.
Warshall's Algorithm
Computes transitive closure by repeatedly allowing each vertex as an intermediate step.
Push-Relabel
Computes maximum flow by pushing excess flow from active vertices and raising vertex heights.
Capacity Scaling Max Flow
Capacity Scaling Max Flow addresses maximum flow by solving flow on large-capacity edges first and lowering the scale threshold.
Gomory-Hu Tree
Gomory-Hu Tree addresses all-pairs minimum cuts by building a cut-equivalent tree from repeated minimum cut computations.
Stoer-Wagner Min Cut
Stoer-Wagner Min Cut uses merging weighted vertices while tracking the cheapest phase cut for global minimum cut.
Karger's Min Cut
Karger's Min Cut addresses global minimum cut by randomly contracting edges until only two supernodes remain.
Edmonds' Blossom Algorithm
Edmonds' Blossom Algorithm uses shrinking odd cycles so augmenting paths can be found in non-bipartite graphs for general graph matching.
Bipartite Matching DFS
Bipartite Matching DFS uses searching for augmenting paths from unmatched left-side vertices for bipartite matching.
Gale-Shapley Algorithm
Gale-Shapley Algorithm uses letting one side propose while the other side keeps its best current proposal for stable matching.
Fleury's Algorithm
Fleury's Algorithm uses walking unused edges while avoiding bridges unless no alternative remains for eulerian cycle construction.
Hopcroft-Tarjan Planarity Test
Hopcroft-Tarjan Planarity Test addresses planarity detection by using depth-first search lowpoint structure to detect planarity obstructions.
Boyer-Myrvold Planarity Test
Boyer-Myrvold Planarity Test addresses planarity embedding by incrementally maintaining embedding constraints during depth-first traversal.
Planar Embedding
Planar Embedding addresses planar embedding construction by ordering edges around vertices so a planar graph can be drawn without crossings.
Fruchterman-Reingold Layout
Fruchterman-Reingold Layout uses balancing attractive edge forces and repulsive vertex forces for force-directed graph drawing.
Sugiyama Layered Drawing
Draws directed graphs in layers by ranking vertices, reducing crossings, and assigning coordinates.
Reingold-Tilford Tree Layout
Draws tidy rooted trees by positioning subtrees recursively while separating their contours.
Walker Tree Layout
Walker Tree Layout addresses tree drawing by extending tidy tree placement to variable-size nodes and general rooted trees.
Greedy Graph Coloring
Greedy Graph Coloring uses assigning each vertex the smallest available color in an ordering for vertex coloring.
DSATUR
DSATUR uses choosing the uncolored vertex with the highest saturation degree for vertex coloring.
Welsh-Powell Coloring
Welsh-Powell Coloring uses coloring vertices in descending degree order with the first available color for vertex coloring.
Misra-Gries Edge Coloring
Misra-Gries Edge Coloring addresses edge coloring by rotating fans around vertices to color edges with bounded extra colors.
Weisfeiler-Lehman Refinement
Refines graph vertex colors by repeatedly encoding each vertex's neighborhood color multiset.
VF2 Graph Isomorphism
Tests graph or subgraph isomorphism by backtracking over node mappings with feasibility pruning.
Nauty Canonical Labeling
Nauty Canonical Labeling addresses canonical graph labeling by partitioning and refining vertex sets to produce canonical graph forms.
Greedy Maximal Independent Set
Greedy Maximal Independent Set uses selecting a vertex and deleting its neighbors until no vertices remain for independent set approximation.
Biconnected Components
Finds maximal graph regions that stay connected after removing any one vertex.
Lengauer-Tarjan Dominators
Lengauer-Tarjan Dominators addresses dominator tree construction by combining DFS numbering with union-find style ancestor queries.
Johnson's Cycle Enumeration
Johnson's Cycle Enumeration addresses simple cycle enumeration by blocking and unblocking vertices to enumerate elementary directed cycles.
Chordal Graph Recognition
Chordal Graph Recognition addresses chordal graph recognition by checking whether maximum cardinality search produces a perfect elimination ordering.