minimum spanning tree tutorial
Ce didacticiel C ++ explique ce qu'est un Spanning Tree minimum (MST) avec les algorithmes de Prim et Kruskal pour rechercher MST dans un graphique et ses applications:
Un Spanning Tree peut être défini comme un sous-ensemble d'un graphe, qui se compose de tous les sommets couvrant le minimum d'arêtes possibles et n'a pas de cycle. Le Spanning Tree ne peut pas être déconnecté.
Chaque graphe connecté et non orienté a au moins un arbre couvrant. Un graphe déconnecté n'a pas d'arborescence couvrant car il n'est pas possible d'inclure tous les sommets.
=> Voir ici pour explorer la liste complète des didacticiels C ++.
Ce que vous apprendrez:
Spanning Tree en C ++
Considérez le graphique connecté suivant.
Comme indiqué ci-dessus, pour le graphe connecté donné contenant 3 sommets, nous avons trois arbres couvrant. En général, si N est le nombre de nœuds dans un graphe, alors un graphe connecté complet a au maximum NN-2nombre d'arbres couvrant. Ainsi dans le graphique ci-dessus N = 3, il a donc 3(3-2)= 3 arbres couvrant.
Certaines des propriétés de l'arbre couvrant sont répertoriées ci-dessous:
- Un graphe connecté peut avoir plus d'un arbre couvrant.
- Tous les arbres couvrant dans un graphique ont le même nombre de nœuds et d'arêtes.
- Si nous supprimons un bord de l'arbre couvrant, il deviendra minimalement connecté et rendra le graphique déconnecté.
- D'autre part, l'ajout d'un bord à l'arbre couvrant le rendra au maximum acyclique créant ainsi une boucle.
- Un Spanning Tree n'a pas de boucle ou de cycle.
Qu'est-ce qu'un arbre couvrant minimum (MST)
Un arbre couvrant minimum est celui qui contient le moins de poids parmi tous les autres arbres couvrant d'un graphe pondéré connecté. Il peut y avoir plus d'un arbre couvrant minimum pour un graphique.
Il existe deux algorithmes les plus courants qui sont utilisés pour trouver l'arbre couvrant minimum dans un graphique.
Ils incluent:
- Algorithme de Kruskal
- Algorithme de Prim
Parlons de ces deux algorithmes!
Algorithme de Kruskal
L’algorithme de Kruskal est un algorithme permettant de trouver le MST dans un graphe connecté.
L’algorithme de Kruskal trouve un sous-ensemble d’un graphe G tel que:
- Il forme un arbre avec chaque sommet en lui.
- La somme des poids est le minimum parmi tous les arbres couvrant qui peuvent être formés à partir de ce graphique.
La séquence d’étapes de l’algorithme de Kruskal est la suivante:
- Triez d'abord tous les bords du poids le plus faible au plus élevé.
- Prenez le bord avec le poids le plus bas et ajoutez-le à l'arbre couvrant. Si le cycle est créé, jetez le bord.
- Continuez à ajouter des arêtes comme à l'étape 1 jusqu'à ce que tous les sommets soient pris en compte.
Pseudocode pour l'algorithme de Kruskal
Le pseudo-code de l'algorithme de Kruskal est donné ci-dessous
Voyons maintenant l'illustration de l'algorithme de Kruskal.
Maintenant, nous choisissons le bord avec le moins de poids qui est 2-4.
Ensuite, choisissez le prochain bord le plus court 2-3.
Ensuite, nous choisissons le bord suivant avec le bord le plus court et cela ne crée pas de cycle, c'est-à-dire 0-3
différence entre le qa et le qc dans les tests de logiciels
L’étape suivante consiste à choisir le bord le plus court pour qu’il ne forme pas de cycle. C'est 0-1.
Comme nous pouvons le voir, nous avons couvert tous les sommets et nous avons ici un arbre couvrant avec un coût minimum.
Ensuite, nous implémenterons l'algorithme de Kruskal en utilisant C ++.
#include #include #include using namespace std; #define graph_edge pair class Graph { private: int V; // number of nodes in graph vector> G; // vector for graph vector> T; // vector for mst int *parent; public: Graph(int V); void AddEdge(int u, int v, int wt); int find_set(int i); void union_set(int u, int v); void kruskal_algorithm(); void display_mst(); }; Graph::Graph(int V) { parent = new int(V); for (int i = 0; i Production:
L'arbre couvrant minimum (MST) selon l'algorithme de Kruskal:
Bord: poids
2 à 4: 1
2 à 3: 2
0 à 1: 3
0 à 3: 3
Notez que nous avons utilisé le même exemple de graphique dans le programme que celui que nous avons utilisé dans l'illustration de l'algorithme de Kruskal ci-dessus. Dans cette implémentation, nous utilisons deux vecteurs; un pour stocker le graphique et un autre pour stocker l'arbre couvrant minimum. Nous trouvons récursivement les arêtes avec le moins de poids et les ajoutons au vecteur MST jusqu'à ce que tous les sommets soient couverts.
Algorithme de Prim
L’algorithme de Prim est encore un autre algorithme pour trouver le minimum couvrant l’arbre d’un graphe. Contrairement à l’algorithme de Kruskal qui commence par des arêtes de graphe, l’algorithme de Prim commence par un sommet. Nous commençons avec un sommet et continuons d'ajouter des arêtes avec le moins de poids jusqu'à ce que tous les sommets soient couverts.
La séquence d’étapes de l’algorithme de Prim est la suivante:
- Choisissez un sommet aléatoire comme sommet de départ et initialisez un arbre couvrant minimum.
- Trouvez les arêtes qui se connectent à d'autres sommets. Trouvez l'arête avec un poids minimum et ajoutez-la à l'arbre couvrant.
- Répétez l'étape 2 jusqu'à ce que l'arbre couvrant soit obtenu.
Pseudocode pour l'algorithme de Prim
Voyons maintenant une illustration de l'algorithme de Prim.
Pour cela, nous utilisons le même exemple de graphique que nous avons utilisé dans l'illustration de l'algorithme de Kruskal.
Choisissons le nœud 2 comme sommet aléatoire.
Ensuite, nous sélectionnons l'arête avec le moins de poids parmi 2. Nous choisissons l'arête 2-4.
Ensuite, nous choisissons un autre sommet qui n'est pas encore dans l'arbre couvrant. Nous choisissons le bord 2-3.
Maintenant, sélectionnons une arête avec le moins de poids parmi les sommets ci-dessus. Nous avons le bord 3-0 qui a le moins de poids.
Ensuite, nous choisissons une arête avec le moins de poids à partir du sommet 0. C'est l'arête 0-1.
À partir de la figure ci-dessus, nous voyons que nous avons maintenant couvert tous les sommets du graphe et obtenu un arbre couvrant complet avec un coût minimum.
Maintenant, implémentons l'algorithme de Prim en C ++.
Notez que dans ce programme également, nous avons utilisé l'exemple de graphique ci-dessus comme entrée afin de pouvoir comparer la sortie donnée par le programme avec l'illustration.
Le programme est donné ci-dessous:
#include #include using namespace std; #define INF 9999 // graph contains 5 vertices #define V 5 // an array G that stores adjacency matrix for input graph int G(V)(V) = { {0, 3, 0, 3, 0}, {3, 0, 0, 0, 4}, {0, 0, 0, 2, 1}, {3, 3, 2, 0, 0}, {0, 4, 1, 0, 0}}; int main () { int num_edge; // number of edge // mst_vertex - array to track vertices selected for spanning tree int mst_vertex(V); // set selected false initially memset (mst_vertex, false, sizeof (mst_vertex)); // set number of edge to 0 num_edge = 0; //let 0th vertex be the first to be selected mst_vertex(0) = true; int x; // row int y; // col // print details of MST cout<<'The Minimum Spanning Tree as per Prim's Algorithm:'< G(i)(j)) { min = G(i)(j); x = i; y = j; } } } } } cout << x << ' - ' << y << ' : ' << G(x)(y); cout << endl; mst_vertex(y) = true; num_edge++; } return 0; } Production:
L'arbre couvrant minimum selon l'algorithme de Prim:
Bord: poids
0 à 1: 3
0 à 3: 3
3 - 2: 2
2 à 4: 1
Applications de Spanning Tree
Certaines des applications des arbres couvrant minimum sont les suivantes:
# 1) Configuration du réseau de communication: Lorsque nous voulons mettre en place un réseau de communication utilisant des liaisons de communication, le coût de mise en place des liaisons de communication entre deux points est mieux déterminé à l'aide d'un MST.
# 2) Analyse de cluster: Il peut être utilisé pour résoudre le problème de K-clustering en trouvant un arbre couvrant minimum et en supprimant les arêtes les plus chères k-1.
# 3) Disposition des réseaux routiers / ferroviaires: Lorsque nous installons divers réseaux routiers ou ferroviaires entre ou à l'intérieur des villes, le coût du projet est un facteur très important. Nous pouvons trouver le meilleur chemin avec un coût minimum en utilisant des arbres couvrant minimum.
# 4) Planification des installations de logement: Des installations telles que l'électricité, l'eau, les eaux usées, etc. devant être fournies à un certain nombre de maisons doivent également être à un coût optimal et cela se fait à l'aide d'un MST.
# 5) Résolution du problème du voyageur de commerce: Nous pouvons utiliser un MST pour résoudre le problème du voyageur de commerce qui nécessite de visiter chaque point au moins une fois.
Conclusion
L'arbre couvrant minimum est le sous-ensemble du graphe g et ce sous-ensemble a tous les sommets du graphe et le coût total des arêtes reliant les sommets est minimum.
Nous avons discuté de deux algorithmes, à savoir celui de Kruskal et celui de Prim, pour trouver l’arbre couvrant minimum à partir du graphique. Les applications du spanning tree ont également été expliquées ici dans ce tutoriel.
=> Découvrez les meilleurs didacticiels de formation C ++ ici.
lecture recommandée
- Tutoriel de réflexion Java avec des exemples
- B Tree et B + Tree Structure de données en C ++
- Tutoriel Python DateTime avec des exemples
- Tutoriel Bugzilla: Tutoriel pratique de l'outil de gestion des défauts
- Structure de données d'arbre binaire en C ++
- 20+ Tutoriel MongoDB pour les débutants: Cours MongoDB gratuit
- Tutoriel de partage MongoDB avec exemple
- Tutoriel MongoDB Create Database
