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
