從到一個最遠的一個節點查找距離它BOOST

Question

我需要從所有節點的距離，它鰭節點最遠的最小生成樹。到目前爲止，我已經完成了這項工作，但我無法找到距離節點最遠的距離。

#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在生成樹最長的距離（和最長的距離可以包括許多邊不僅之一）的生成樹。

Answer 1

我不會給你確切的代碼是如何做到這一點，但我給你和想法如何做到這一點。

首先，MST（最小生成樹）的結果就是所謂的樹。想想定義。可以說，這是一個從每個節點到每個其他節點都存在路徑並且沒有周期的圖。或者你可以說，鑑於圖是樹當且僅當從頂點u恰好存在一條路徑到v爲每一個u和v。

根據定義，你可以定義以下

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到最遠頂點的路徑。

現在來描述它在做什麼。首先簽名。第一個參數來自你想知道最遠的那個頂點。第二個參數是一組禁止的頂點。所以它說：「嘿，給我從v到最遠頂點的最長路徑，這樣來自P的頂點不在那條路徑上」。

接下來是這個foreach事情。在這裏，您正在尋找當前頂點的最遠頂點，而無需訪問P中已有的頂點（當前頂點已經存在）。當你找到更長的路徑時，目前發現它不是farthest和P0。請注意，L(u, v)是邊{u，v}的長度。

在最後你會回來的長度，並禁止頂點（這是路徑最遠的頂點）。

在這裏，你還記得已經訪問過的頂點只是簡單的DFS（深度優先搜索）算法。

現在關於時間複雜度。假設你可以得到O（1）中給定頂點的鄰居（取決於你擁有的數據結構）。函數精確訪問每個頂點一次。所以它至少是O（N）。要知道每個頂點的最遠頂點，您必須爲每個頂點調用此函數。這給你的問題解決方案的時間複雜度至少爲O（n^2）。

我的猜測是使用動態編程可以完成更好的解決方案，但這只是一個猜測。通常在圖中找到最長的路徑是NP難題。這讓我感到懷疑，可能沒有任何更好的解決方案。但這是另一個猜測。