提高最小生成树，如何先做深度？

本文介绍了提高最小生成树，如何先做深度？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我想使用Boost Graph库提供的kruskal_minimum_spanning_tree算法构建最小生成树。

I would like to construct a minimum spanning tree using the kruskal_minimum_spanning_tree algorithm available in the boost graph library.

的输出

kruskal_minimum_spanning_tree（克，性病:: back_inserter（spanning_tree））;

BGL的例子是边一个简单的列表。不过，我想处理一个深度优先算法树，不知道该怎么做。

from the BGL example is a simple list of edges. However, I would like to process the tree with a depth first algorithm and do not know how to do that.

可能有人给我一个提示这个？

Could someone give me a hint on this?

推荐答案

下面是对问题和克鲁斯卡的好榜样，并编写自定义的DFS游客的解决方案。它应该运行原样。示例输出在下面的是自包含的code所示。正如我在评论中提到的MST算法的输出是一组边。这说明您如何使用这些数据来建立一个新的图形。

Here is a solution to the problem and good example of Kruskal and writing a custom DFS visitors. It should run as is. Example output in shown in the code below as to be self contained. As I mentioned in the comment the output of the MST algorithm is a set of edges. This shows you how to construct a new graph using that data.

例采取从 en.wikipedia/wiki/Kruskals_algorithm 。

改进的任何建议将是AP preciated。谢谢你。

Any suggestions for improvement would be appreciated. Thanks.

/** Kruskal example from en.wikipedia/wiki/Kruskal's_algorithm MST followed by DFS Written by Paul W. Bible */ #include <iostream> #include <vector> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/graph/kruskal_min_spanning_tree.hpp> using namespace std; using namespace boost; typedef adjacency_list < vecS, vecS, undirectedS, property< vertex_index_t, size_t> , property< edge_index_t, size_t, property<edge_weight_t,double> > > Graph; typedef graph_traits<Graph>::vertex_descriptor Vertex; typedef graph_traits<Graph>::edge_descriptor Edge; typedef boost::property_map< Graph, boost::vertex_index_t>::type VertexIndexMap; typedef boost::property_map< Graph, boost::edge_weight_t>::type WeightMap; //DFS visitor, got help from stackoverflow/questions/14126/how-to-create-a-c-boost-undirected-graph-and-traverse-it-in-depth-first-search // and www.boost/doc/libs/1_55_0/libs/graph/example/dfs-example.cpp struct MyVis:default_dfs_visitor{ //Default dfs is templeted to work with any Edge or Graph class // you will need to pass external graph info to the class MyVis(vector<string> vNames):vertNames(vNames){} template < typename Edge, typename Graph > void tree_edge(Edge e, const Graph& g) const { //This works since all graph verts will have an index VertexIndexMap vMap = get(boost::vertex_index,g); //print output message, source and target get the edge vertices cout << "Edge " << vertNames.at(vMap[source(e,g)]) << " " << vertNames.at(vMap[target(e,g)]) << endl; //cout << vertNames.size() << endl; } private: vector<string> vertNames; }; int main(int argc, char* argv[]){ Graph G; vector<Vertex> verts; vector<Edge> edges; /* Vertices 0 A 1 B 2 C 3 D 4 E 5 F 6 G */ //add 7 vertices for(size_t i = 0; i < 7; ++i){ Vertex v = add_vertex(G); verts.push_back(v); } //vertex to index map, typdef above VertexIndexMap vertexIndexMap = get(boost::vertex_index, G); vector<string> vertexNames(num_vertices(G)); // Create the external property map, this map wraps the storage vector vertexNames boost::iterator_property_map< std::vector< string >::iterator, VertexIndexMap > vertexNameMap(vertexNames.begin(), vertexIndexMap); //set names vertexNames.at(0) = "A"; vertexNames.at(1) = "B"; vertexNames.at(2) = "C"; vertexNames.at(3) = "D"; vertexNames.at(4) = "E"; vertexNames.at(5) = "F"; vertexNames.at(6) = "G"; //get internal weight map WeightMap weightMap = get(edge_weight,G); //Edge 1 A -> B, weight 7 pair<Edge,bool> myPair = add_edge(verts.at(0),verts.at(1),G); edges.push_back(myPair.first); weightMap[myPair.first] = 7.0; //Edge 2 A -> D, weight 5 myPair = add_edge(verts.at(0),verts.at(3),G); edges.push_back(myPair.first); weightMap[myPair.first] = 5.0; //Edge 3 B -> C, weight 8 myPair = add_edge(verts.at(1),verts.at(2),G); edges.push_back(myPair.first); weightMap[myPair.first] = 8.0; //Edge 4 B -> D, weight 9 myPair = add_edge(verts.at(1),verts.at(3),G); edges.push_back(myPair.first); weightMap[myPair.first] = 9.0; //Edge 5 B -> E, weight 7 myPair = add_edge(verts.at(1),verts.at(4),G); edges.push_back(myPair.first); weightMap[myPair.first] = 7.0; //Edge 6 C -> E, weight 5 myPair = add_edge(verts.at(2),verts.at(4),G); edges.push_back(myPair.first); weightMap[myPair.first] = 5.0; //Edge 7 D -> E, weight 15 myPair = add_edge(verts.at(3),verts.at(4),G); edges.push_back(myPair.first); weightMap[myPair.first] = 15.0; //Edge 8 D -> F, weight 6 myPair = add_edge(verts.at(3),verts.at(5),G); edges.push_back(myPair.first); weightMap[myPair.first] = 6.0; //Edge 9 E -> F, weight 8 myPair = add_edge(verts.at(4),verts.at(5),G); edges.push_back(myPair.first); weightMap[myPair.first] = 8.0; //Edge 10 E -> G, weight 9 myPair = add_edge(verts.at(4),verts.at(6),G); edges.push_back(myPair.first); weightMap[myPair.first] = 9.0; //Edge 11 F -> G, weight 11 myPair = add_edge(verts.at(5),verts.at(6),G); edges.push_back(myPair.first); weightMap[myPair.first] = 11.0; //output cout << "vertices " << num_vertices(G) << endl; cout << "edges " << num_edges(G) << endl; //create a stoage vector for MST edges vector<Edge> spanning_tree_edges; kruskal_minimum_spanning_tree(G, std::back_inserter(spanning_tree_edges)); cout << "num MST edges " << spanning_tree_edges.size() << endl; //create a graph for the MST Graph MST; //get a weight map for the MST, may be used later WeightMap mstWeightMap = get(edge_weight,MST); //create a list of original names for the MST graph. vector<string> mstNames(num_vertices(G)); //the MST must span all verts in G //Index map for verts in MST, all graphs use an indepenent index system. VertexIndexMap mstIndexMap = get(boost::vertex_index, MST); cout << "MST Edges" << endl; for(size_t i = 0; i < spanning_tree_edges.size(); ++i){ //get the edge Edge e = spanning_tree_edges.at(i); //get the vertices Vertex v1 = source(e,G); Vertex v2 = target(e,G); // output edge information cout << "edge weight " << weightMap[e] << " v1 " << vertexNameMap[v1] << " v2 " << vertexNameMap[v2] << endl; //insert the edge to the MST graph // Both graphs will share the vertices in verts list. myPair = add_edge(v1,v2,MST); //set the correct weights // may be needed at some point Edge mstE = myPair.first; mstWeightMap[mstE] = weightMap[e]; //get the vertex index in the MST and set the name to that of original graph // mstNames will be used by the visitor mstNames.at(mstIndexMap[v1]) = vertexNameMap[v1]; mstNames.at(mstIndexMap[v2]) = vertexNameMap[v2]; } //Create your custom visitor and pass names to the visitor MyVis vis(mstNames); cout << "DFS on MST: start node E" << endl; //call dfs, see visitor implimentation above. boost::depth_first_search(MST, visitor(vis).root_vertex(verts.at(4))); cout << "DFS on MST: start node B" << endl; //call dfs, see visitor implimentation above. boost::depth_first_search(MST, visitor(vis).root_vertex(verts.at(1))); /* output vertices 7 edges 11 num MST edges 6 MST Edges edge weight 5 v1 A v2 D edge weight 5 v1 C v2 E edge weight 6 v1 D v2 F edge weight 7 v1 B v2 E edge weight 7 v1 A v2 B edge weight 9 v1 E v2 G DFS on MST: start node E Edge E C Edge E B Edge B A Edge A D Edge D F Edge E G DFS on MST: start node B Edge B E Edge E C Edge E G Edge B A Edge A D Edge D F */ //hold for output cin.get(); }