BÀI TẬP LỚN MÔN: CẤU TRÚC DỮ LIỆU VÀ GIẢI
THUẬT
Đề tài: Cài đặt thuật toán Prim tìm cây khung nhỏ nhất của đồ
thị vô hướng
I.

Giới thiệu chung về thuật toán Prim và các ứng dụng
Bài toán cây khung nhỏ nhất của đồ thị là một trong số những bài toán tối ưu
trên đồ thị tìm được ứng dụng trong nhiều lĩnh vực khác nhau của đời sống.
Trước hết chúng ta phát biểu nội dung bài toán: Cho G=(V,E) là đồ thị vô
hướng liên thông với tập đỉnh V={1,2,…,n} và tập cạnh E gồm m cạnh. Mỗi
cạnh E của đồ thị G được gán với một số không âm c(e), gọi là độ dài của nó.
Giả sử H=(V,T) là cây khung của đồ thị G. Ta gọi độ dài c(H) của cây khung H
là tổng độ dài các cạnh của nó: C(H)=∑e c(e).
Bài toán đặt ra trong tất cả cây khung của đò thị G hãy tìm cây khung với độ
dài nhỏ nhất. Cây khung như vậy được gọi là bài thoán cây khung nhỏ nhất.
Đối với bài toán cây khung nhỏ nhất chúng ta có những thuật toán rất hiệu
quả để giải chúng. Một trong số đó là thuật toán Prim.
Thuật toán Prim còn được gọi là thuật toán lân cận gần nhất. Trong phương
pháp này bắt đầu từ một đỉnh tùy ý của đồ thị, đầu tiên ta nối s với đỉnh lân cận
gần nó nhất, chẳng hạn là đỉnh y. Nghĩa là trong số các cạnh kề của đỉnh s, cạnh
(s,y) có độ dài nhỏ nhất. Tiếp theo trong số các cạnh kề với hai đỉnh s hoặc đỉnh
y ta tìm cạnh có độ dài nhỏ nhất, cạnh này dẫn đến đỉnh thứ ba z, vf ta thu được
cây bộ phận gồm 3 đỉnh 2 cạnh. Quá trình này sẽ tiếp tục cho đến khi ta thu
được cây gồm n đỉnh và n-1 cạnh sẽ chính là cây khung nhỏ nhất cần tìm.

II.

Các bước của thuật toán Prim
Bước 1: Chọn một đỉnh bất kì để bắt đầu( đưa đỉnh đó vào tập các đỉnh VH),
VH={s}.

Bước 2: Lặp lại công việc sau n-1 bước với n là số đỉnh của đồ thị {|V|=n}.


-

Chọn 1 đỉnh trong số các đỉnh chưa được chọn sao cho nó có cạnh ngắn
nhất tới 1 đỉnh trong VH.
Kết nạp đỉnh đó vào trong VH.

Mô tả thuật toán:
-

-

Tập VH( cây MST) ={};
Ở bước khởi tạo chọn một đỉnh bất kì đưa vào VH, giả sử đó là đỉnh s:
VH={s};
Xây dựng một danh sách( theo thứ tự tang dần) của các đỉnh với tiêu chí
sắp xếp theo khoảng cách từ đỉnh đó tới các đỉnh trong VH, gọi là tập Q.
Dùng một mảng đánh dấu một đỉnh đã được chọn vào cây MST
Thực hiện các thao tác sau n-1 bước:
• Loại bỏ đỉnh v khỏi Q, v chính là đỉnh có khoảng cách nhỏ nhất
với VH.
• Nếu V!=s thì kết nạp v vào VH.
• Xét các đỉnh kề với v và chưa được kết nạp vào VH( đỉnh u): nếu
khoảng cách từ u tới VH lớn hơn độ dài cung (v,u) thì cập nhật lại
khoảng cách đó: d[u]=a[v][u].
Thuật toán sẽ dừng sau n-1 cạnh được kết nạp vào cây MST.
Một mảng preview để đánh dấu đỉnh trước của mỗi đỉnh sử dụng kết nạp
đỉnh v vào cây MST( thêm cạnh preview[v],v) vào cây) và cập nhật khi

thay đổi nhãn của u preview[u]=v.

Ví dụ: Cho đồ thị vô hướng G sau:

ST

VH

Q

MST

P


T
0
1

A

2

A,D

3

A,D,F

4


A,D,F,B

(A,0) (B,∞) (C,∞)
(D,∞) (E,∞) (F,∞)
(G,∞)
(B,7) (C,∞) (D,5)
(E,∞) (F,∞) (G,∞)
(B,7) (C,∞) (E,15)
(F,6) (G,∞)
(B,7) (C,∞) (E,8)
(G,11)
(C,8) (E,7) (G,11)

5

A,D,F,B,E

(C,5) (G,9)

6

A,D,F,B,E,
C

(G,9)

7

A,D,F,B,E,

C

-1,-1,-1,-1,-1,1,-1

(A,D)
(A,D)(D,F)
(A,D)(D,F)
(A,B)
(A,D)(D,F)
(A,B) (B,E)
(A,D)(D,F)
(A,B) (B,E)
(E,C)
(A,D)(D,F)
(A,B) (B,E)
(E,C)(E,G)

-1,A,-1,A,-1,1,-1
-1,A,1,A,D,D,-1
-1,A,1,A,F,D,F
-1,
A,B,A,B,D,F
-1,
A,E,A,B,D,E
-1,
A,E,A,B,D,E

Cây MST của đò thị gồm các cạnh (A,D) (D,F) (A,B) (B,E) (E,C) (E,G) và
có tổng trọng số là 39.
III.


Cài đặt thuật toán Prim
#include <stdio.h>


#include <stdlib.h>
#define nMax 100
#define INF 100000
#define true 1
#define false 0
typedef struct{
int u;//dinh dau
int v;//dinh cuoi
int do_dai;
}Canh;
int G[nMax][nMax]; //ma tran trong so
int so_dinh;
int so_canh = 0;
int d[nMax];
int da_ket_nap[nMax];
int W = 0;//do rong cua cay khung
int lien_thong = 1;
Canh T[nMax];
void input(){
FILE *f = fopen("input.txt","r");
fscanf(f,"%d\n",&so_dinh);
for(int i = 0; i < so_dinh; i++){
for(int j = 0; j < so_dinh; j++){
fscanf(f, "%d ", &G[i][j]);
if(G[i][j] == 0 && i != j) G[i][j] = INF;

}
fscanf(f,"\n");
}
fclose(f);
}
void print_matrix(int a[][nMax], int n){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++) {
if(G[i][j] == INF) printf("INF ");
else printf("%-3d ",G[i][j]);
}
printf("\n");


}
}
void prim(){
//khoi tao cay co 1 dinh so 0
d[0] = 0;
da_ket_nap[0] = true;
for(int i = 1; i < so_dinh; i++) d[i] = INF;
W = 0;
//ket nap cac dinh khac
while(so_canh < so_dinh-1){
Canh c_min;
int d_min;
for(int i = 0; i < so_dinh; i++){
if(da_ket_nap[i] == false){
d_min = INF;
for(int j = 0; j < so_dinh; j++){

if(da_ket_nap[j] == true){
if(G[i][j] < d_min){
c_min.u = i;
c_min.v = j;
c_min.do_dai = G[i][j];
d_min = G[i][j];
}
}
}
if(d_min == INF){
lien_thong = false;
return;
}
else{
break;
}
}
}
T[so_canh] = c_min;
W += c_min.do_dai;
da_ket_nap[c_min.u] = true;
so_canh++;
}
}


int main(){
input();
printf("Ma tran trong so: \n");
print_matrix(G, so_dinh);

prim();
if(lien_thong == true){
printf("Do rong cua cay khung nho nhat: W = %d.\n",W);
printf("Danh sach canh cua cay khung: \n");
for(int i = 0; i < so_canh; i++) printf("%d - %d (%d)\n",T[i].u,
T[i].v, T[i].do_dai);
}
else{
printf("Do thi khong lien thong!.\n");
printf("Cac dinh chua dc ket nap: ");
for(int i = 0; i < so_dinh; i++) if(da_ket_nap[i] == false)
printf("%d ",i);
}
return 0;
}
Dữ liệu lấy từ file:

Kết quả chạy chương trình:


IV.

Đánh giá thuật toán

Cấu trúc dữ liệu tìm cạnh có trọng số nhỏ nhất
Tìm kiếm trên ma trận kề
Đống nhị phân và danh sách kề
Đống Fibonacci và danh sách kề
Một cách lập trình đơn giản sử dụng ma trận kề và tìm kiếm toàn bộ mảng để
tìm cạnh có trọng số nhỏ nhất có thời gian chạy O(V2). Bằng cách sử dụng cấu

trúc dữ liệu đống nhị phân và danh sách kề, có thể giảm thời gian chạy
xuống O(E log V). Bằng cách sử dụng cấu trúc dữ liệu đống Fibonacci phức tạp
hơn, có thể giảm thời gian chạy xuống O(E+ V log V), nhanh hơn thuật toán trước
khi đồ thị có số cạnh E=ω(V).
V.

Chứng minh tính đúng đắn

Đặt G là một đồ thị có trọng số liên thông. Trong mỗi bước, thuật toán Prim
chọn một cạnh nối một đồ thị con với một đỉnh không thuộc đồ thị con đó. Vì G
liên thông nên luôn tồn tại đường đi từ mỗi đồ thị con tới tất cả các đỉnh còn lại.
Kết quả T của thuật toán Prim là một cây, vì các cạnh và đỉnh được thêm vào T là
liên thông và cạnh mới thêm không bao giờ tạo thành chu trình với các cạnh cũ.


Đặt T1 là một cây bao trùm nhỏ nhất của G. Nếu T1=T thì T là cây bao trùm nhỏ
nhất. Nếu không, đặt e là cạnh đầu tiên được thêm vào T mà không thuộc T1, và V
là tập hợp các đỉnh thuộc T trước khi thêm e. Một đầu của e thuộc V và đầu kia
không thuộc V. Vì T1 là một cây bao trùm của G, nên tồn tại đường đi trong T1
nối hai đầu của e. Trên đường đi đó, nhất định tồn tại cạnh f nối một đỉnh trong V
với một đỉnh ngoài V. Trong bước lặp khi e được thêm vào Y, thuật toán cũng có
thể chọn f thay vì e nếu như trọng số của nó nhỏ hơn e. Vì f không được chọn nên
w(f) >= w(e).
Đặt T2 là đồ thị thu được bằng cách xóa f và thêm e vào T1. Dễ thấyT2 liên
thông, có cùng số cạnh như T1, và tổng trọng số các cạnh không quá trọng số của
T1, nên nó cũng là một cây bao trùm nhỏ nhất của G và nó chứa e cũng như tất cả
các cạnh được thuật toán chọn trước nó. Lặp lại lập luận trên nhiều lần, cuối cùng
ta thu được một cây bao trùm nhỏ nhất của G giống hệt như T. Vì vậy T là một cây
bao trùm nhỏ nhất.