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 的最长距离（最长距离可以包含许多边，而不仅仅是一条边）。

4

1 回答 1

0

我不会给你确切的代码如何做到这一点，但我会给你和想法如何做到这一点。

首先，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

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

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

接下来就是这个foreach东西了。在那里，您正在寻找距当前顶点最远的顶点，而无需访问 P 中已经存在的顶点（当前顶点已经存在）。当您找到比当前更长的路径时，不会找到farthestand P0。注意L(u, v)是边 {u, v} 的长度。

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

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

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

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

于 2013-10-22T18:13:29.907 回答