查找从一个节点到距离它最远的节点的距离
我需要在最小生成树中找到从所有节点到距离最远的节点的距离。到目前为止，我已经做到了这一点，但我没有找到到节点的最长距离的线索。
#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
Stack Overflow用户
发布于 2013-10-23 02:13:30
我不会给你确切的代码如何做到这一点，但我会给你和想法如何做到这一点。
首先，最小生成树( 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-hard问题。这让我怀疑可能没有任何明显更好的解决方案。但这是另一种猜测。
https://stackoverflow.com/questions/19482176
复制相似问题
腾讯云开发者
