找到从节点到离它最远的节点的距离 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

然后，您将在图调用DFS_Farthest(v, empty set)中的每个顶点 v 中为您提供（最远的 P），其中最远是最远节点的距离，P 是一组顶点，您可以从中重建从 v 到最远顶点的路径。

所以现在来描述一下它在做什么。首先是签名。第一个参数是你想知道最远的顶点。第二个参数是一组禁止的顶点。所以它说"嘿，给我从 v 到最远顶点的最长路径，这样 P 的顶点就不在那条路径上"。

接下来是foreach的事情。在那里，您正在寻找距离当前顶点最远的顶点，而无需访问 P 中已有的顶点（当前顶点已经存在）。当你找到更长的路径时，目前发现不是它farthest和P0。请注意，L(u, v)是边 {u， v} 的长度。

最后，您将返回这些长度和禁止的顶点（这是通往最远顶点的路径）。

这只是简单的DFS（深度优先搜索）算法，您可以在其中记住已经访问过的顶点。

现在关于时间复杂度。假设您可以在 O（1） 中获取给定顶点的邻居（取决于您拥有的数据结构）。函数只访问每个顶点一次。所以它至少是O（N）。要知道距离每个顶点最远的顶点，您必须为每个顶点调用此函数。这使您的问题解决方案的时间复杂度至少为 O（n^2）。

我的猜测是，使用动态编程可能会完成更好的解决方案，但这只是一个猜测。通常，在图中查找最长路径是NP难题。这让我怀疑可能没有更好的解决方案。但这是另一种猜测。