Một cây khung là một đồ thị con liên thông và vô hướng kết nối tất cả các đỉnh. Nhiều cây khung có thể tồn tại trong một đồ thị. Cây khung nhỏ nhất (MST) trên mỗi đồ thị có trọng số bằng hoặc nhỏ hơn tất cả các cây khung khác. Trọng số được gán cho các cạnh của cây khung và tổng là trọng số được gán cho mỗi cạnh. Với V là số đỉnh trong đồ thị, cây khung nhỏ nhất có (V - 1) cạnh, nơi V là số cạnh.
Tìm cây khung nhỏ nhất bằng thuật toán Kruskal
Tất cả các cạnh nên được sắp xếp theo trình tự không giảm của trọng số.
Chọn cạnh nhỏ nhất. Cạnh này được bao gồm nếu không tạo thành chu trình.
Bước 2 nên được thực hiện cho đến khi cây khung có (V-1) cạnh.
Trong kịch bản này, chúng ta được yêu cầu sử dụng phương pháp tham lam. Lựa chọn tham lam là chọn cạnh có trọng số nhỏ nhất. Ví dụ: Cây khung nhỏ nhất cho đồ thị này là (9-1)= 8 cạnh.
Sau khi sắp xếp: Trọng số 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
Bây giờ chúng ta cần chọn tất cả các cạnh theo thứ tự sắp xếp.
Cạnh 26-27-> bao gồm vì không tạo chu trình
Cạnh 28-22-> bao gồm vì không tạo chu trình
Cạnh 26-25-> bao gồm vì không tạo chu trình.
Cạnh 20-21-> bao gồm vì không tạo chu trình
Cạnh 22-25-> bao gồm vì không tạo chu trình.
Cạnh 28-26-> loại bỏ vì tạo chu trình
Cạnh 22-23-> bao gồm vì không tạo chu trình
Cạnh 27-28-> loại bỏ vì tạo chu trình
Cạnh 20-27-> bao gồm vì không tạo chu trình
Cạnh 21-22-> loại bỏ vì tạo chu trình
Cạnh 23-24-> bao gồm vì không tạo chu trình
Vì số cạnh là (V-1), nên thuật toán kết thúc ở đây.
Ví dụ
#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("Các cạnh trong cây khung nhỏ nhất được xây dựng\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("Chi phí nhỏ nhất cây khung: %d",minimumCost); return; } int main(){ /* Hãy tạo đồ thị có trọng số sau 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; }Đầu ra
Các cạnh trong cây khung nhỏ nhất được xây dựng 22 -- 23 == 24 20 -- 23 == 25 20 -- 21 == 30 Chi phí nhỏ nhất cây khung: 79
Kết luận
Hướng dẫn này đã trình bày cách sử dụng thuật toán Kruskal tìm cây khung nhỏ nhất - phương pháp tham lam và code C++ để giải quyết bài toán này. Chúng ta cũng có thể viết code này bằng Java, Python và các ngôn ngữ khác. Chương trình được mô hình hóa theo khái niệm của Kruskal. Chương trình này tìm cây khung ngắn nhất trong một đồ thị cho trước. Hy vọng bạn thấy hướng dẫn này hữu ích.