Arêtes de l'arbre
Longueur totale
Arêtes examinées

  • Actuel
  • Dans l'arbre
  • Voisin de l'arbre
  • Meilleure arête jusqu'ici
  • Fermerait un cycle

En savoir plus sur les arbres couvrants minimaux

Arbre couvrant minimal

Vous voulez relier chaque ville par un câble, chaque maison par des conduites d'eau ou chaque ordinateur d'un réseau, avec le moins de matériel possible. La réponse est un arbre couvrant minimal : l'ensemble d'arêtes qui relie tous les nœuds avec la plus petite longueur totale. Choisissez l'algorithme de Kruskal ou de Prim et avancez pas à pas pour voir l'arbre grandir, en ajoutant à chaque fois la plus courte arête permise. Appuyez sur Lecture pour voir l'arbre grandir, ou sur Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où. Choisissez l'algorithme : Kruskal essaie les arêtes de la plus courte à la plus longue, Prim fait grandir un seul arbre depuis le départ ; cliquez sur un nœud pour en faire le départ de Prim. Le nombre sur chaque arête est sa longueur. Sous le graphe se trouve la liste des arêtes encore à essayer, ou les nœuds en attente avec la longueur de leur meilleure arête vers l'arbre. Nouveau graphe crée un autre graphe ; choisissez son nombre de nœuds et d'arêtes. Quand le plateau est sélectionné, les flèches avancent ou reculent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.

Comment ça marche

  1. Choisissez l'algorithme de Kruskal ou de Prim. Pour Prim, cliquez sur un nœud pour en faire le départ.
  2. Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où.
  3. Observez les arêtes rejoindre l'arbre et la longueur totale augmenter. Nouveau graphe crée un autre graphe à essayer.

Algorithme de Kruskal

Triez toutes les arêtes de la plus courte à la plus longue et essayez-les dans cet ordre. Si une arête relie deux morceaux pas encore reliés, elle entre dans l'arbre. Si ses deux extrémités sont déjà reliées par l'arbre, elle fermerait un cycle, donc on la passe. On s'arrête quand l'arbre a une arête de moins qu'il n'y a de nœuds. Pour savoir vite si deux nœuds sont déjà reliés, l'algorithme de Kruskal garde les morceaux dans une structure union-find.

Algorithme de Prim

Commencez par un arbre d'un seul nœud. Chaque nœud hors de l'arbre retient sa plus courte arête vers l'arbre. Ajoutez à chaque fois le nœud dont l'arête est la plus courte, avec cette arête, et examinez ses arêtes : l'une d'elles peut donner à un voisin un accès plus court à l'arbre. L'algorithme de Prim ressemble à l'algorithme de Dijkstra, mais il compare des arêtes seules, pas des distances entières depuis le départ. Les deux algorithmes finissent toujours avec la même longueur totale.

Questions fréquemment posées

Qu'est-ce qu'un arbre couvrant minimal ?

Pour un graphe connexe dont les arêtes ont des longueurs, un arbre couvrant est un ensemble d'arêtes qui relie tous les nœuds sans aucun cycle ; avec n nœuds, il a toujours n − 1 arêtes. Un arbre couvrant minimal est un arbre couvrant dont la longueur totale est la plus petite possible.

Quelle est la différence entre l'algorithme de Kruskal et celui de Prim ?

L'algorithme de Kruskal parcourt les arêtes de tout le graphe de la plus courte à la plus longue et réunit des morceaux séparés en un seul arbre. L'algorithme de Prim fait grandir un seul arbre depuis un départ, en ajoutant toujours la plus courte arête qui en sort. Les deux sont gloutons et trouvent un arbre de même longueur totale ; Kruskal convient aux graphes creux, Prim aux graphes denses.

L'arbre couvrant minimal est-il unique ?

Quand toutes les longueurs d'arêtes sont différentes, oui. Quand certaines sont égales, plusieurs arbres peuvent avoir le même plus petit total, et les algorithmes peuvent en choisir de différents selon leur façon de départager les égalités.

Un arbre couvrant minimal donne-t-il les plus courts chemins ?

Non. L'arbre couvrant minimal garde petite la longueur totale de toutes les arêtes, mais le chemin entre deux nœuds dans l'arbre peut être bien plus long que leur plus court chemin. Pour les plus courts chemins, utilisez l'algorithme de Dijkstra.

Mon graphe est-il envoyé quelque part ?

Non. Le graphe est créé et l'arbre construit dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur