อัลกอริทึม Kruskal สำหรับต้นไม้ครอบคลุมน้ำหนักขั้นต่ำ

บทนำ

อัลกอริทึม Kruskal เป็นอีกวิธีหนึ่งในการหาต้นไม้ครอบคลุมน้ำหนักขั้นต่ำ (MST) จากกราฟที่เชื่อมต่อ G(V, E) โดยมีน้ำหนักเส้นขอบกำหนดไว้

หลักการทำงาน

ใช้แนวคิด "Merge-Tree Approach" เริ่มต้นด้วยต้นไม้แยกกันหลายต้น (แต่ละโหนดเป็นต้นไม้ตัวเดียว) จากนั้นรวมต้นไม้โดยเลือกเส้นขอบที่มีน้ำหนักน้อยที่สุดทีละเส้น ตรวจสอบว่าการเพิ่มเส้นขอบนั้นจะทำให้เกิดวงจร (Cycle) หรือไม่ หากเกิดวงจรจะทิ้งเส้นขอบนั้นไป พิจารณาเส้นขอบถัดไป

ความซับซ้อนของเวลา (Time Complexity)

O(E log E) หรือ O(E log V) โดยที่ E คือจำนวนเส้นขอบ และ V คือจำนวนโหนด

อินพุตและเอาต์พุต

Input: เมทริกซ์ติดกัน (Adjacency Matrix)
Output: 
Edge: B--A And Cost: 1
Edge: E--B And Cost: 2
Edge: F--E And Cost: 2
Edge: C--A And Cost: 3
Edge: G--F And Cost: 3
Edge: D--A And Cost: 4
Total Cost: 15

อัลกอริทึม

kruskal(g: Graph, t: Tree)

Input: กราฟ g, ต้นไม้ว่าง t
Output: ต้นไม้ t ที่มีเส้นขอบที่เลือกแล้ว

Begin
    สร้างเซตสำหรับแต่ละโหนดในกราฟ g
    สำหรับแต่ละเซตของโหนด u do
        ใส่ u เข้า vertexSet[u]
    done
    เรียงลำดับรายการเส้นขอบตามค่าใช้จ่าย
    count := 0
    while count <= V-1 do  // ต้นไม้ต้องมี V-1 เส้นขอบ
        ed := edgeList[count]  // เลือกเส้นขอบจากรายการ
        if โหนดเริ่มต้นและโหนดปลายของ ed อยู่ในเซตเดียวกัน then
            รวม vertexSet[start] และ vertexSet[end]
            เพิ่ม ed เข้าไปในต้นไม้ t
        count := count + 1
    done
End

ตัวอย่างโค้ด (C++)

#include<iostream>
#define V 7
#define INF 999
using namespace std;

int costMat[V][V] = {
    {0, 1, 3, 4, INF, 5, INF},
    {1, 0, INF, 7, 2, INF, INF},
    {3, INF, 0, INF, 8, INF, INF},
    {4, 7, INF, 0, INF, INF, INF},
    {INF, 2, 8, INF, 0, 2, 4},
    {5, INF, INF, INF, 2, 0, 3},
    {INF, INF, INF, INF, 4, 3, 0}
};

typedef struct { int u, v, cost; } edge;

void swapping(edge &e1, edge &e2) { edge temp = e1; e1 = e2; e2 = temp; }

class Tree {
    int n; edge edges[V-1];
public:
    Tree() { n = 0; }
    void addEdge(edge e) { edges[n] = e; n++; }
    void printEdges() {
        int tCost = 0;
        for(int i = 0; i= 0) set1.addVertex(set2.deleteVertex());
}

int findVertex(VSet *vertSetArr, int vert) {
    for(int i = 0; i edgeList[j+1].cost) {
                swapping(edgeList[j], edgeList[j+1]);
                flag = 1;
            }
    }
}

void kruskal(Tree &tr) {
    int ecount, maxEdge = V*(V-1)/2;
    edge edgeList[maxEdge], ed;
    int uloc, vloc;
    VSet VSetArray[V];
    ecount = findEdge(edgeList);
    for(int i = 0; i < V; i++) VSetArray[i].addVertex(i);
    sortEdge(edgeList, ecount);
    int count = 0;
    while(count <= V-1) {
        ed = edgeList[count];
        uloc = findVertex(VSetArray, ed.u);
        vloc = findVertex(VSetArray, ed.v);
        if(uloc != vloc) {
            merge(VSetArray[uloc], VSetArray[vloc]);
            tr.addEdge(ed);
        }
        count++;
    }
}

int main() {
    Tree tr;
    kruskal(tr);
    tr.printEdges();
}

ผลลัพธ์

Edge: B--A And Cost: 1 Edge: E--B And Cost: 2 Edge: F--E And Cost: 2 Edge: C--A And Cost: 3 Edge: G--F And Cost: 3 Edge: D--A And Cost: 4 Total Cost: 15