Algorithme de Kruskal

Arbre couvrant minimum

Un graphique qui n'a pas de directions est appelé un graphique non dirigé. Chaque graphique doit avoir un chemin d'un nœud à un autre nœud. Un arbre couvrant est également un graphique connecté non dirigé où tous les nœuds du graphique sont présents avec des bords minimaux. Si un arbre couvrant n'a pas tous les nœuds du graphique, alors nous ne pouvons pas dire que c'est un arbre couvrant. Le poids total de l'arbre couvrant sera inférieur au poids d'origine du graphique car nous l'avons connecté à travers les bords de poids minimum. L'arbre couvrant n'a pas non plus de cycle. Tout graphique a plus d'un arbre couvrant, mais un seul d'entre eux sera unique. Nous l'appelons un arbre couvrant minimal car nous essayons de créer un graphique complet avec tous les nœuds tout en gardant le poids bas.

Comprenons l'arbre couvrant minimum avec un exemple. Ainsi, comme nous le savons, l'arbre couvrant minimum fait partie du graphique mais avec moins de coût. Donc ce scénario peut être illustré par un exemple. Supposons que nous ayons un graphique comme celui-ci.

Le graphique ci-dessus peut être organisé de différentes manières afin que le cycle du graphique soit supprimé, sinon ce ne sera pas un MST (arbre de couture minimum). Nous allons donc supprimer le cycle du graphique et compter le coût total du graphique. Nous avons quatre nœuds, ou sommets (A, B, C et D).

Cas 1:

Après avoir retiré le cycle du graphique, le coût du graphique MST ci-dessus (arbre couvrant minimum) est de 56.

Cas -2:

Après avoir retiré le cycle du graphique, le coût du graphique MST ci-dessus (arbre couvrant minimum) est de 53.

Cas - 3:

Après avoir retiré le cycle du graphique, le coût du graphique MST ci-dessus (arbre couvrant minimum) est de 41.

Nous pouvons voir que le dernier graphique du coût total de Case-3 est beaucoup plus faible par rapport aux deux autres graphiques. Ce graphique est donc notre final MST (arbre couvrant minimum) pour le graphique d'origine. Le motif des algorithmes du Prim ou de Kruskal est de trouver le coût du graphique aussi bas que possible. C'est donc notre motif dans cet article pour expliquer ce MST.

Nous pouvons dessiner un arbre couvrant à l'aide des deux méthodes suivantes:

1. L'algorithme de Kruskal
2. Algorithme de Prim

Dans cet article, nous allons discuter de l'algorithme de Kruskal. L'algorithme de Prim sera discuté dans le prochain article.

L'algorithme de Kruskal

L'algorithme de Kruskal est très facile à mettre en œuvre par rapport à l'algorithme de Prim car nous n'avons pas à nous soucier des sommets de la contiguïté dans cet algorithme. Dans cet algorithme, l'algorithme de Kruskal commence à partir de tous les sommets du graphique. Nous choisissons le vertige de bord de poids minimum et commençons à créer l'arbre couvrant minimum. Nous choisissons un autre bord avec le poids minimum et l'ajoutons à l'arbre couvrant minimum. Ce processus se poursuit jusqu'à ce que nous n'ajouons pas tous les nœuds graphiques d'origine. Une fois que tous les nœuds du graphique sont ajoutés à l'arbre couvrant minimum, l'algorithme s'arrêtera. Lors de la création de l'arbre couvrant minimum d'un graphique, nous devons également prendre soin de ce graphique, sans créer de cycles car les cycles ne devraient pas être dans l'arbre couvrant minimum.

Donc, si un nœud crée le cycle dans l'arbre couvrant minimum, nous choisissons l'autre nœud, même si le poids de ce nœud est supérieur au nœud précédent qui crée le cycle.

L'algorithme de Kruskal est différent de l'algorithme de Prim. L'algorithme de Prim, lors de la création d'un arbre couvrant minimum, commence à partir de n'importe quel nœud ou verti, puis ajoute un autre nœud ou verti uniquement à partir des nœuds d'adjacence. Mais l'algorithme de Kruskal ne se soucie pas du nœud d'adjacence et sélectionne toujours ce nœud qui a moins de poids, mais ce nœud ne doit pas créer un cycle dans l'arbre à courir minimum.

Étapes de l'algorithme de Kruskal:

Les étapes suivantes sont prises lors de l'écriture du code C ++ pour l'algorithme de Kruskal.

1. Nous créons un tableau pour stocker des groupes des nœuds ou des sommets du graphique.
2. Nous créons un autre tableau pour stocker les poids des bords graphiques.
3. Pour l'arbre couvrant, nous créons un nouveau tableau.
4. Nous organisons le tableau des bords en ordre croissant.
5. Nous répétons l'étape 6 jusqu'à ce que le tableau de poids de bord triés ne soit pas vide.
6. Nous comparons les deux groupes côte à côte. Dans ce cas, si un nœud d'un groupe ne correspond pas à l'autre nœud, nous ajoutons ce bord à l'arbre couvrant et l'ajoutons dans le même groupe.
7. Itérer à travers tous les bords de l'arbre couvrant pour déterminer son poids total.

Maintenant, nous implémenterons les étapes d'algorithme ci-dessus en utilisant un exemple. Nous avons le graphique ci-dessous, et nous découvrirons l'arbre couvrant minimum pour ce graphique.

Ainsi, selon l'algorithme, nous choisissons d'abord le plus petit bord de poids, qui est AB. Nous avons donc choisi ce bord et l'avons gardé dans le tableau d'arbres coupé. Le poids du bord ab est 9.

Maintenant, nous choisissons le plus petit bord le plus petit, CD et gardons ce bord dans le réseau d'arbres couvrant minimum. Le poids du bord du CD est 12.

Le prochain plus petit bord que nous avons eu était la Colombie-Britannique, que nous avons gardé dans le tableau. Le bord BC pondéré est de 17.

Notre algorithme s'arrêtera ici parce que nous avons tous les sommets d'un graphique, et nous avons notre arbre couvrant minimum. Le poids total de ce MST est 9 + 12 + 17 = 38.

Programme: Ce qui est un code C ++ pour l'algorithme de Kruskal.

#inclure
#inclure
#inclure
class edgegraph
public:
int nodestart;
int nodeend;
int wght;
Edgegraph ()
EdgeGraph (int node_1, int node_2, inthonométrage): Nodestart (Node_1),
nodeend (node_2), wght (poids)
;
bool compareedgeCost (const edgegraph a, const edgegraph b)
retourner un.wght < b.wght;

classe G
privé:
int num_of_nodes;
STD :: Vector EdgeGraphList;
STD :: Vector parentNode;
STD :: Vector RANKNODE;
public:
G()
G (int num_of_nodes)

this-> num_of_nodes = num_of_nodes;
norme parentale.redimensit (num_of_nodes);
notation.redimensit (num_of_nodes);

VOID ADDADGEGRAPH (Edgegraph E);
int findparentNode (nœud int);
vide kruskalmst_algo (vecteur std ::&);
void DisplayEdgeGraphs (STD :: Vector&);
;
void g :: AddgeGraph (edgegraph e)
EdgeGraphlist.push_back (e);

int g :: findparentNode (node ​​int)
if (nœud != parentNode [nœud])
parentNode [node] = findParentNode (parentNode [node]);
return parentNode [nœud];

void g :: DisplayEdgeGraphs (STD :: Vector& mst)
Int coût = 0;
std :: cout << "EdgeGraphs of MST : ";
pour (auto & e: mst)
std :: cout << "[" << e.nodeSTART << "-" << e.nodeEND
<< "](" << e.wght << ") ";
Coût + = E.wght;

std :: cout << "\n Kruskal MST Cost : " << cost << std :: endl;

// c'est la fonction algorithme principale de Kruskal qui recherche
// l'arbre couvrant minimum.
void g :: kruskalmst_algo (vecteur std ::& résultat)
pour (int i = 0; iparentNode [i] = i;
rankNode [i] = 0;

trier (edgegraphlist.begin (), edgegraphlist.fin(),
CompareEdgeCost);
pour (auto & e: edgegraphlist)
int root_1 = findparentNode (e.NODESTART);
int root_2 = findparentNode (e.nodeend);
if (root_1 != root_2)
résultat.push_back (e);
if (ranknode [root_1] < rankNode[root_2])
parentNode [root_1] = root_2;
rankNode [root_2] ++;
autre
parentNode [root_2] = root_1;
rankNode [root_1] ++;




int main()
int num_of_nodes = 6; // (0, 1, 2, 3, 4, 5)
Edgegraph E1 (0, 1, 4);
Edgegraph E2 (0, 2, 1);
Edgegraph E3 (0, 3, 5);
Edgegraph E4 (1, 3, 2);
Edgegraph E5 (1, 4, 3);
Edgegraph E6 (1, 5, 3);
Edgegraph E7 (2, 3, 2);
Edgegraph E8 (2, 4, 8);
Edgegraph E9 (3, 4, 1);
Edgegraph E10 (4, 5, 3);
G G1 (num_of_nodes);
G1.AddingGegraph (E1);
G1.AddingGegraph (E2);
G1.AddingGegraph (E3);
G1.AddingGegraph (E4);
G1.AddingGegraph (E5);
G1.AddingGegraph (E6);
G1.AddingGegraph (E7);
G1.AddingGegraph (E8);
G1.AddgeGraph (E9);
G1.AddingGegraph (E10);
STD :: Vector MST; // Cela stockera l'arbre couvrant minimum
G1.Kruskalmst_algo (MST);
G1.DisplayEdgeGraphs (MST);
retour 0;

Sortir:

EdgeGraphs de MST: [0-2] (1) [3-4] (1) [1-3] (2) [2-3] (2) [1-5] (3)
Kruskal MST Coût: 9

Conclusion:

Nous avons étudié l'arbre de couture minimum de Kruskal, qui est la première préférence de la plupart des gens lorsqu'ils doivent trouver le graphique MST d'un graphique. L'algorithme de Kruskal est simple à saisir et à mettre en œuvre dans une application du monde réel. Comme l'algorithme de Prim, l'algorithme de Kruskal est également très utile dans les applications réelles. Nous devons donc comprendre cet algorithme.