ต้นไม้ครอบคลุม (Spanning Tree) คือซับกราฟของกราฟเชื่อมต่อและไม่มีทิศทาง ที่เชื่อมต่อทุกโหนด (vertices) กราฟหนึ่งสามารถมีหลายต้นไม้ครอบคลุม ต้นไม้ครอบคลุมขั้นต่ำ (MST) ของแต่ละกราฟมีน้ำหนักเท่ากันหรือน้อยกว่าต้นไม้ครอบคลุมอื่นๆ ทุกตัว น้ำหนักถูกกำหนดให้กับขอบ (edges) ของต้นไม้ครอบคลุม และผลรวมคือน้ำหนักที่กำหนดให้แต่ละขอบ เนื่องจาก V คือจำนวนโหนดในกราฟ ต้นไม้ครอบคลุมขั้นต่ำมีขอบ (V - 1) ขอบ โดย V คือจำนวนขอบ
การหาต้นไม้ครอบคลุมขั้นต่ำด้วยอัลกอริทึม Kruskal
- จัดเรียงขอบทั้งหมดตามน้ำหนักแบบไม่ลดลง (non-descending)
- เลือกขอบที่มีน้ำหนักน้อยที่สุด รวมขอบนี้เข้าไปถ้าไม่เกิดรูปวงจร (cycle)
- ทำซ้ำขั้นตอนที่ 2 จนกว่าต้นไม้ครอบคลุมจะมี (V-1) ขอบ
ในสถานการณ์นี้ เราถูกบอกให้ใช้วิธี Greedy (貪婪) ตัวเลือก Greedy คือเลือกขอบที่มีน้ำหนักน้อยที่สุด ตัวอย่าง: ต้นไม้ครอบคลุมขั้นต่ำของกราฟนี้คือ (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
ตอนนี้เราต้องเลือกขอบทั้งหมดตามลำดับที่จัดเรียงแล้ว
Edge 26-27 → รวมเข้า เพราะไม่เกิดวงจร
Edge 28-22 → รวมเข้า เพราะไม่เกิดวงจร
Edge 26-25 → รวมเข้า เพราะไม่เกิดวงจร
Edge 20-21 → รวมเข้า เพราะไม่เกิดวงจร
Edge 22-25 → รวมเข้า เพราะไม่เกิดวงจร
Edge 28-26 → ทิ้ง เพราะเกิดวงจร
Edge 22-23 → รวมเข้า เพราะไม่เกิดวงจร
Edge 27-28 → ทิ้ง เพราะเกิดวงจร
Edge 20-27 → รวมเข้า เพราะไม่เกิดวงจร
Edge 21-22 → ทิ้ง เพราะเกิดวงจร
Edge 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's Minimum Spanning Tree Algorithm แบบ Greedy และโค้ด C++ เพื่อแก้ปัญหานี้ สามารถเขียนใน Java, Python และภาษาอื่นๆ ได้ โมเดลนี้พัฒนาโดยแนวคิดของ Kruskal โปรแกรมนี้หาต้นไม้ครอบคลุมสั้นที่สุดในกราฟที่กำหนด หวังว่าบทช่วยสอนนี้จะมีประโยชน์
