อัลกอริทึม Prim สำหรับต้นไม้ครอบคลุมน้ำหนักขั้นต่ำ (Minimum Spanning Tree)

บทนำ

อัลกอริทึม Prim เป็นหนึ่งในอัลกอริทึมที่ใช้หาต้นไม้ครอบคลุมน้ำหนักขั้นต่ำ (Minimum Spanning Tree - MST) จากกราฟที่เชื่อมต่อกัน (Connected Graph) G(V, E) โดยที่แต่ละเส้นขอบ (Edge) มีน้ำหนักหรือค่าใช้จ่ายกำหนดไว้

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

อัลกอริทึมนี้ใช้แนวคิด "Growing Tree Approach" เริ่มจากจุดเริ่มต้น (Seed Vertex) ที่เลือกไว้ แล้วขยายต้นไม้โดยการเพิ่มโหนด (Vertex) ทีละตัว โดยเลือกเส้นขอบที่มีน้ำหนักน้อยที่สุดซึ่งเชื่อมระหว่างโหนดที่อยู่ในต้นไม้อยู่แล้วกับโหนดที่ยังไม่ได้ถูกเลือก

การแก้ปัญหานี้ใช้ชุดข้อมูล 2 ชุด:

• UsedVert: ชุดของโหนดที่ถูกเลือกเข้าต้นไม้แล้ว
• UnusedVert: ชุดของโหนดที่ยังไม่ถูกพิจารณา

จากโหนดเริ่มต้น จะพิจารณาโหนดที่อยู่ติดกัน โดยเลือกเส้นขอบที่มีค่าน้ำหนักน้อยที่สุด ทำซ้ำจนครบทุกโหนด

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

O(V²) โดยที่ V คือจำนวนโหนด (Vertices)

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

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)

อัลกอริทึม

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

Input: กราฟ g, ต้นไม้ว่างเปล่า t, และโหนดเริ่มต้น 'start'
Output: ต้นไม้ t หลังจากเพิ่มเส้นขอบแล้ว

Begin
    กำหนดชุด usedVert และ unusedVert
    usedVert[0] := start และ unusedVert[0] := φ
    สำหรับทุกโหนดยกเว้น start:
        usedVert[i] := φ
        unusedVert[i] := i  // ใส่โหนดทั้งหมดเข้า unused list
    done
    
    while จำนวนโหนดใน usedVert ≠ V do  // V = จำนวนโหนดทั้งหมด
        min := ∞
        สำหรับทุกโหนดใน usedVert array:
            สำหรับทุกโหนดในกราฟ:
                if min > cost[i,j] AND i ≠ j then
                    min := cost[i,j]
                    ed := เส้นขอบระหว่าง i และ j, cost ของ ed := min
            done
        done
        unusedVert[ปลายทางของ ed] := φ
        เพิ่มเส้นขอบ ed เข้าไปในต้นไม้ t
        เพิ่มต้นทางของ ed เข้า 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];  // ต้นไม้มีเส้นขอบ V-1 เส้น
public:
    Tree() { n = 0; }
    void addEdge(edge e) { edges[n] = e; n++; }
    void printEdges() {
        int tCost = 0;
        for(int i = 0; i costMat[i][j] && costMat[i][j] != 0) {
                        min = costMat[i][j];
                        ed.u = i; ed.v = j; ed.cost = min;
                    }
                }
            }
        }
        unusedVert[ed.v] = -1;  // ลบ v ออกจาก unusedVertex
        tr.addEdge(ed);
        usedVert[p] = ed.u; p++;  // เพิ่ม u เข้า usedVertex
    }
}

main() {
    Tree tr;
    prims(tr, 0);  // เริ่มจากโหนด 0
    tr.printEdges();
}

ผลลัพธ์

(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)