15.boost最小生成树 prim_minimum_spanning

15.boost最小生成树 prim_minimum_spanning_tree

 1 #include <iostream>
 2 #include <boost/config.hpp>
 3 //图(矩阵实现)
 4 #include <boost/graph/adjacency_matrix.hpp>
 5 #include <boostgraphgraph_utility.hpp>
 6 #include <boost/graph/graph_traits.hpp>
 7 //图(链表实现)
 8 #include <boost/graph/adjacency_list.hpp>
 9 //求最小生成树
10 #include <boost/graph/kruskal_min_spanning_tree.hpp>
11 //prim算法求最小生成树
12 #include <boost/graph/prim_minimum_spanning_tree.hpp>
13 using namespace std;
14 using namespace boost;
15 
16 //顶点名称
17 enum { A, B, C, D, E, F };
18 //顶点个数
19 #define N 6
20 const char *name = "ABCDEF";
21 
22 //无向图
23 void main()
24 {
25     //图,每个结点是vec来实现,无向图,有边长与权重的属性
26     adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int>> myg;
27     add_edge(A, B,13, myg);
28     add_edge(B, C,23 ,myg);
29     add_edge(A, C,1, myg);
30     add_edge(A, D,11, myg);
31     add_edge(C, D,10, myg);
32     add_edge(B, D,11, myg);
33 
34     //定义图的类型
35     typedef adjacency_list<vecS, vecS, undirectedS, property<edge_weight_t, int>> mygraph;
36 
37     //创建边与权重的映射(weight是函数指针)
38     auto weight= get(edge_weight,myg);
39     //property_map<mygraph, edge_weight_t>::type weight = get(edge_weight, myg);
40 
41     //vector数组,存放四个顶点
42     vector<graph_traits<mygraph>::vertex_descriptor> pv(4);
43 
44     //将最小生成树的结果插到vector中
45     prim_minimum_spanning_tree(myg, &pv[0]);
46 
47     //输出
48     for (int i = 0; i < pv.size(); i++)
49     {
50         if (pv[i] != i)
51         {
52             graph_traits<mygraph>::edge_descriptor ed;
53             bool isok;
54             //生成绑定
55             tie(ed, isok) = edge(i, pv[i], myg);
56             cout << "tree" << i << "<--->" << pv[i] << "   " << weight[ed] << endl;
57         }
58     }
59     
60     cin.get();
61 }