Найти расстояние от узла до самого дальнего от него BOOST
Мне нужно вычислить расстояние от всех узлов до самого дальнего от него узла в минимальном остовном дереве. Я сделал это до сих пор, но у меня не было никакой подсказки, чтобы найти самое длинное расстояние от узла.
#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 в остовном дереве (и самое длинное расстояние может состоять из множества ребер, а не только одного).
Решение
Я не дам вам точный код, как это сделать, но я дам вам и идею, как это сделать.
Во-первых, результатом 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-сложной задачей. Это вызывает у меня подозрение, что у меня не может быть значительно лучшего решения. Но это другое предположение.
Другие решения
Других решений пока нет …