Algorithme de Kruskal
Fermé
melo96
Messages postés
23
Date d'inscription
mardi 2 août 2016
Statut
Membre
Dernière intervention
30 octobre 2017
-
Modifié par mamiemando le 1/03/2017 à 11:18
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 1 mars 2017 à 11:35
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 1 mars 2017 à 11:35
A voir également:
- Algorithme de Kruskal
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Algorithme somme de deux nombres - Forum Programmation
- Code ascii algorithme - Guide
- Algorithme excel - Forum VB / VBA
- Remplir une matrice algorithme - Forum Pascal
1 réponse
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
Modifié par mamiemando le 1/03/2017 à 11:44
Modifié par mamiemando le 1/03/2017 à 11:44
Bonjour,
En gros il faut faire ce qui est expliqué ici :
https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal#Pseudo-code
Explication détaillée :
Oublions Kruskal pour le moment et supposons qu'on cherche à construire un arbre en ajoutant progressivement des arêtes. Supposons que l'on a selectionné une arête. On se demande si on peut ajouter une arête (u,v) à cet arbre sans former de cycle. Pour cela il faut qu'une de ses extrémités soient dans l'arbre (pour que la structure reste connexe) et que l'autre ne soit pas dans l'arbre (pour ne pas former de cycle) (et u != v). Ainsi maintenir un ensemble qui contient les sommets déjà présents dans l'arbre permet de tester si une arête (u, v) peut être ajoutée. Il faut qu'elle vérifie le test :
Revenons à Kruskal. La difficulté supplémentaire, c'est qu'on construit progressivement plusieurs sous-arbre qu'on finit par regrouper. Le test précédent est donc trop strict car on ne pourra jamais recoller deux sous-arbres pour former l'arbre recherché. C'est là que la structure union find intervient.
On identifie chaque sous-arbre par une racine (donc dans un graphe non orienté, un nœud arbitraire du sous arbre). Chaque nœud du sous-arbre est associé à cette racine. La primitive
Il ne reste plus qu'à interdire la construction d'un arc si et seulement si il connecte deux nœuds du même sous-arbre, c'est-à-dire deux nœuds qui correspondent à une même racine, ce qui généralise le test que j'ai énoncé au début.
En effet :
- si u et v ne sont rattachés à aucune racine : on crée juste un nouveau sous arbre (dont la racine sera arbitrairement u ou v)
- si u ou bien v sont rattaché à un arbre t : on ne fait qu'ajouter une branche à un arc existant.
- si u et v sont rattachés à un arbre : si u et v sont rattaché à la même racine, et il faut interdire la construction ; sinon, comme par construction, l'arbre de t1 et t2 sont deux arbres disjoints, ce raccordement ne peut pas former de cycle.
Il reste un dernier point à régler. Quand on fusionne deux sous arbres t1 et t2, il faut alors faire en sorte que leurs nœuds soient rattaché à la même racine. Si on note r1 la racine de t1 et r2 celle de t2 soit on réassocie les nœuds de t2 à r1, soit ceux de t1 à r2. C'est le rôle de la primitive
Bonne chance
En gros il faut faire ce qui est expliqué ici :
https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal#Pseudo-code
Explication détaillée :
Oublions Kruskal pour le moment et supposons qu'on cherche à construire un arbre en ajoutant progressivement des arêtes. Supposons que l'on a selectionné une arête. On se demande si on peut ajouter une arête (u,v) à cet arbre sans former de cycle. Pour cela il faut qu'une de ses extrémités soient dans l'arbre (pour que la structure reste connexe) et que l'autre ne soit pas dans l'arbre (pour ne pas former de cycle) (et u != v). Ainsi maintenir un ensemble qui contient les sommets déjà présents dans l'arbre permet de tester si une arête (u, v) peut être ajoutée. Il faut qu'elle vérifie le test :
(u != v) and ((u in s and v not in s) or (u not in s and v in s)).
Revenons à Kruskal. La difficulté supplémentaire, c'est qu'on construit progressivement plusieurs sous-arbre qu'on finit par regrouper. Le test précédent est donc trop strict car on ne pourra jamais recoller deux sous-arbres pour former l'arbre recherché. C'est là que la structure union find intervient.
On identifie chaque sous-arbre par une racine (donc dans un graphe non orienté, un nœud arbitraire du sous arbre). Chaque nœud du sous-arbre est associé à cette racine. La primitive
findpermet de retrouver la racine associée à un nœud quand elle existe.
Il ne reste plus qu'à interdire la construction d'un arc si et seulement si il connecte deux nœuds du même sous-arbre, c'est-à-dire deux nœuds qui correspondent à une même racine, ce qui généralise le test que j'ai énoncé au début.
En effet :
- si u et v ne sont rattachés à aucune racine : on crée juste un nouveau sous arbre (dont la racine sera arbitrairement u ou v)
- si u ou bien v sont rattaché à un arbre t : on ne fait qu'ajouter une branche à un arc existant.
- si u et v sont rattachés à un arbre : si u et v sont rattaché à la même racine, et il faut interdire la construction ; sinon, comme par construction, l'arbre de t1 et t2 sont deux arbres disjoints, ce raccordement ne peut pas former de cycle.
Il reste un dernier point à régler. Quand on fusionne deux sous arbres t1 et t2, il faut alors faire en sorte que leurs nœuds soient rattaché à la même racine. Si on note r1 la racine de t1 et r2 celle de t2 soit on réassocie les nœuds de t2 à r1, soit ceux de t1 à r2. C'est le rôle de la primitive
union.
Bonne chance
