Prim's MST สำหรับ Adjacency List Representation

Prim's Algorithm หา Minimum Spanning Tree (MST) ของกราฟเชื่อมต่อแบบ Undirected Weighted Graph ใช้ Adjacency List และ Priority Queue ทำให้ได้ Time Complexity O(E log V)

ความซับซ้อน (Complexity)

แนวคิดการทำงาน

1. เริ่มจากโหนดใดโหนดหนึ่ง (เช่น 0) ใส่เข้า Set MST Set
2. ดูขอบทั้งหมดที่เชื่อมจาก MST Set ไปยังโหนดนอก Set
3. เลือกขอบที่มีน้ำหนัก น้อยที่สุด เพิ่มโหนดปลายขอบเข้า MST Set
4. ทำซ้ำจนครบทุกโหนด (V-1 ขอบ)

ตัวอย่างกราฟ

โหนด: A(0), B(1), C(2), D(3), E(4), F(5), G(6)

Edges:
A-B:1  A-C:3  A-D:4  A-F:5
B-A:1  B-D:7  B-E:2
C-A:3  C-E:8
D-A:4  D-B:7
E-B:2  E-F:2  E-G:4
F-A:5  F-E:2  F-G:3
G-E:4  G-F:3

ผลลัพธ์ MST

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

อัลกอริทึม (Pseudocode)

primsMST(graph, start)
  MST = empty graph
  inMST[V] = {false}
  minWeight[V] = {INF}
  parent[V] = {-1}

  minWeight[start] = 0
  PQ = MinHeap of (weight, vertex)
  PQ.push(0, start)

  while PQ not empty:
    (w, u) = PQ.pop()
    if inMST[u]: continue
    inMST[u] = true
    if parent[u] != -1:
      add edge (parent[u], u, w) to MST

    for each (v, weight) in adj[u]:
      if not inMST[v] AND weight < minWeight[v]:
        minWeight[v] = weight
        parent[v] = u
        PQ.push(weight, v)

  return MST

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

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <climits>
using namespace std;

struct Edge { int dest, weight; };

struct Graph {
    int V;
    vector<vector<Edge>> adj;
    Graph(int v) : V(v), adj(v) {}
    void addEdge(int u, int v, int w) {
        adj[u].push_back({v, w});
    }
};

void primsMST(Graph &g, int start) {
    int V = g.V;
    vector<bool> inMST(V, false);
    vector<int> minWeight(V, INT_MAX), parent(V, -1);
    minWeight[start] = 0;

    // Min-heap: (weight, vertex)
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, start});

    int totalCost = 0;

    while (!pq.empty()) {
        auto [w, u] = pq.top(); pq.pop();
        if (inMST[u]) continue;
        inMST[u] = true;
        totalCost += w;

        if (parent[u] != -1)
            cout << "Edge: " << char('A'+parent[u]) << "-" << char('A'+u)
                 << " Cost: " << w << endl;

        for (auto &e : g.adj[u]) {
            int v = e.dest, weight = e.weight;
            if (!inMST[v] && weight < minWeight[v]) {
                minWeight[v] = weight;
                parent[v] = u;
                pq.push({weight, v});
            }
        }
    }
    cout << "Total Cost: " << totalCost << endl;
}

int main() {
    Graph g(7);
    g.addEdge(0,1,1); g.addEdge(0,2,3); g.addEdge(0,3,4); g.addEdge(0,5,5);
    g.addEdge(1,0,1); g.addEdge(1,3,7); g.addEdge(1,4,2);
    g.addEdge(2,0,3); g.addEdge(2,4,8);
    g.addEdge(3,0,4); g.addEdge(3,1,7);
    g.addEdge(4,1,2); g.addEdge(4,2,8); g.addEdge(4,5,2); g.addEdge(4,6,4);
    g.addEdge(5,0,5); g.addEdge(5,4,2); g.addEdge(5,6,3);
    g.addEdge(6,4,4); g.addEdge(6,5,3);

    primsMST(g, 0);
}

Prim's vs Kruskal's