生成樹是連接所有頂點的有向無向圖子圖。圖中可以存在許多生成樹。每個圖上的最小生成樹（MST）的權重相同或小於所有其他生成樹。權重被分配給生成樹的邊，總和是分配給每個邊的權重。由於 V 是圖中的頂點數，因此最小生成樹的邊數為 (V - 1)，其中 V 是邊數。
所有邊應依權重非降序排列。
選擇最小的邊。如果未形成環，則包含該邊。
應執行步驟 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中文網其他相關文章！
