0

最小スパニングツリーで、すべてのノードから最も遠いノードまでの距離を見つける必要があります。これまでにこれを行いましたが、ノードからの最長距離を見つける手がかりがありませんでした。

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

using namespace std;
using namespace boost;

int main()
{
typedef adjacency_list< vecS, vecS, undirectedS, property <vertex_distance_t,int>, property< edge_weight_t, int> > Graph;
int test=0,m,a,b,c,w,d,i,no_v,no_e,arr_w[100],arr_d[100];
cin>>test;
m=0;
while(m!=test)
{
cin>>no_v>>no_e;
Graph g(no_v);
property_map <Graph, edge_weight_t>:: type weightMap=get(edge_weight,g);
bool bol;
graph_traits<Graph>::edge_descriptor ed;

for(i=0;i<no_e;i++)
{
cin>>a>>b>>c;
tie(ed,bol)=add_edge(a,b,g);
weightMap[ed]=c;
}

property_map<Graph,edge_weight_t>::type weightM=get(edge_weight,g);
property_map<Graph,vertex_distance_t>::type distanceMap=get(vertex_distance,g);
property_map<Graph,vertex_index_t>::type indexMap=get(vertex_index,g);

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

kruskal_minimum_spanning_tree(g,back_inserter(spanning_tree));

vector<graph_traits<Graph>::vector_descriptor>p(no_v);

prim_minimum_spanning_tree(g,0,&p[0],distancemap,weightMap,indexMap,default_dijkstra_visitor());



w=0;

for(vector<graph_traits<Graph>::edge_descriptor>::iterator eb=spanning_tree.begin();eb!=spanning_tree.end();++eb) //spanning tree weight
{
w=w+weightM[*eb];
}

arr_w[m]=w;
d=0;

graph_traits<Graph>::vertex_iterator vb,ve;

for(tie(vb,ve)=vertices(g),.

arr_d[m]=d;
m++;
}

for( i=0;i<test;i++)
{
cout<<arr_w[i]<<endl;
}

return 0;
}

ノード 1 2 3 4 を持つスパニング ツリーがある場合、スパニング ツリーで 1 2 3 4 からの最長距離を見つける必要があります (最長距離は、1 つだけでなく多くのエッジで構成できます)。

4

1 に答える 1

0

これを行うための正確なコードは提供しませんが、これを行う方法とアイデアを提供します。

まず、MST(Minimum Spanning Tree)の結果をツリーと呼びます。定義を考えてみてください。これは、すべてのノードから他のすべてのノードへのパスが存在し、サイクルがないグラフであると言えます。あるいは、与えられたグラフは、すべての u と v に対して頂点 u から v へのパスが 1 つだけ存在する場合、ツリーであると言うことができます。

定義によれば、次のように定義できます

function DFS_Farthest (Vertex u, Vertices P)
begin
    define farthest is 0
    define P0 as empty set
    add u to P

    foreach v from neighbours of u and v is not in P do
    begin
        ( len, Ps ) = DFS_Farthest(v, P)
        if L(u, v) + len > farthest then
        begin
            P0 is Ps union P
            farthest is len + L(u, v)
        end
    end

    return (farthest, P0)
end

次に、グラフ呼び出しですべての頂点 v を取得するとDFS_Farthest(v, empty set)、(最も遠い、P) が得られます。ここで、最も遠いノードの距離は最も遠く、P は v から最も遠い頂点までのパスを再構築できる頂点のセットです。

それでは、それが何をしているのかを説明しましょう。まずはサイン。最初のパラメーターは、知りたい頂点から最も遠いものです。2 番目のパラメータは、禁止された頂点のセットです。そのため、「ねえ、v から最も遠い頂点までの最長パスを教えてください。P からの頂点がそのパスに含まれないようにします」と表示されます。

次にforeachこんなものがあります。そこで、すでに P にある頂点を訪問せずに、現在の頂点から最も遠い頂点を探しています (現在の頂点は既にそこにあります)。より長いパスを見つけた場合、現在は と ではありませfarthestんP0。L(u, v)辺 {u, v} の長さであることに注意してください。

最後に、それらの長さと禁止された頂点を返します (これは、最も遠い頂点へのパスです)。

これは単純な DFS (深さ優先探索) アルゴリズムであり、既に訪れた頂点を記憶しています。

次に、時間の複雑さについてです。O(1) で特定の頂点の近傍を取得できるとします (データ構造によって異なります)。関数はすべての頂点を 1 回だけ訪れます。したがって、少なくとも O(N) です。すべての頂点から最も遠い頂点を知るには、すべての頂点に対してこの関数を呼び出す必要があります。これにより、問題のこのソリューションの時間の複雑さが少なくとも O(n^2) になります。

私の推測では、動的計画法を使用するとより良い解決策が得られる可能性がありますが、これは単なる推測です。一般に、グラフ内の最長パスを見つけることは NP 困難な問題です。これにより、大幅に優れた解決策がないのではないかと疑われます。しかし、それは別の推測です。

于 2013-10-22T18:13:29.907 に答える