CPP/Boost/BGL/PrimMST
From ProgrammingExamples
DijkstraDirected.cpp
#include <iostream> #include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/prim_minimum_spanning_tree.hpp> typedef boost::property<boost::edge_weight_t, double> EdgeWeightProperty; typedef boost::adjacency_list<boost::setS, // OutEdgeContainer boost::vecS, // VertexContainer boost::undirectedS, boost::no_property, EdgeWeightProperty> Graph; using PredecessorContainer = std::vector<boost::graph_traits < Graph >::vertex_descriptor>; Graph CreateGraphFromPredecessors(const PredecessorContainer& predecessors) { Graph g(predecessors.size()); for(unsigned int vertexID = 0; vertexID < predecessors.size(); ++vertexID) { if(predecessors[vertexID] != vertexID) { add_edge(predecessors[vertexID], vertexID, g); } } return g; } void PrintEdges(Graph g) { typedef boost::graph_traits<Graph>::edge_iterator edge_iter; std::pair<edge_iter, edge_iter> edgePair; for(edgePair = edges(g); edgePair.first != edgePair.second; ++edgePair.first) { std::cout << *(edgePair.first) << std::endl; } std::cout << std::endl; } int main(int,char*[]) { // Create a graph object Graph g(3); // Create a "triangle" EdgeWeightProperty weight0 = 5; add_edge(0, 1, weight0, g); EdgeWeightProperty weight1 = 3; add_edge(1, 2, weight1, g); EdgeWeightProperty weight2 = 4; add_edge(0, 2, weight2, g); PrintEdges(g); // Create a container to store the predecessors for each vertex. Upon completion of the algorithm, the edges (p[u],u) for all u in V are in the minimum spanning tree. PredecessorContainer predecessors(num_vertices(g)); // "named parameter" signature prim_minimum_spanning_tree(g, &predecessors[0], boost::root_vertex(1)); for (std::size_t i = 0; i != predecessors.size(); ++i) { if (predecessors[i] != i) { std::cout << "parent[" << i << "] = " << predecessors[i] << std::endl; } else { std::cout << "parent[" << i << "] = no predecessors (i.e. root node)" << std::endl; } } Graph mst = CreateGraphFromPredecessors(predecessors); PrintEdges(mst); return 0; }
CMakeLists.txt
cmake_minimum_required(VERSION 2.6) Project(PrimMST) set(Boost_USE_MULTITHREADED ON) FIND_PACKAGE(Boost 1.38 COMPONENTS program_options required) INCLUDE_DIRECTORIES(${INCLUDE_DIRECTORIES} ${Boost_INCLUDE_DIRS}) LINK_DIRECTORIES(${LINK_DIRECTORIES} ${Boost_LIBRARY_DIRS}) ADD_EXECUTABLE(PrimMST PrimMST.cpp)