CAUTION: Boost.Graph in Boost 1.93 deprecates support for C++14 and will require C++17 from Boost 1.95 onwards (see discussion #613).

The Boost Graph Library (BGL) is a generic library that allows users to:

1. Represent graph data using different structures (adjacency matrix, adjacency list, compressed sparse row, vectors of vectors, user-defined data structures).
2. Attach user-defined data to vertices, edges, or the graph itself.
3. Run a large number of algorithms on the graph.
4. Inject user logic into algorithms using visitor hooks.

Try it on Compiler Explorer

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/visitors.hpp>
#include <iostream>
#include <limits>
#include <vector>

struct City {};
struct Road { int cost; };

using namespace boost;
using Graph = adjacency_list<vecS, vecS, directedS, City, Road>;
using Vertex = graph_traits<Graph>::vertex_descriptor;

int main() {
    Graph g(4);
    add_edge(0, 1, Road{1}, g);
    add_edge(1, 2, Road{2}, g);
    add_edge(0, 2, Road{10}, g);
    add_edge(2, 3, Road{1}, g);

    // Storage: you control allocation, lifetime, and container type
    std::vector<Vertex> storage_pred(num_vertices(g));
    std::vector<int>    storage_dist(num_vertices(g));

    // Property maps: lightweight views into the storage
    auto index_map       = get(vertex_index, g);
    auto costs_map       = get(&Road::cost, g);
    auto predecessor_map = make_iterator_property_map(storage_pred.begin(), index_map);
    auto distance_map    = make_iterator_property_map(storage_dist.begin(), index_map);

    dijkstra_shortest_paths(g, vertex(0, g),
        predecessor_map, distance_map,
        costs_map, index_map,
        std::less<int>(), std::plus<int>(),
        std::numeric_limits<int>::max(), 0,
        dijkstra_visitor<null_visitor>());

    for (auto v : make_iterator_range(vertices(g)))
        std::cout << "distance to " << v << " = " << storage_dist[v] << "\n";
}

distance to 0 = 0
distance to 1 = 1
distance to 2 = 3
distance to 3 = 4

BGL ships dozens of graph algorithms: shortest paths (Dijkstra, Bellman-Ford, A*, Floyd-Warshall, Johnson), spanning trees (Kruskal, Prim), maximum flow (Edmonds-Karp, push-relabel, Boykov-Kolmogorov), traversal (BFS, DFS, topological sort), planarity testing, isomorphism, component decomposition, and more.

See the full algorithm reference for the complete catalogue.

• GitHub Issues for bug reports. Search before opening a new one.
• GitHub Discussions for questions, design ideas, and general conversation about the library.
• Boost mailing list for general Boost development. Use the [graph] tag in the subject line.
• CppLang Slack for real-time chat. Request an invite, then join the #boost channel.
• Direct contact with maintainers: see CONTRIBUTING.md#maintainers.

Install Boost via your package manager:

Then wire it into CMake:

find_package(Boost REQUIRED COMPONENTS graph)
target_link_libraries(my_app PRIVATE Boost::graph)

Most of BGL is header-only. Linking Boost::graph is only required for the GraphViz and GraphML parsers.

Bug fixes, new algorithms, documentation and performance work are all welcome. CONTRIBUTING.md covers building Boost from source, running the test suite, and the pull request process.