Prim MST với biểu diễn danh sách kề

Tương tự Prim với ma trận kề, khác ở chỗ đồ thị G(V,E) biểu diễn bằng danh sách kề.

Độ phức tạp danh sách kề: O(E log V).

Input và Output

Input: Ma trận chi phí (hình ảnh)
Output:
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

Thuật toán

prims(g: Graph, start)
Input: Đồ thị g, đỉnh gốc start
Output: Cây khung nhỏ nhất (MST)

Begin
  tạo 2 tập hợp B (đã chọn), N (tất cả đỉnh)
  thêm start vào B
  for u in V do thêm u vào N done
  while B ≠ N do
    min := ∞
    for u in V do
      if u in B then
        for v kề với u do
          if v in (N - B) then
            if min > cost(u,v) then min:=cost, parent:=u, node:=v
          done
        done
      done
    done
    thêm node vào B
    thêm cạnh parent-node vào cây
  done
  return tree
End

Ví dụ (C++)

#include <iostream>
#include <list>
#include <set>
using namespace std;

struct node { int dest, cost; };

class Graph {
    int n; list<node> *adjList;
    void showList(int src, list<node> lt) { /* ... */ }
public:
    Graph(int n=0): n(n) { if(n) adjList=new list<node>[n]; }
    void addEdge(int src, int dest, int cost) {
        adjList[src].push_back({dest,cost});
    }
    void displayEdges() { /* ... */ }
    friend Graph primsMST(Graph g, int start);
};

set<int> difference(set<int> a, set<int> b) {
    set<int> res;
    for(int x:a) if(b.find(x)==b.end()) res.insert(x);
    return res;
}

Graph primsMST(Graph g, int start) {
    int n = g.n;
    set<int> B, N; Graph tree(n);
    B.insert(start);
    for(int u=0;u e.cost) { min=e.cost; par=u; v=e.dest; }
            }
        }
        B.insert(v);
        tree.addEdge(par,v,min); tree.addEdge(v,par,min);
    }
    return tree;
}

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);
    Graph tree = primsMST(g, 0);
    tree.displayEdges();
}

Kết quả

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

Cải tiến: Dùng priority queue (min-heap) lưu (weight, vertex) thay vì quét toàn bộ cạnh mỗi lần → O(E log V). Code trên dùng set + quét để minh họa thuật toán cơ bản.