Prim's Algorithm (Minimum Spanning Tree - MST): หาต้นไม้ครอบคลุมน้ำหนักน้อยสุด

มีกราฟเชื่อมต่อ G(V,E) พร้อมน้ำหนัก/ค่าใช้จ่ายของแต่ละ Edge Prim's Algorithm หา Minimum Spanning Tree (MST) จากกราฟ G

เป็น Growing Tree Approach ต้องการ Seed Vertex เริ่มต้น ขยายต้นไม้จากโหนด Seed

แก้ด้วย 2 Sets: Used Vertices (เลือกแล้ว) และ Unused Vertices (ยังไม่เลือก) จาก Seed เลือกโหนดติดกันที่ Edge Cost น้อยที่สุด ขยายต้นไม้ทีละโหนด

• Time Complexity: O(V²) โดย V = จำนวนโหนด

Input

Adjacency List (แสดงในรูปภาพ)

Output

(0)---(1|1) (0)---(2|3) (0)---(3|4) (1)---(0|1) (1)---(4|2) (2)---(0|3) (3)---(0|4) (4)---(1|2) (4)---(5|2) (5)---(4|2) (5)---(6|3) (6)---(5|3)

Algorithm

prims(g: Graph, t: tree, start)

Input: กราฟ g, Tree ว่าง, Seed vertex 'start'
Output: Tree หลังเพิ่ม Edges

Begin
    define two sets: usedVert, unusedVert
    usedVert[0] := start; unusedVert[0] := φ
    for all vertices except start do
        usedVert[i] := φ; unusedVert[i] := i
    done
    while number of vertices in usedVert ≠ V do
        min := ∞
        for all vertices of usedVert do
            for all vertices of graph do
                if min > cost[i,j] AND i ≠ j then
                    min := cost[i,j]
                    ed := edge between i and j, cost = min
                done
            done
        done
        unusedVert[destination of ed] := φ
        add edge ed into tree t
        add source of ed into usedVert
    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;
    }
    friend void prims(Tree &tre, int start);
};

void prims(Tree &tr, int start) {
    int usedVert[V], unusedVert[V];
    int i, j, min, p; edge ed;
    usedVert[0] = start; p = 1;
    unusedVert[0] = -1;
    for(i = 1; i < V; i++) {
        usedVert[i] = -1; unusedVert[i] = i;
    }
    tr.n = 0;
    while(p != V) {
        min = INF;
        for(i = 0; i < p; i++)
            for(j = 0; j < V; j++)
                if(unusedVert[j] != -1)
                    if(min > costMat[i][j] && costMat[i][j] != 0) {
                        min = costMat[i][j];
                        ed.u = i; ed.v = j; ed.cost = min;
                    }
        unusedVert[ed.v] = -1;
        tr.addEdge(ed);
        usedVert[p] = ed.u; p++;
    }
}

main() {
    Tree tr;
    prims(tr, 0); // starting node 0
    tr.printEdges();
}

Output

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