bagnalla/cpp_graphs

C++ graph library

cpp_graphs

A simple graph library for practice/brushing up on basic graph algorithms and experimenting with modern C++ features (e.g., concepts).

The graph data structure is defined in graph.h. Code shared between multiple algorithms is in common.h. A binary min-heap data structure is defined in binary_heap.h, and a union-find (disjoint-set) data structure is defined in union_find.h.

Graph algorithms implemented:

• Dijkstra's shortest path (dijkstra.h),
• A* (astar.h),
• Prim's minimum spanning tree (forest) (prim.h),
• Kruskal's minimum spanning tree (forest) (kruskal.h),
• Kahn's topological sort (kahn.h).

We also implement a few sorting algorithms (specialized to vectors but generic in the type of elements) in sort.h.