Algorithme de Kruskal

Graphe original
Questions
  1. Appliquer l'algorithme de Kruskal sur le graphe ci-contre pour obtenir un arbre couvrant minimum.
    Arbre couvrant minimum :
    Graphe résultat

    Étape 1

    On met toutes les arêtes dans une liste que l'on trie par ordre croissant et on crée un graphe résultat contenant l'ensemble des sommets.

    Graphe étape 1

    Liste des arêtes : EF(1), CF(3), AE(4), AD(8), DG(12), BF(15), EG(15), BG(16), BC(17), CE(19), AB(19), CG(23), FG(24), AF(25), CD(28), BD(28).


    Étape 2

    On ajoute l'arête EF au graphe résultat.

    Graphe étape 2

    Liste des arêtes : CF(3), AE(4), AD(8), DG(12), BF(15), EG(15), BG(16), BC(17), CE(19), AB(19), CG(23), FG(24), AF(25), CD(28), BD(28).


    Étape 3

    On ajoute l'arête CF au graphe résultat.

    Graphe étape 3

    Liste des arêtes : AE(4), AD(8), DG(12), BF(15), EG(15), BG(16), BC(17), CE(19), AB(19), CG(23), FG(24), AF(25), CD(28), BD(28).


    Étape 4

    On ajoute l'arête AE au graphe résultat.

    Graphe étape 4

    Liste des arêtes : AD(8), DG(12), BF(15), EG(15), BG(16), BC(17), CE(19), AB(19), CG(23), FG(24), AF(25), CD(28), BD(28).


    Étape 5

    On ajoute l'arête AD au graphe résultat.

    Graphe étape 5

    Liste des arêtes : DG(12), BF(15), EG(15), BG(16), BC(17), CE(19), AB(19), CG(23), FG(24), AF(25), CD(28), BD(28).


    Étape 6

    On ajoute l'arête DG au graphe résultat.

    Graphe étape 6

    Liste des arêtes : BF(15), EG(15), BG(16), BC(17), CE(19), AB(19), CG(23), FG(24), AF(25), CD(28), BD(28).


    Étape 7

    On ajoute l'arête BF au graphe résultat.

    Graphe étape 7

    Liste des arêtes : EG(15), BG(16), BC(17), CE(19), AB(19), CG(23), FG(24), AF(25), CD(28), BD(28).


    Étape 8

    On a ajouté 6 arêtes ; comme il y a 7 sommets, on a terminé.

Afficher les réponses
Lancer un exercice similaire avec les mêmes paramètres
Lancer un exercice similaire avec des paramètres différents
Lancer un exercice différent
Télécharger le graphe au format GraphVIZ