Algorithme prim

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.

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 Prim. L'algorithme de Kruskal sera discuté dans le prochain article.

Algorithme de Prim:

L'algorithme de Prim est utilisé pour trouver l'arbre couvrant minimum d'un graphique. L'algorithme du Prim commence à partir de n'importe quel nœud, puis ajoute tout nœud adjacent dont le poids est le minimum, et ce processus se poursuit jusqu'à ce que tous les nœuds des graphiques soient visités. Lors de la création de l'arbre couvrant minimum d'un graphique, nous devons également ne pas créer de cycles car les cycles ne devraient pas être dans l'arbre à courir minimum.

Étapes de l'algorithme de Prim:

L'algorithme du prim utilise l'approche gourmand pour l'arbre couvrant minimum. Nous devons choisir n'importe quel sommet du graphique, puis choisir le prochain sommet d'adjacence dont le poids est moindre, et nous continuons ce processus jusqu'à ce que nous ne faisons pas connecter les nœuds de graphe entier.

Étape 1: Choisissez n'importe quel sommet source dans le graphique.

Étape 2: Trouvez le bord de poids minimum qui est adjacent à la source, puis connectez-le à l'arbre couvrant.

Étape 3: Répétez l'étape 2 jusqu'à ce que tous les nœuds ne soient pas ajoutés dans l'arbre de couture minimum.

Exemple :

Ci-dessous est un exemple pour rechercher un arbre couvrant minimum en utilisant l'algorithme de Prim.

1. Nous choisissons n'importe quel nœud aléatoire à partir du graphique G et l'ajoutons au MST (arborescence couvante) minimale). Nous sélectionnons ici nœud 0.

2. Maintenant, nous sélectionnons ce bord qui est adjacent au nœud source (0) mais avec le plus petit poids, puis ajoutant ce nœud de poids le plus petit à l'arbre couvrant minimum.

3. Maintenant, nous sélectionnons ce bord qui est adjacent au nœud source (0 ou 1) mais avec le plus petit poids, puis ajoutez ce nœud de poids le plus petit à l'arbre couvrant minimum.

4. Maintenant, nous sélectionnons ce bord qui est adjacent au nœud source (0, 1 ou 3) mais avec le plus petit poids, puis ajoutez ce nœud de poids le plus petit à l'arbre couvrant minimum.

5. Maintenant, nous sélectionnons ce bord qui est adjacent au nœud source (0, 1, 3 ou 4) mais avec le plus petit poids, puis ajoutant ce nœud de poids le plus petit à l'arbre à entendre minimum.

6. Maintenant, nous sélectionnons ce bord qui est adjacent au nœud source (0, 1, 3, 4 ou 6) mais avec le plus petit poids, puis ajoutant ce nœud de poids le plus petit à l'arbre de transfert minimum.

7. Maintenant, nous sélectionnons ce bord qui est adjacent au nœud source (0, 1, 3, 4, 6 ou 2) mais avec le plus petit poids, puis ajoutant ce nœud de poids le plus petit à l'arbre couvrant minimum.

Ci-dessus est notre MST final (arbre couvrant minimum), et le coût total est de 6.

Programme MST (Minimum Spanning Tree) de C ++ Prim:

#inclure
#inclure
#inclure
#inclure
#inclure
Typedef std :: paire Sii;
Typedef STD :: Vector Ssii;
int primsmst (int sourcenode, std :: vector & graphique)
// Cette file d'attente stockera les détails de chaque nœud
// avec leur valeur de poids.
std :: priority_queue, std :: plus grand> k;
k.push (std :: make_pair (0, sourceNode));
bool nœuds radiés [graphique.taille()];
MEMSET (NODESADDED, FAUX, SIZEOF (BOOL) * Graphique.taille());
int mst_tree_cost = 0;
alors que (!k.vide())
// Nous sélectionnons ici le nœud qui a un coût minimum
Sii itemNode;
itemNode = k.haut();
k.populaire();
int node = itemNode.deuxième;
int Cost = itemNode.d'abord;
// Nous vérifions ici si aucun nœud n'a été ajouté au MST,
// puis ajoutant ce nœud.
si (!NODESADDED [NODE])
MST_TREE_COST + = COST;
NODESADDED [NODE] = TRUE;
// itération sur les nœuds de négtibour qui ont été récemment pris
// hors de la file d'attente prioritaire.
// et ajouté au MST qui n'est pas encore ajouté
pour (auto & pair_node_cost: graphique [node])
int adjency_node = pair_node_cost.deuxième;
if (nœuds aded [adjency_node] == false)
k.push (pair_node_cost);




return mst_tree_cost;

int main()
// les détails du graphique avec le nœud coûts et de direction.
Ssii fromNode_0_in_graph_1 = 1,1, 2,2, 1,3,
1,4, 2,5, 1,6;
Ssii fromNode_1_in_graph_1 = 1,0, 2,2, 2,6;
Ssii fromNode_2_in_graph_1 = 2,0, 2,1, 1,3;
Ssii fromNode_3_in_graph_1 = 1,0, 1,2, 2,4;
Ssii fromNode_4_in_graph_1 = 1,0, 2,3, 2,5;
Ssii fromNode_5_in_graph_1 = 2,0, 2,4, 1,6;
Ssii fromNode_6_in_graph_1 = 1,0, 2,2, 1,5;
int num_of_nodes = 7; // Total des nœuds (0 à 6)
STD :: Vector primsgraph;
graphique.redimensit (num_of_nodes);
primsgraph [0] = fromNode_0_in_graph_1;
primsgraph [1] = fromNode_1_in_graph_1;
primsgraph [2] = fromNode_2_in_graph_1;
primsgraph [3] = fromNode_3_in_graph_1;
primsgraph [4] = fromNode_4_in_graph_1;
primsgraph [5] = fromNode_5_in_graph_1;
primsgraph [6] = fromNode_6_in_graph_1;
// Comme nous le savons déjà, nous devons choisir le sommet source,
// Nous commençons donc du nœud Vertex 0.
std :: cout << "Total cost of minimum spanning tree after Prim's algorithm : "
"" << PrimsMST(0, primsgraph) << std :: endl;
retour 0;

Sortir:

Coût total de l'arbre de couture minimum après l'algorithme de Prim: 6

Complexité temporelle de l'algorithme MST de Prim:

1. Le temps total nécessaire pour traiter et sélectionner le nœud de file d'attente de priorité spécifique qui n'a pas encore été ajouté au MST est logv.Mais comme cela fonctionne pour chaque sommet, la complexité du temps totale est V (logv).

2. Le graphique n'est pas dirigé, et les bords totaux seront 2E. Comme nous devons pousser les nœuds dans la file d'attente prioritaire, il faudra un journal de temps total (V). Cependant, comme nous avons un total de 2e bords, notre opération de poussée totale sera 2E (log (v)).

3. La complexité totale après l'opération 1 et 2 est O ((e + v) log (v)).

Conclusion:

Nous avons étudié l'arbre couvrant minimum du prim, 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 du Prim est simple à saisir et à implémenter dans une application réelle.L'algorithme de Prim est très utile dans les applications réelles, par exemple, reliant les voies ferrées à l'ensemble sur les villes. C'est donc juste un seul exemple, mais son application est énorme, nous devons donc comprendre cet algorithme.