Algoritma Pokok Spanning Minimum Kruskal - Algoritma Tamak dalam C++

Pokok rentang ialah subgraf graf tidak terarah yang menghubungkan semua bucu. Terdapat banyak pokok rentang dalam graf. Pokok rentang minimum (MST) pada setiap graf mempunyai berat yang sama atau lebih kecil daripada semua pokok rentang yang lain. Pemberat diberikan pada tepi pokok rentang, dan jumlahnya ialah berat yang diberikan pada setiap tepi. Oleh kerana V ialah bilangan bucu dalam graf, pokok rentang minimum mempunyai bilangan tepi (V - 1), dengan V ialah bilangan tepi.

Cari pepohon rentang minimum menggunakan algoritma Kruskal

• Semua tepi hendaklah diisih dalam susunan tidak menurun mengikut berat.

• Pilih bahagian yang paling kecil. Jika tiada gelung terbentuk, tepi disertakan.

• Langkah 2 hendaklah dilakukan sehingga pokok rentang mempunyai (V-1) tepi.

Dalam hal ini, kita disuruh menggunakan pendekatan tamak. Pilihan tamak adalah memilih kelebihan dengan berat terkecil. Sebagai contoh: pokok rentang minimum graf ini ialah (9-1)= 8 tepi.

After sorting:

Weight  Src    Dest
21       27    26
22       28    22
22       26    25
24       20    21
24       22    25
26       28    26
27       22    23
27       27    28
28       20    27
28       21    22
29       23    24
30       25    24
31       21    27
34       23    25

Kini kita perlu memilih semua tepi berdasarkan pengisihan.

Mengandungi tepi 26-27->, kerana tiada gelung terbentuk

Tepi termasuk 28-22->, kerana tiada gelung terbentuk

# 🎜🎜#Sertakan tepi 26-25-> kerana tiada gelung terbentuk.

Tepi 20-21-> disertakan kerana tiada gelung terbentuk

Tepi 22-25-> disertakan kerana tiada gelung terbentuk.

Tepi 28-26-> dibuang kerana pembentukan gelung

Tepi 22-23-> > disertakan kerana tiada gelung terbentuk

#🎜🎜 #Tepi27- 28->Dibuang kerana pembentukan gelung

Edge20-27->dimasukkan kerana tiada gelung terbentuk

Edge21-22->disebabkan Membentuk kitaran dan dibuang#🎜 🎜#

Tepi 23-24->Dimasukkan sebagai tidak membentuk kitaran

Memandangkan bilangan tepi ialah (V-1), algoritma berakhir di sini .

Contoh

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Edge {
   int src, dest, weight;
};
struct Graph {
   int V, E;
   struct Edge* edge;
};
struct Graph* createGraph(int V, int E){
   struct Graph* graph = (struct Graph*)(malloc(sizeof(struct Graph)));
   graph->V = V;
   graph->E = E;
   graph->edge = (struct Edge*)malloc(sizeof( struct Edge)*E);
   return graph;
}
struct subset {
   int parent;
   int rank;
};
int find(struct subset subsets[], int i){
   if (subsets[i].parent != i)
      subsets[i].parent
   = find(subsets, subsets[i].parent);
   return subsets[i].parent;
}
void Union(struct subset subsets[], int x, int y){
   int xroot = find(subsets, x);
   int yroot = find(subsets, y);
   if (subsets[xroot].rank < subsets[yroot].rank)
      subsets[xroot].parent = yroot;
   else if (subsets[xroot].rank > subsets[yroot].rank)
      subsets[yroot].parent = xroot;
   else{
      subsets[yroot].parent = xroot;
      subsets[xroot].rank++;
   }
}
int myComp(const void* a, const void* b){
   struct Edge* a1 = (struct Edge*)a;
   struct Edge* b1 = (struct Edge*)b;
   return a1->weight > b1->weight;
}
void KruskalMST(struct Graph* graph){
   int V = graph->V;
   struct Edge
   result[V];
   int e = 0;
   int i = 0;
   qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
   struct subset* subsets
   = (struct subset*)malloc(V * sizeof(struct subset));
   for (int v = 0; v < V; ++v) {
      subsets[v].parent = v;
      subsets[v].rank = 0;
   }
   while (e < V - 1 && i < graph->E) {
      struct Edge next_edge = graph->edge[i++];
      int x = find(subsets, next_edge.src);
      int y = find(subsets, next_edge.dest);
      if (x != y) {
         result[e++] = next_edge;
         Union(subsets, x, y);
      }
   }
   printf("Following are the edges in the constructed MST\n");
   int minimumCost = 0;
   for (i = 0; i < e; ++i){
      printf("%d -- %d == %d\n", result[i].src,
      result[i].dest, result[i].weight);
      minimumCost += result[i].weight;
   }
   printf("Minimum Cost Spanning tree : %d",minimumCost);
   return;
}
int main(){
   /* Let us create the following weighted graph
   30
   0--------1
   | \       |
   26| 25\ |15
   | \ |
   22--------23
   24 */
   int V = 24;
   int E = 25;
   struct Graph* graph = createGraph(V, E);
   graph->edge[0].src = 20;
   graph->edge[0].dest = 21;
   graph->edge[0].weight = 30;
   graph->edge[1].src = 20;
   graph->edge[1].dest = 22;
   graph->edge[1].weight = 26;
   graph->edge[2].src = 20;
   graph->edge[2].dest = 23;
   graph->edge[2].weight = 25;
   graph->edge[3].src = 21;
   graph->edge[3].dest = 23;
   graph->edge[3].weight = 35;
   graph->edge[4].src = 22;
   graph->edge[4].dest = 23;
   graph->edge[4].weight = 24;
   KruskalMST(graph);
   return 0;
}

Output

Following are the edges in the constructed MST
22 -- 23 == 24
20 -- 23 == 25
20 -- 21 == 30
Minimum Cost Spanning tree : 79

Kesimpulan

Tutorial Krusan ini menunjukkan cara menggunakan pokok sprink minimum kaedah dan kod C++ untuk menyelesaikan masalah ini. Kita juga boleh menulis kod ini dalam java, python dan bahasa lain. Ia dimodelkan mengikut konsep Kruskal. Atur cara ini mencari pokok rentang terpendek dalam graf tertentu. Kami harap anda mendapati tutorial ini membantu.

Atas ialah kandungan terperinci Algoritma Pokok Spanning Minimum Kruskal - Algoritma Tamak dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!