Kruskal's Algorithm (Minimum Spanning Tree - MST): แนวทาง Merge Tree

มีกราฟเชื่อมต่อ G(V,E) พร้อมน้ำหนัก Edge Kruskal's Algorithm หา MST ด้วยแนวทาง Merge Tree

เริ่มต้นมีหลายต้นไม้ แล้ว Merge โดยเลือก Edge น้ำหนักน้อยสุด สร้างเป็นต้นไม้เดียว

รายการ Edge ทั้งหมด เรียงตาม Cost น้อยไปมาก เลือก Edge น้อยสุดเพิ่มเข้า Tree ตรวจสอบ Cycle ถ้ามี Cycle ทิ้ง Edge ไปเลย

• Time Complexity: O(E log E) หรือ O(E log V) โดย E = จำนวน Edge, V = จำนวน Vertex

Input

Adjacency Matrix

0 1 3 4 ∞ 5 ∞
1 0 ∞ 7 2 ∞ ∞
3 ∞ 0 ∞ 8 ∞ ∞
4 7 ∞ 0 ∞ ∞ ∞
∞ 2 8 ∞ 0 2 4
5 ∞ ∞ ∞ 2 0 3
∞ ∞ ∞ ∞ 4 3 0

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

Algorithm

kruskal(g: Graph, t: Tree)

Input: กราฟ g, Tree ว่าง t
Output: Tree t พร้อม Edge ที่เลือก

Begin
    create set for each vertex in graph g
    for each set of vertex u do
        add u in vertexSet[u]
    done
    sort the edge list
    count := 0
    while count <= V-1 do
        ed := edgeList[count]
        if start and end of ed in same set then
            merge vertexSet[start] and vertexSet[end]
            add ed into tree 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;

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 < n; i++) {
            cout << "Edge: " << char(edges[i].u+'A') << "--" << char(edges[i].v+'A');
            cout << " And Cost: " << edges[i].cost << endl;
            tCost += edges[i].cost;
        }
        cout << "Total Cost: " << tCost << endl;
    }
};

class VSet {
    int n; int set[V];
public:
    VSet() { n = -1; }
    void addVertex(int vert) { set[++n] = vert; }
    int deleteVertex() { return set[n--]; }
    friend int findVertex(VSet *vertSetArr, int vert);
    friend void merge(VSet &set1, VSet &set2);
};

void merge(VSet &set1, VSet &set2) {
    while(set2.n >= 0) set1.addVertex(set2.deleteVertex());
}

int findVertex(VSet *vertSetArr, int vert) {
    for(int i = 0; i < V; i++)
        for(int j = 0; j <= vertSetArr[i].n; j++)
            if(vert == vertSetArr[i].set[j]) return i;
}

int findEdge(edge *edgeList) {
    int count = -1, i, j;
    for(i = 0; i < V; i++)
        for(j = 0; j < i; j++)
            if(costMat[i][j] != INF) {
                count++;
                edgeList[count].u = i; edgeList[count].v = j;
                edgeList[count].cost = costMat[i][j];
            }
    return count+1;
}

void sortEdge(edge *edgeList, int n) {
    int flag = 1, i, j;
    for(i = 0; i < (n-1) && flag; i++) {
        flag = 0;
        for(j = 0; j < (n-i-1); j++)
            if(edgeList[j].cost > edgeList[j+1].cost) {
                swap(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();
}

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