Algorithms

Boost.Graph ships with ~80 generic graph algorithms, grouped into the categories below. Every algorithm is a function template and works against any graph type that models the required concepts (see Graph Concepts).

Category	What it covers
Traversal	Breadth-first and depth-first search, with visitor-based customization points for tracking discovery, finish order, edge classification, and more.
Shortest Paths	Dijkstra, Bellman-Ford, DAG shortest paths, Johnson all-pairs, Floyd-Warshall, A*, and resource-constrained shortest paths.
Spanning Trees	Kruskal, Prim, random spanning trees (Wilson’s algorithm), and common spanning trees of two graphs.
Connected Components	Connected, strongly connected (Tarjan), biconnected components with articulation points, and incremental/disjoint-sets variants.
Network Flow	Max-flow (Edmonds-Karp, push-relabel, Boykov-Kolmogorov), min-cost-flow (cycle canceling, successive shortest paths), Stoer-Wagner min cut, Edmonds maximum matching.
Topological Sort	Topological ordering of a DAG via DFS.
Graph Coloring	Sequential vertex coloring, edge coloring, bipartiteness test, odd-cycle extraction.
Connectivity	Edge connectivity, s-t connectivity.
Graph Metrics	PageRank, Brandes betweenness, degree / closeness / eccentricity, geodesic distance, clustering coefficient, core numbers, profile, wavefront, bandwidth.
Graph Isomorphism	General isomorphism, VF2 subgraph isomorphism, McGregor common subgraphs.
Planar Graphs	Boyer-Myrvold planarity test and embedding, Chrobak-Payne straight line drawing, Kuratowski subgraph extraction, face traversal, make-connected / biconnected / maximal-planar.
Layout	Random, circle, Kamada-Kawai spring, Fruchterman-Reingold force-directed, Gürsoy-Atun layouts.
Sparse Matrix Ordering	Cuthill-McKee, King, minimum-degree, Sloan orderings for bandwidth and profile reduction.
Cycle Detection	Hawick circuits (all elementary cycles), Tiernan all cycles, Howard cycle ratio.
Clique Detection	Bron-Kerbosch enumeration of maximal cliques.
Utility	Copy, transpose, transitive closure / reduction, Lengauer-Tarjan dominators, metric-TSP approximation, maximum adjacency search, neighbor BFS, loop-erased random walk, graph statistics, and more.

Category

What it covers

Traversal

Breadth-first and depth-first search, with visitor-based customization points for tracking discovery, finish order, edge classification, and more.

Shortest Paths

Dijkstra, Bellman-Ford, DAG shortest paths, Johnson all-pairs, Floyd-Warshall, A*, and resource-constrained shortest paths.

Spanning Trees

Kruskal, Prim, random spanning trees (Wilson’s algorithm), and common spanning trees of two graphs.

Connected Components

Connected, strongly connected (Tarjan), biconnected components with articulation points, and incremental/disjoint-sets variants.

Network Flow

Max-flow (Edmonds-Karp, push-relabel, Boykov-Kolmogorov), min-cost-flow (cycle canceling, successive shortest paths), Stoer-Wagner min cut, Edmonds maximum matching.

Topological Sort

Topological ordering of a DAG via DFS.

Graph Coloring

Sequential vertex coloring, edge coloring, bipartiteness test, odd-cycle extraction.

Connectivity

Edge connectivity, s-t connectivity.

Graph Metrics

PageRank, Brandes betweenness, degree / closeness / eccentricity, geodesic distance, clustering coefficient, core numbers, profile, wavefront, bandwidth.

Graph Isomorphism

General isomorphism, VF2 subgraph isomorphism, McGregor common subgraphs.

Planar Graphs

Boyer-Myrvold planarity test and embedding, Chrobak-Payne straight line drawing, Kuratowski subgraph extraction, face traversal, make-connected / biconnected / maximal-planar.

Layout

Random, circle, Kamada-Kawai spring, Fruchterman-Reingold force-directed, Gürsoy-Atun layouts.

Sparse Matrix Ordering

Cuthill-McKee, King, minimum-degree, Sloan orderings for bandwidth and profile reduction.

Cycle Detection

Hawick circuits (all elementary cycles), Tiernan all cycles, Howard cycle ratio.

Clique Detection

Bron-Kerbosch enumeration of maximal cliques.

Utility

Copy, transpose, transitive closure / reduction, Lengauer-Tarjan dominators, metric-TSP approximation, maximum adjacency search, neighbor BFS, loop-erased random walk, graph statistics, and more.

Edit this Page