Giới thiệu
Cho một đồ thị liên thông G(V, E) với trọng số (chi phí) cho mọi cạnh. Thuật toán Prim sẽ tìm cây khung tối thiểu (Minimum Spanning Tree - MST) từ đồ thị G.
Đây là phương pháp "phát triển cây". Thuật toán cần một đỉnh gốc (seed vertex) để bắt đầu xây dựng cây. Từ đỉnh gốc này, cây được mở rộng dần dần cho đến khi bao phủ toàn bộ đồ thị.

Bài toán được giải quyết bằng hai tập hợp: một tập chứa các đỉnh đã chọn, tập kia chứa các đỉnh chưa xét. Từ đỉnh gốc, thuật toán lấy các đỉnh kề dựa trên chi phí cạnh nhỏ nhất, từ đó mở rộng cây bằng cách thêm đỉnh lần lượt.
Độ phức tạp thời gian: O(V²), trong đó V là số đỉnh.
Đầu vào và Đầu ra
Đầu vào: Danh sách kề:Đầu ra: (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)
Thuật toán
prims(g: Graph, t: tree, start)
Đầu vào: Đồ thị g, một cây rỗng và đỉnh gốc tên là 'start'
Đầu ra: Cây sau khi thêm các cạnh.
Begin
định nghĩa hai tập hợp usedVert, unusedVert
usedVert[0] := start và unusedVert[0] := ∅
với mọi đỉnh trừ start làm:
usedVert[i] := ∅
unusedVert[i] := i // thêm tất cả đỉnh vào danh sách chưa dùng
done
trong khi số đỉnh trong usedVert ≠ V làm: // V là tổng số nút
min := ∞
với mọi đỉnh của mảng usedVert làm:
với mọi đỉnh của đồ thị làm:
nếu min > cost[i,j] VÀ i ≠ j thì
min := cost[i,j]
ed := cạnh giữa i và j, chi phí của ed := min
done
done
done
unusedVert[đích của ed] := ∅
thêm cạnh ed vào cây t
thêm nguồn của ed vào usedVert
done
End
Ví dụ (C++)
#include <iostream>
#define V 7
#define INF 999
using namespace std;
// Ma trận chi phí của đồ thị
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]; // cây có V-1 cạnh
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;
// Khởi tạo
usedVert[0] = start; p = 1;
unusedVert[0] = -1; // -1 chỉ vị trí trống
for(i = 1; i < V; i++) {
usedVert[i] = -1; // tất cả vị trí trừ đầu tiên đều trống
unusedVert[i] = i; // điền các đỉnh
}
tr.n = 0;
// Lấy cạnh và thêm vào cây
while(p != V) { // p là số đỉnh trong mảng usedVert
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; // xóa v khỏi unusedVertex
tr.addEdge(ed);
usedVert[p] = ed.u; p++; // thêm u vào usedVertex
}
}
int main() {
Tree tr;
prims(tr, 0); // đỉnh bắt đầu 0
tr.printEdges();
}
Kết quả đầu ra
(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)
Đầu ra: (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)