1

最小スパニング ツリーの重みを見つけるには、boost ライブラリの kruskals アルゴリズムを使用する必要があります。私はそれを管理したと思います

#include <iostream>
#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include<vector>

using namespace std;
using namespace boost;



int main(){

typedef adjacency_list <vecS,vecS,undirectedS,no_property,property <edge_weight_t,int> > Graph;

typedef graph_traits <Graph>::edge_descriptor Edge;
typedef graph_traits <Graph>::vertex_descriptor Vertex;

int a,b,c,no_vertices,no_edges;

cin>>no_vertices>>no_edges;

Graph g(no_vertices);

property_map <Graph,edge_weight_t>::type weightmap=get(edge_weight,g);
vector <Edge> spanning_tree;

for(int i=0;i<no_edges;i++)
{
    bool success;
    Edge e;
    cin>>a>>b>>c;
    tie(e,success)=add_edge(a,b,g);
    weightmap[e]=c;
}

kruskal_minimum_spanning_tree(g,back_inserter(spanning_tree));

//weight of spanning tree
int ww=0;
graph_traits<Graph>::edge_iterator ei, ei_end;
  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
{
   ww=ww+weightmap[*ei];
}

cout<<"\n"<<ww;


return 0;

}

ここで、頂点 0 とそこから最も遠い頂点の間の距離 (重みの合計) を見つける必要がありますか? どうすればそれができるかについてのヒントはありますか？

頂点イテレータを使用することを考えていましたが、重みを weightMap に格納するので、グラフの頂点を反復処理する場合、どのようにアクセスすればよいでしょうか?

編集: プログラムを修正し、kruskal と prim を使用することにしました

1. スパニング ツリーの重みの kruskal 2. 頂点 0 からの各頂点の距離の prim アルゴリズム (マップの距離に格納されているスパニング ツリー内)

残念ながら、何かがうまくいかず、3 番目の頂点である距離 [*頂点] は答え 2 を与えませんが、1 を与えます

また、スパニング ツリーの重みは 7 ではなく 14 です。

私のダミー入力は次のとおりです。

5 6
0 1 1
0 2 2 
1 2 5
1 3 1
3 2 2
2 4 3

ここに私のプログラム：

#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
using namespace std;

int
main()
{
  using namespace boost;

  typedef adjacency_list < vecS, vecS, undirectedS,
    property<vertex_distance_t, int>, property < edge_weight_t, int > > Graph;

    int num_nodes,num_edges,a,b,c;
    cin>>num_nodes>>num_edges;



  Graph g(num_nodes);

  property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g);

  for (int j = 0; j < num_edges ; ++j) {
        cin>>a>>b>>c;
    graph_traits<Graph>::edge_descriptor e;
  bool inserted;
    tie(e, inserted) = add_edge(a, b, g);
    weightmap[e] = c;
  }

    vector < graph_traits < Graph >::vertex_descriptor > p(num_vertices(g));
    cout<<num_vertices(g);


  property_map<Graph, vertex_distance_t>::type distance = get(vertex_distance, g);
  property_map<Graph, vertex_index_t>::type indexmap = get(vertex_index, g);

  prim_minimum_spanning_tree
    (g, *vertices(g).first, &p[0], distance, weightmap, indexmap,
     default_dijkstra_visitor());

  vector <graph_traits<Graph>::edge_descriptor> spanning_tree;

  kruskal_minimum_spanning_tree(g,back_inserter(spanning_tree));
  int ww=0;
  typedef graph_traits < Graph >::edge_descriptor Edge;

  for (vector<Edge>::iterator et= spanning_tree.begin(); et != spanning_tree.end(); ++et)
{
   ww=ww+weightmap[*et];
}

typedef graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = vertices(g); vp.first != vp.second; ++vp.first)
{
    cout<<distance[*vp.first];
}






prim_minimum_spanning_tree
    (g, *vertices(g).first, &p[0], distance, weightmap, indexmap,
     default_dijkstra_visitor());

  return EXIT_SUCCESS;
}

ありがとうございました ：）

4

1 に答える 1

1

Kruskal MST アルゴリズム (特にエッジ リスト) の結果をどのように解釈するかはよくわかりません。これはあなたが探していたものでしょうか：

int ww = 0;
for (auto const& e : spanning_tree) {
    std::cout << "Traversing: " << source(e,g) << " -> " << target(e,g) << ", cost " << weightmap[e] << "\n";
    ww += weightmap[e];
}

cout << "\n" << ww;

それ以外の場合は、先行マップを Kruskal に渡し、目的のパスを読み取ることをお勧めします。

その間、私の上記のスケッチを参照してくださいLive On Coliru

于 2014-10-14T23:07:52.167 に答える