Gerar número de arestas entre dois nós
-
29-10-2019 - |
Pergunta
Eu gerei esta árvore de abrangência mínima usando o algoritmo de Kruskal e tenho dificuldade em gerar caminhos entre dois nós.Alguém pode me ajudar com pseudocódigo?Tentei usar a Lista de Adjacência e a Matriz de Adjacência
Loc1 | Loc2 | Distance
02 | 10 | 2.00 Km
05 | 07 | 5.39 Km
02 | 09 | 5.83 Km
04 | 05 | 5.83 Km
06 | 08 | 5.83 Km
03 | 09 | 7.07 Km
01 | 04 | 11.18 Km
07 | 09 | 11.18 Km
07 | 08 | 15.81 Km
Total Weight = 70.12 Km
----------------------------------------------------
Solução
Se você quiser apenas qualquer caminho entre dois nós, uma Primeira pesquisa ampla faria, egeraria o caminho mais curto (porque é uma árvore de abrangência mínima).
Outras dicas
Spanning trees, por definição, não têm ciclos (ou loops), então, no máximo, você pode ter apenas um caminho (ou seja, não "caminhos", plural) entre dois nós.
Talvez eu não esteja entendendo a pergunta.Você está tentando descobrir como dois nós dados estão conectados em sua árvore?
Nesse caso, parece-me a força bruta mais simples nisso, onde você apenas seguiria de um ponto ao longo de suas bordas possíveis, talvez empurrando e retirando possibilidades de uma pilha, seria o pior caso O (Bordas)tempo de execução, o que seria trivial em comparação com o algoritmo de Kruskal. Você precisa de algo mais rápido?