Thuật toán Prim còn được mang tên là người láng giềng gần nhất.Trong thuật toán này, bắt đầu tại một đỉnh tuỳ ý s của đồ thị, nối s với đỉnh y sao cho trọng số cạnh c[s, y] là nhỏ nhất. Tiếp theo, từ đỉnh s hoặc y tìm cạnh có độ dài nhỏ nhất, điều này dẫn đến đỉnh thứ ba z và thu được cây bộ phận gồm 3 đỉnh 2 cạnh. Quá trình được tiếp tục cho tới khi ta nhận được cây gồm n-1 cạnh, đó chính là cây khung nhỏ nhất cần tìm.

Giả mã thuật toán Prim

void Prim (void)

{ /*bước khởi tạo*/

Chọn s là một đỉnh nào đó của đồ thị;

VH={s};T=Ø;  //rỗng

d[s]=0;

near[s]=s;

For (v ϵ V\VH)  // thuộc

{

D[v] = C[s, v]; near[v] = s;

}

/* Bước lặp */

Stop = False;

while ( not stop ) {

Tìm u ϵ V\VH thoả mãn: d[u] = min { d[v] với u ϵ V\VH};

VH = VH ∪ {u};

T = T ∪ (u, near[u] );

if ( | VH |) == n )

 {

H = <VH, T> là cây khung nhỏ nhất của đồ thị;

Stop = TRUE;

}

else { for ( v ϵ V\VH ) {

if (d[v] > C[u, v]) {

D[v] = C[u, v];

Near[v] = ;

}

}

}

}

}