Kruskal的最小生成樹演算法-貪婪演算法在C++中

生成樹是連接所有頂點的有向無向圖子圖。圖中可以存在許多生成樹。每個圖上的最小生成樹（MST）的權重相同或小於所有其他生成樹。權重被分配給生成樹的邊，總和是分配給每個邊的權重。由於 V 是圖中的頂點數，因此最小生成樹的邊數為 (V - 1)，其中 V 是邊數。

使用 Kruskal 演算法找出最小生成樹

• 所有邊應依權重非降序排列。

• 選擇最小的邊。如果未形成環，則包含該邊。

• 應執行步驟 2，直到生成樹具有 (V-1) 條邊。

在這種情況下，我們被告知要使用貪婪方法。貪心選項是選擇權重最小的邊。舉例來說：此圖的最小生成樹為 (9-1)= 8 條邊。

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

現在我們需要根據排序選取所有邊。

包含邊26-27->，因為沒有形成環

邊包括28-22->，因為沒有形成環路

包括邊緣26- 25->，因為沒有形成環路。

包括邊緣 20-21->，因為沒有形成環路

邊 22-25-> 被包含，因為沒有形成環路。

邊28-26-> 因環路形成而被丟棄

邊22-23-> > 包括，因為沒有形成環路

邊27-28- > 因環路形成而被丟棄

邊線20-27-> 包括，因為沒有形成環路

邊21-22->因形成環而被丟棄

#邊23-24->因未形成環而被包含

由於邊的數量為(V-1)，所以演算法到此結束。

範例

#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;
}

輸出

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

結論

#本教學示範如何使用Kruskal 的最小生成樹演算法-貪心法和C 程式碼來解決此問題。我們也可以用java、python和其他語言來寫這段程式碼。它是根據克魯斯卡爾的概念建模的。該程式會尋找給定圖中的最短生成樹。我們希望本教學對您有所幫助。

以上是Kruskal的最小生成樹演算法-貪婪演算法在C++中的詳細內容。更多資訊請關注PHP中文網其他相關文章！