Générer un nombre de bords entre deux nœuds

Question

J'ai généré cet arbre couvrant minimum en utilisant l'algorithme de Kruskal et j'ai du mal à générer des chemins entre deux nœuds. Quelqu'un peut-il m'aider avec Pseudocode? J'ai essayé d'utiliser la liste d'adjacence et la matrice Adjaceny

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
----------------------------------------------------

Answer 1

Si vous voulez juste un chemin entre deux nœuds, un Étendue de la première recherche ferait, et générerait le chemin le plus court (car c'est un arbre couvrant minimum).

Answer 2

Les arbres couvrant, par définition, n'ont pas de cycles (ou de boucles), donc au plus vous ne pouvez avoir qu'un seul chemin (c'est-à-dire pas des "chemins", pluriel) entre deux nœuds.

Peut-être que je ne comprends pas la question. Essayez-vous de trouver comment deux nœuds donnés sont connectés dans votre arbre?

Si c'est le cas, cela me semble être la force brute la plus simple à ce sujet, où vous découvririez juste à partir d'un point le long de ses bords possibles, peut-être en poussant et en faisant sauter des possibilités d'une pile, serait le temps d'exécution du pire-cas (bords), qui serait trivial par rapport à l'algorithme de Kruskal. Avez-vous besoin de quelque chose de plus rapide?