Discussion :

[vdumont]

Bonjour, j'essaie de déterminer si une arête E fait parti d'un arbre de recouvrement minimal d'un graph G. Le poids des arêtes de G sont tous distincts, il y a donc 1 seul arbre de recouvrement minimal pour le graph.

Mon problème est que j'essaie de respecter une compléxité de O(m+n) ou m est le nombre d'arêtes et n le nombre de noeuds.


J'avais l'intention de simplement modifier Prim de sorte que si l'arête minimal choisie est égale à E alors retourner VRAI mais l'algorithme de Prim pour trouver le MST est de O(|m|log|n|) à lui seul et donc brise à lui seul la complexité désirée.

Est-ce que vous voyez une retouche (sans dire la réponse exacte!) que je pourrais faire à Prim pour avoir la compléxité désirée ?

Merci

[PRomu@ld]

j'essaie de déterminer si une arête E fait parti d'un arbre de recouvrement minimal d'un graph G

Pour savoir si elle fait parti de l'un des arbres de recouvrement de ton graphe, il faut savoir identifier un arbre de recouvrement, en général, ça va passer par la construction de cet arbre (pour pouvoir l'identifier), avec les algos classiques, Kruskall ou Prim, la construction est en (n log n), donc ta complexité va être difficile à atteindre.

Ou alors tu connais autre chose dans ton arbre couvrant.