Discussion :

[Lucas Panny]

Bonjour,

Je parle des algorithmes de Prim et de Kruskal.
Je me demande si l'arbre de poids minimal issu d'un graphe est unique ou pas ?
L'arbre résultant de ces 2 algos est-il toujours le même ?

[Jean-Marc.Bourguet]

Je parle des algorithmes de Prim et de Kruskal.
Je me demande si l'arbre de poids minimal issu d'un graphe est unique ou pas?

Pas nécessairement.

L'arbre résultant de ces 2 algos est-il toujours le même ?

La description classique de ces deux algorithmes n'est pas déterministes (dans les deux il faut prendre un arc de poid minimum, s'il y en a plusieurs rien dans l'algo permet d'en choisir un plutôt qu'un autre). Parler de l'arbre résultant de chacun d'entre eux n'a pas de sens dans les cas où le MST n'est pas unique, et c'est justement dans ces cas que les arbres générés vont pouvoir être différent. S'il n'y a qu'un MST, les deux vont le trouver.

[Invité]

Bonjour,
Je confirme, s'il n'y a qu'une solution possible, Prim et Kruskal vont trouver la même. Ce qui diffère entre les 2 va être le temps pour trouver la solution car l'un dépend des noeuds et l'autre des lignes. Mais en général, le temps pour trouver la solution est quasi-identique.
En revanche si plusieurs solutions sont équivalentes, il y a des chances que tu trouves des solutions différentes.

[bruce-willis]

Bonjour,

Je me demandais en fait si le protocole réseau 802.1d ou Spanning tree n'est-il pas une autre application des algorithmes sur les arbres couvrants de poids minimal ?
Son principe est assez similaire : éliminer les boucles, recherche de chemin unique entre les ponts