Cho đồ thị liên thông G(V,E) với trọng số cạnh. Prim tìm cây khung nhỏ nhất từ G.
Cách tiếp cận phát triển cây (growing tree). Cần giá trị hạt giống (seed vertex) để bắt đầu. Đỉnh hạt giống phát triển thành toàn bộ cây.

Giải quyết bằng hai tập hợp: tập đỉnh đã chọn và tập chưa xem xét. Từ đỉnh hạt giống, lấy đỉnh kề dựa trên chi phí cạnh nhỏ nhất, phát triển cây bằng cách thêm nút từng cái.
- Độ phức tạp thời gian: O(V²). V là số đỉnh.
Đầ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, cây rỗng, đỉnh hạt giống 'start'. Đầu ra: Cây sau khi thêm cạnh.
Begin
định nghĩa hai tập usedVert, unusedVert
usedVert[0] := start và unusedVert[0] := φ
for all vertices except start do
usedVert[i] := φ
unusedVert[i] := i //thêm tất cả đỉnh vào unused
done
while số đỉnh trong usedVert ≠ V do
min := ∞
for all vertices của usedVert do
for all vertices của đồ thị do
if min > cost[i,j] AND i ≠ j then
min := cost[i,j]
ed := cạnh giữa i và j, chi phí 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
EndVí dụ (C++)
#include#define V 7 #define INF 999 using namespace std; int costMat[V][V] = { ... }; typedef struct{ int u, v, cost; }edge; class Tree{ ... }; void prims(Tree &tr, int start){ ... } main(){ Tree tr; prims(tr, 0); tr.printEdges(); }
Đầ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)