Giáo trình Cấu trúc dữ liệu và thuật giải 2 - Nguyễn Thị Thanh Bình

 đi có đỉnh đầu và đỉnh cuối trùng 
nhau gọi là một chu trình. Một chu trình đơn là một đường đi đơn có đỉnh đầu và đỉnh 
cuối trùng nhau và có độ dài ít nhất là 1. Ví dụ trong hình I.1a thì 3,2,4,3 tạo thành 
một chu trình có độ dài 3. Trong hình I.1b thì 1,2,5,1 là một chu trình có độ dài bằng 
3. 
Trong nhiều ứng dụng ta thường kết hợp các giá trị hay nhãn với các đỉnh hoặc các 
cạnh, lúc này ta có đồ thị có nhãn. Nhãn kết hợp với các đỉnh hoặc cạnh có thể biểu 
diễn tên, giá, khoảng cách Nói chung nhãn có thể có kiểu tuỳ ý. Hình I.2 là một đồ 
thị có nhãn. 
Hình I.2 
Đồ thị con của một đồ thị G = (V, E) là một đồ thị G’ = (V’, E’) trong đó: 
- V’⊆ V và 
38 
- E’ gồm các cạnh (v, w) ∈ E sao cho v, w ∈V’ 
II. Biểu diễn đồ thị 
Thông thường để biểu diễn đồ thị người ta dùng hai cấu trúc dữ liệu là ma trận (ma 
trận kề) hoặc mảng các danh sách liên kết các đỉnh kề (danh sách kề). 
1. Biểu diễn đồ thị bằng ma trận kề 
Ta dùng một mảng hai chiều, chẳng hạn mảng DT, kiểu boolean để biểu diễn các đỉnh 
kề. Nếu đồ thị có n đỉnh thì ta dùng mảng DT kích thước n x n. Giả sử các đỉnh được 
đánh số 1..n thì DT[i,j] = true, nếu có cạnh nối giữa hai đỉnh i và j, ngược lại DT[i,j] = 
false. Nếu đồ thị G là đồ thị vô hướng thì ma trận kề sẽ là ma trận đối xứng. Chẳng 
hạn đồ thị I.1b có biểu diễn ma trận kề như sau: 
j 
i 
1 2 3 4 5 
1 True True True False True 
2 True True False False True 
3 True False True True False
4 False False True True True 
5 True True False True True 
Ở đây ta cũng có thể biểu diễn dùng hai giá trị 0 và 1 để biểu diễn, quy ước 1 tương 
ứng với true còn 0 tương ứng với false. Với cách biểu diễn này thì đồ thị hình I.1a có 
biểu diễn ma trận kề như sau: 
39 
j 
i 
1 2 3 4 5 
1 1 1 1 0 0 
2 0 1 0 0 1 
3 0 0 1 1 0 
4 0 0 0 1 0 
5 1 0 0 1 1 
Trên đồ thị có nhãn thì ma trận kề có thể dùng để lưu trữ nhãn của các cung chẳng hạn 
cung giữa i và j có nhãn a thì DT[i,j] = a. Ví dụ ma trận kề của đồ thị hình I.2 là: 
j 
i 
1 2 3 4 5 
1 0 10 VC 30 100 
2 VC 0 50 VC VC 
3 VC VC 0 VC 10 
4 VC VC 10 0 60 
5 VC VC VC VC 0 
Đối với những cặp đỉnh i, j không có cung nối với nhau ta phải gán cho nó một giá trị 
đặc biệt nào đó để phân biệt với các giá trị có nghĩa khác. Chẳng hạn như trong bài 
toán tìm đường đi ngắn nhất, các giá trị số nguyên biểu diễn cho khoảng cách giữa hai 
thành phố không có cạnh nối ta gán cho nó khoảng cách bằng giá tri VC là một giá trị 
vô cùng lớn, còn khoảng cách từ một đỉnh đến chính nó là 0. 
40 
Bài tập: Hãy viết thủ tục nhập liệu một ma trận kề biểu diễn cho một đồ thị. Dữ liệu 
đầu vào là số đỉnh V, số cạnh E và các cạnh nối hai đỉnh. 
Cách biểu diễn đồ thị bằng ma trận kề cho phép kiểm tra một cách trực tiếp hai đỉnh 
nào đó có thể kề nhau không. Nhưng nó phải mất thời gian duyệt qua toàn bộ mảng để 
xác định tất cả các cạnh trên đồ thị. Thời gian này độc lập với số cạnh và số đỉnh của 
đồ thị. Ngay cả khi số cạnh của đồ thị rất nhỏ thì ta vẫn phải dùng một ma trận nxn để 
lưu trữ. Do vậy, nếu ta cần làm việc thường xuyên với các cạnh của đồ thị thì ta có thể 
phải dùng cách biểu diễn khác cho phù hợp hơn. 
2. Biểu diễn đồ thị bằng danh sách các đỉnh kề. 
Trong cách biểu diễn này, ta sẽ lưu trữ các đỉnh kề với một đỉnh i trong một danh sách 
liên kết theo một thứ tự nào đó. Như vậy ta cần một mảng LIST một chiều có n phần 
tử để biểu diễn cho đồ thị có n đỉnh. LIST[i] là con trỏ trỏ tới danh sách các đỉnh kề 
với đỉnh i. Ví dụ đồ thị hình I.1a có thể biểu diễn như sau: 
1 
2 
3 
4 * 
5 
2 
5 * 
4 * 
1 
3 * 
4 * 
Mảng LIST 
Bài tập: viết thủ tục nhập dữ liệu cho đồ thị biểu diễn bằng danh sách kề. 
IV. Các phép duyệt đồ thị (traversals of Graph) 
Trong khi giải nhiều bài toán được mô hình hóa bằng đồ thị, ta cần đi qua các đỉnh và 
các cung của đồ thị một cách có hệ thống. Việc đi qua các đỉnh của đồ thị một cách có 
hệ thống như vậy gọi là duyệt đồ thị. Có hai phép duyệt đồ thị phổ biến đó là duyệt 
theo chiều sâu, và duyệt theo chiều rộng. 
1. Duyệt theo chiều sâu (Depth-first search) 
Giả sử ta có đồ thị G = (V, E) với các đỉnh ban đầu được đánh dấu là chưa duyệt 
(mảng đánh dấu mang giá trị 0). Từ một đỉnh v nào đó ta bắt đầu duyệt như sau: đánh 
dấu v đã duyệt, với mỗi đỉnh w chưa duyệt kề với v, ta thực hiện đệ qui quá trình trên 
cho w. Sở dĩ cách duyệt này có tên là duyệt theo chiều sâu vì nó sẽ duyệt theo một 
hướng nào đó sâu nhất có thể được. Giải thuật duyệt theo chiều sâu một đồ thị có thể 
được trình bày như sau, trong đó ta dùng một mảng DX có n phần tử để đánh dấu các 
đỉnh của đồ thị là đã duyệt hay chưa. 
41 
//đánh dấu chưa duyệt tất cả các đỉnh 
for (v =1; v <= n; v++) DX[v] = 0; 
Thủ tục duyệt đồ thị theo chiều sâu dfs có thể được viết dạng đệ quy như sau: 
void dfs(đỉnh v) // v thuộc [0..n] 
{ 
 vertex w; 
 DX[v]=1; 
 for (mỗi đỉnh w là đỉnh kề với v) 
 if (DX[w] == 0) 
 dfs(w); 
} 
Ví dụ: duyệt theo chiều sâu đồ thị trong hình I.1.a. Giả sử ta bắt đầu duyệt từ đỉnh 1, 
tức là dfs(1). Giải thuật sẽ đánh dấu 1 đã được duyệt, 1 có hai đỉnh kề là 2 và 3, chọn 
đỉnh đầu tiên trong danh sách các đỉnh kề với 1, đó là 2. Tiếp tục duyệt 2, 2 được đánh 
dấu đã xét, 2 có một đỉnh kề là 5, 5 được đánh dấu đã duyệt, 5 có hai đỉnh kề là 1 và 4, 
nhưng 1 đã được đánh dấu là xét rồi do đó thuật toán thực hiện duyệt tới đỉnh 4 là 
dfs(4). Đến đây, không còn đỉnh nào kề với 4, bây giờ giải thuật sẽ tiếp tục với đỉnh kề 
với 1 mà còn chưa duyệt là 3. Đỉnh 3 không có đỉnh kề nên phép duyệt dfs(3) kết thúc 
vậy dfs(1) cũng kết thúc.Và thứ tự duyệt sẽ là: 1, 2, 5, 4, 3. 
Ví dụ duyệt theo chiều sâu đồ thị hình I.3 bắt đầu từ đỉnh A: duyệt A, A có các đỉnh 
kề là B, C, D, theo tứ tự đó thì B đuợc duyệt. B có một đỉnh kề chưa được duyệt là F, 
nên F được duyệt. F có các đỉnh kề chưa được duyệt là D, G, theo thứ tự đó thì ta 
duyệt D. D có các đỉnh kề chưa được duyệt là C, E, G, theo thứ tự đó thì C được 
duyệt. Các đỉnh kề với C đều đã được duyệt nên giải thuật tiếp tục với E. E có một 
đỉnh kề chưa duyệt là G, vậy ta duyệt G. Lúc này tất cả các đỉnh đều đã được duyệt 
xong. Vậy thứ tự đỉnh được duyệt là ABFDCEG. 
 Hình I.3 
2. Duyệt theo chiều rộng (breadth-first search) 
Giả sử ta có đồ thị G với các đỉnh ban đầu được đánh dấu là chưa duyệt (mảng đánh 
dấu mang giá trị 0). Từ một đỉnh v nào đó ta bắt đầu duyệt như sau: đánh dấu v đã 
được duyệt, kế đến là duyệt tất cả các đỉnh kề với v. Khi ta duyệt một đỉnh v rồi đến 
42 
đỉnh w thì các đỉnh kề của v được duyệt trước các đỉnh kề của w, vì vậy ta dùng một 
hàng đợi để lưu trữ các đỉnh theo thứ tự được duyệt để có thể duyệt các đỉnh kề với 
chúng. Ta cũng dùng mảng một chiều DX để đánh dấu một đỉnh đã duyệt hay chưa. 
Giải thuật duyệt theo chiều rộng được viết dạng lặp như sau: 
//n là số đỉnh của đồ thị 
void bfs(vertex v) // v thuoc [1..n], v là đỉnh bắt đầu duyệt 
{ 
 //đánh dấu chưa duyệt tất cả các đỉnh 
 for (v = 1; v<=n; v++) DX[v] = 0; 
 QUEUE Q;//sử dụng hàng đơi Q 
 vertex x,y; 
 DX[v] = 1; 
 ENQUEUE(v,Q); 
 while !(EMPTY_QUEUE(Q)) 
 { 
 x = DEQUEUE(Q); //lấy x ra khoi Q 
 for (mỗi đỉnh y kề với x) 
 { 
 if (DX[y] ==0) 
 { 
 DX[y] = 1; //duyệt y 
 ENQUEUE(y,Q); 
 } 
 } 
 } 
} 
Ví dụ duyệt theo chiều rộng đồ thị hình I.1.a. Giả sử bắt đầu duyệt từ 1. Đỉnh 1 có ba 
đỉnh kề là 2 và 3. Duyệt 2, 3 và đánh dấu 2, 3 đã duyệt. Tiếp theo là duyệt đến các 
đỉnh kề với 2 có 5. Duyệt 5 và đánh dấu 5 đã đánh, xét tiếp các đỉnh kề với 3, có đỉnh 
4 chưa xét, do đó duyệt 4. Đến đây tất cả các đỉnh đã xét, ta dừng thuật toán. Vậy thứ 
tự duyệt theo chiều rộng đồ thị hình I.1.a là 1, 2, 3, 5, 4 
Ví dụ duyệt theo chiều rộng đồ thị hình I.3. Giả sử bắt đầu duyệt từ A. Duyệt A, kế 
đến duyệt tất cả các đỉnh kề với A, đó là B, C, D theo thứ tự đó. Kế tiếp duyệt các đỉnh 
kề của B, C, D theo thứ tự đó. Vậy các đỉnh được duyệt tiếp theo là F, E, G. Có thể 
minh họa hoạt động của hàng đợi trong phép duyệt trên như sau: 
43 
Duyệt A có nghĩa là đánh dấu đã xét và đưa nó vào hàng đợi: 
Kế đến duyệt tất cả các đỉnh kề với đỉnh đầu hàng mà chưa được duyệt, tức là ta loại 
A khỏi hàng đợi, duyệt B, C, D và đưa chúng vào hàng đợi, bây giờ hàng đợi chứa các 
đỉnh B, C, D. 
Kế đến lấy B ra khỏi hàng đợi và các đỉnh kề với B mà chưa được duyệt, đó là F, sẽ 
được duyệt, F được đẩy vào hàng đợi. 
Kế đến thì C được lấy ra khỏi hàng đợi và các đỉnh kề với C mà chưa được duyệt sẽ 
được duyệt. Không có đỉnh nào như vậy, nên bước này không thêm đỉnh nào được 
duyệt. 
44 
Kế đến thì D được lấy ra khỏi hàng đợi và duyệt các đỉnh kề chưa duyệt của D, tức là 
E, G được duyệt. E, G được đưa vào hàng đợi. 
Tiếp tục, F được lấy ra khỏi hàng đợi. Không có đỉnh nào kề với F mà chưa được 
duyệt. Vậy không duyệt thêm đỉnh nào. 
Tương tự như F, E rồi đến G được lấy ra khỏi hàng. Hàng trở thành rỗng và thuật giải 
kết thúc. 
V. Một số bài toán trên đồ thị 
Phần này sẽ giới thiệu với một số bài toán quan trọng trên đồ thị, như bài toán tìm 
đường đi ngắn nhất, bài toán tìm bao đóng chuyển tiếp, cây bao trùm tối thiểu 
1. Bài toán tìm đường đi ngắn nhất từ một đỉnh của đồ thị 
Cho đồ thị G với tập các đỉnh V và tập các cạnh E (đồ thị có hướng hoặc vô hướng). 
Mỗi cạnh của đồ thị có một nhãn, đó là một giá trị không âm, nhãn này còn gọi là giá 
(cost) của cạnh. Cho trước một đỉnh v xác định, gọi là đỉnh nguồn. Vấn đề là tìm 
đường đi ngắn nhất từ v đến các đỉnh còn lại của G, tức là các đường đi từ v đến các 
đỉnh còn lại với tổng các giá (cost) của các cạnh trên đường đi là nhỏ nhất. Chú ý rằng 
nếu đồ thị có hướng thì đường đi này là có hướng. 
Ta có thể giải bài toán này bằng cách xác định một tập hợp S chứa các đỉnh mà 
khoảng cách ngắn nhất từ nó đến nguồn v đã biết. Khởi đầu S = {v}, sau đó mỗi bước 
ta sẽ thêm vào S các đỉnh mà khoảng cách từ nó đến v là ngắn nhất. Với giả thiết mỗi 
cung có một giá trị không âm thì ta luôn luôn tìm được một đường đi ngắn nhất như 
vậy mà chỉ đi qua các đỉnh đã tồn tại trong S. Để chi tiết hóa thuật giải, giả sử G có n 
đỉnh và nhãn trên mỗi cung được lưu trong mảng hai chiều C, tức C[i,j] là giá (có thể 
xem như độ dài) của cung (i,j), nếu i, j không nối nhau thì C[i,j] = ∞ (VC). Ta dùng 
mảng một chiều L có n phần tử để lưu độ dài của đường đi ngắn nhất từ mỗi đỉnh của 
45 
đồ thị đến v. Khởi đầu khoảng cách này chính là độ dài cạnh (v, i), tức là L[i] = C[v,i]. 
Tại mỗi bước của giải thuật thì L[i] sẽ được cập nhật lại để lưu độ dài đường đi ngắn 
nhất từ đỉnh v đến đỉnh i, đường đi này chỉ đi qua các đỉnh đã có trong S. 
Dưới đây là mô tả giải thuật Dijkstra để giải bài toán trên. 
Kí hiệu: 
• L(v): để chỉ nhãn của đỉnh v, tức là cận trên của chiều dài đường đi ngắn nhất 
từ s0 đến v. 
• d(s0, v): chiều dài đường đi ngắn nhất từ s0 đến v. 
• m(s, v): trong số của cạnh (s,v). 
Mô tả 
Input: G, s0 
Output: d(s0, v), với mọi v khác s0 
• Khởi động: 
 L(v) = ∞ , ∀ v≠ s0; //nhãn tạm thời 
 S = Rỗng; 
• Bước 0 
 d(s0, s0) = L(s0) = 0; 
 S = {s0}; //s0 có nhãn chính thức 
• Bước 1 
- Tính lại nhãn tạm thời L(v), với v∉S 
 Nếu v kề với s0 thì 
 L(v) = Min{L(v), L(s0) + m(s0, v)}; 
- Tìm s1∉S và kề với s0 sao cho: 
 L(s1) = Min{L(v): ∀ v∉S}; // khi đó d(s0, s1) = L(s1) 
- S = S∪ {s1}; //S = {s0, s1}, s1 có nhãn chính thức 
• Bước 2 
- Tính lại nhãn tạm thời L(v), với v∉S 
 Nếu v kề với s1 thì 
 L(v) = Min{L(v), L(s1) + m(s1, v)}; 
- Tìm s2∉S và kề với s1 sao cho: 
 L(s2) = Min{L(v): ∀ v∉S}; // khi đó d(s0, s2) = L(s2) 
 Nếu L(s2) = Min{L(sj), L(sj)+m(sj, s2)} thì đường đi từ s0 đến s2 qua sj là bé 
nhất, và sj là đỉnh kề trước s2 
46 
- S = S∪ {s2}; //S = {s0, s1, s2}, s2 có nhãn chính thức 
• ... 
• Bước i 
- Tính lại nhãn tạm thời L(v), với v∉S 
 Nếu v kề với si-1 thì 
 L(v) = Min{L(v), L(si-1) + m(si-1, v)}; 
- Tìm si∉S và kề với sj, j∈[0,i-1] sao cho: 
 L(si) = Min{L(v): ∀ v∉S}; // khi đó d(s0, si) = L(si) 
 Nếu L(si) = Min{L(sj), L(sj)+m(sj, si)} thì đường đi từ s0 đến si qua sj là bé 
nhất, và sj là đỉnh kề trước si 
- S = S∪ {s2}; //S = {s0, s1, s2...si}, si có nhãn chính thức 
Cài đặt thuật toán Dijkstra 
Để cài đặt thuật giải dễ dàng, ta giả sử các đỉnh của đồ thị được đánh số từ 1 đến n, tức 
là V = {1,..,n} và đỉnh nguồn là 1. Nếu muốn lưu trữ lại các đỉnh trên đường đi ngắn 
nhất để có thể xây dựng lại đường đi này từ đỉnh nguồn đến các đỉnh khác, ta dùng 
một mảng ddnn. Mảng này sẽ lưu ddnn[u] = w với u là đỉnh “trước” đỉnh w trong 
đường đi. 
void Dijkstra(int v, int C[max][max]) 
{ 
 int dnnn[Max];//mảng chứa đường đi ngắn nhất 
 int i, k, min, dht; //dht: đỉnh hiện tại 
 int DX[Max]; //đánh dấu các đỉnh đã đưa vào S 
 int L[Max]; //L[i] chứa chi phí tới đỉnh i 
for (i =1; i<=SoDinh; i++) 
{ 
DX[i] = 0; 
L[i] = VC; //VC: vô cùng 
} 
DX[v] = 1; 
L[v] = 0; 
dht = v; 
int h = 1; 
47 
while(h<SoDinh-1) 
{ 
 min = CV; 
 for(int i=1; i<=SoDinh; i++) 
 { 
 if(DX[i] == 0) 
 { 
 if(L[dht] + C[dht][i] < L[i]) //tính lại nhãn 
 { 
 L[i] = L[dht] + C[dht][i]; 
 dnnn[i] = dht; // gán đỉnh hiện tại bằng đỉnh 
 trước i trên lộ trình 
 } 
 if(L[i] < min) // chọn đỉnh k 
 { 
 min = L[i]; 
 k = i; 
 } 
 } 
 //Tại mỗi bước lặp h, tìm được đường đi ngắn nhất từ s 
 //đến k 
 Xuatddnn(v,k, ddnn); 
 cout<<”\nTrong so: ”<< L[k]; 
 dht = k; // khởi động lại dht 
 DX[dht] = 1; //Đưa nút k vào tập nút đã xét 
 h++; 
 } 
 } 
 } 
Ví dụ: áp dụng thuật giải Dijkstra cho đồ thị hình I.5 
48 
 Hình I.5 
 Kết quả khi áp dụng giải thuật 
Lần lặp S W L[2] L[3] L[4] L[5] 
Khởi đầu {1} - 10 
(1) 
∞ 30 
(1) 
100 
(1) 
1 {1,2} 2 10 
(1) 
60 
(2) 
30 
(1) 
100 
(1) 
2 {1,2,4} 4 10 
(1) 
40 
(4) 
30 
(1) 
90 
(4) 
3 {1,2,3,4} 3 10 
(1) 
40 
(4) 
30 
(1) 
50 
(3) 
4 {1,2,3,4,5} 5 10 
(1) 
40 
(4) 
30 
(1) 
50 
(3) 
 Mảng ddnn có giá trị như sau: 
Từ kết quả trên ta có thể suy ra rằng đường đi ngắn nhất từ đỉnh 1 đến đỉnh 3 là 
1Æ4Æ3 có độ dài là 40. Đường đi ngắn nhất từ 1 đến 5 là 1Æ4Æ3Æ5 có độ dài là 
50. 
Bài tập: 
1. Viết thủ tục xuất đường đi Xuatdnnn(int v, int k, int ddnn[max]). 
2. Cài đặt thuật giải Dijkstra. 
2. Bài toán tìm bao đóng chuyển tiếp. 
Trong một số trường hợp ta chỉ cần xác định có hay không một đường đi nối giữa hai 
đỉnh i,j bất kì. Bây giờ khoảng cách giữa i, j là không quan trọng mà ta chỉ cần biết i,j 
được nối với nhau bởi một cạnh, ngược lại C[i,j]=0 (có nghĩa là false). Lúc này mảng 
49 
A[i,j] không cho khoảng cách ngắn nhất giữa i, j mà nó cho biết là có đường đi từ i 
đến j hay không. A gọi là bao đóng chuyển tiếp trong đồ thị G có biểu diễn ma trận kề 
là C. Giải thuật tìm bao đóng chuyển tiếp hay còn gọi giải thuật Warshall. 
 int A[n,n], C[n,n]; //A là bao đóng chuyển tiếp, C là ma trận kề 
void Warshall() 
{ 
 int i,j,k; 
for (i=1; i<=n; i++) 
 for (j=1; j<=n; j++) 
 A[i-1,j-1] = C[i-1,j-1]; 
for (k=1; k<=n; k++) 
 for (i=1; i<=n; i++) 
 if(A[i,k] != 0) 
 for (j=1; j<=n; j++) 
 if(A[k][j]) 
 A[i,j] = 1; 
} 
3. Bài toán tìm cây bao trùm tối thiểu (minimum-cost spanning tree) 
Giả sử ta có một đồ thị vô hướng G = (V, E). Đồ thị G gọi là liên thông nếu tồn tại 
đường đi giữa hai đỉnh bất kì. Bài toán tìm cây bao trùm tối thiểu (hoặc cây phủ tối 
thiểu) là tìm một tập hợp T chứa các cạnh của một đồ thị liên thông C sao cho V cùng 
với tập các cạnh này cũng là một đồ thị liên thông, tức là (V, T) là một đồ thị liên 
thông. Hơn nữa tổng độ dài của các cạnh trong T là nhỏ nhất. Một thể hiện của bài 
toán này trong thực tế là bài toán thiết lập mạng truyền thông, ở đó các đỉnh là các 
thành phố còn các cạnh của cây bao trùm là đường nối mạng giữa các thành phố. 
Giả sử G có n đỉnh được đánh số từ 1..n. Giải thuật Prim để giải bài toán này như sau: 
Ý tưởng 
- Bắt đầu, tập khởi tạo là U bằng 1 đỉnh nào đó, đỉnh 1 chẳng hạn, U = {1}, T = 
U. 
- Sau đó ta lặp lại cho đến khi U = V, tại mỗi bước lặp ta chọn cạnh nhỏ nhất 
(u,v) sao cho u ∈U, v∈V-U. Thêm v vào U và (u, v) vào T. Khi thuật giải kết 
thúc thì (U,T) là một cây phủ tối tiểu. 
Mô tả thuật toán 
• Input: G=(V,E) 
• Output: T = (V, ?) là nhỏ nhất. 
50 
• Khởi động: 
- U ⊂V 
- T = (U,.) = Rỗng; //đồ thị rỗng 
- U = {1}; 
• Trong khi (U≠ V) 
Tìm cạnh (u,v) có trọng số nhỏ nhất với u∈U, v∈V. Thêm đỉnh v này vào U, 
thêm (u,v) vào T 
Cài đặt 
Để tiến hành cài đặt thuật toán, ta cần mô tả dữ liệu. Đồ thị có trọng số được biểu 
diễn thành một ma trận kề C[n,n]. 
Khi tìm cạnh có trọng số nhỏ nhất nối một đỉnh trong U và một đỉnh ngoài U tại 
mỗi bước, ta dùng hai mảng để lưu trữ: 
- Mảng closest[], với i ∈V\U thì closest[i]∈U là đỉnh kề gần i nhất. 
- Mảng lowcost[i] lưu trọng số của cạnh (i, closest[i]) 
- Mảng daxet đánh đấu đỉnh đã được xét chưa 
Tại mỗi bước ta duyệt mảng lowcost để tìm đỉnh closest[k] ∈U sao cho trọng số 
(k, closest[k]) = lowcost[k] là nhỏ nhất. Khi tìm được, ta in cạnh (closest[k],k), cập 
nhật vào các mảng closest và lowcost, và có k thêm vào U. Khi ta tìm được một 
đỉnh k cho cây bao trùm, ta cho daxet[k] = DX là đánh dấu đã xét. 
#define VC 10000 //định nghĩa giá trị vô cùng 
#define DX 1 //định nghĩa giá trị khi đỉnh đã được xét 
... 
void Prim(int C[max][max]) 
{ 
 double lowcost[Max]; 
 int closest[Max]; 
 int daxet[Max]; 
 int i,j,k,Min; 
 //bắt đầu từ đỉnh số 1 
 for(i=2; i<=n; i++) 
 { 
 lowcost[i] = C[1][i]; 
 closest[i] = 1; 
 daxet[i] = 0; 
51 
 } 
 for(i=2; i<=n; i++) 
 { 
 Min = lowcost[2]; 
 k = 2; 
 for(j=3; j<=n; j++) 
 { 
 if(!daxet[j] && lowcost[j] < Min) 
 { 
 Min = lowcost[j]; 
 k = j; 
 } 
 } 
 daxet[k] = DX; 
 //Khởi động lại chosest[], lowcost[] 
 for(j=2; j<=n; j++) 
 if(c[k][j]<lowcost[j] && !daxet[j]) 
 { 
 lowcost[j] = c[k][j]; 
 closest[j] = k 
 } 
 } 
} 
Ví dụ: áp dụng giải thuật Prim để tìm cây bao trùm tối thiểu của đồ thị liên thông hình 
I.6 
Ma trận kề: 
52 
 1 2 3 4 5 6 
1 0 6 1 5 VC VC 
2 6 0 5 VC 3 VC 
3 1 5 0 5 6 4 
4 5 VC 5 0 VC 2 
5 VC 3 6 VC 0 6 
6 VC VC 4 2 6 0 
 Khởi tạo 
 Mảng lowcost 
2 3 4 5 6 
6 1 5 VC VC 
 Mảng closest 
2 3 4 5 6 
1 1 1 1 1 
 Mảng daxet 
2 3 4 5 6 
0 0 0 0 0 
 Bước 1: tìm được Min = 1, k = 3, mảng lowcost và closest cập nhật như sau: 
 Mảng lowcost 
2 3 4 5 6 
5 1 5 6 4 
Mảng closest 
2 3 4 5 6 
3 1 1 3 3 
 Mảng daxet 
2 3 4 5 6 
0 1 0 0 0 
 Bước 2: tìm được Min = 4, k = 6 
53 
 Mảng lowcost 
2 3 4 5 6 
5 1 2 6 4 
 Mảng closest 
2 3 4 5 6 
3 1 6 3 3 
 Mảng daxet 
2 3 4 5 6 
0 1 0 0 1 
 Bước 3: tìm được Min = 2, k = 4 
 Mảng lowcost 
2 3 4 5 6 
5 1 2 6 4 
 Mảng closest 
2 3 4 5 6 
3 1 6 3 3 
 Mảng daxet 
2 3 4 5 6 
0 1 1 0 1 
 Bước 4: tìm được Min = 5, k = 2 
Mảng lowcost 
2 3 4 5 6 
5 1 2 3 4 
 Mảng closest 
2 3 4 5 6 
3 1 6 2 3 
 Mảng daxet 
54 
2 3 4 5 6 
1 1 1 0 1 
 Bước 5: tìm Min = 3, k = 5 
 Mảng lowcost 
2 3 4 5 6 
5 1 2 3 4 
 Mảng closest 
2 3 4 5 6 
3 1 6 2 3 
 Mảng daxet 
2 3 4 5 6 
1 1 1 1 1 
Bài tập 
1. Viết biểu diễn đồ thị I.7 bằng: 
- Ma trận kề. 
- Danh sách các đỉnh kề. 
2. Duyệt đồ thị hình I.7 (xét các đỉnh theo thứ tự a,b,c...) 
- Theo chiều rộng bắt đầu từ a. 
- Theo chiều sâu bắt đầu từ f 
3. Áp dụng giải thuật Dijkstra cho đồ thị hình I.7, với đỉnh nguồn là a 
4. Viết biểu diễn đồ thị I.8 bằng: 
55 
- Ma trận kề. 
- Danh sách các đỉnh kề. 
5. Duyệt đồ thị hình I.8 (xét các đỉnh theo thứ tự A,B,C...) 
- Theo chiều rộng bắt đầu từ A. 
- Theo chiều sâu bắt đầu từ B. 
6. Áp dụng giải thuật Dijkstra cho đồ thị hình I.8, với đỉnh nguồn là A. 
7. Tìm cây bao trùm tối thiểu của đồ thị hình I.8 bằng giải thuật Prim. 
8. Cài đặt đồ thị có hướng bằng ma trận kề rồi viết các giải thuật: 
- Duyệt theo chiều rộng. 
- Duyệt theo chiều sâu. 
- Tìm đường đi ngắn nhất từ một đỉnh cho trước (Dijkstra). 
9. Cài đặt đồ thị có hướng bằng danh sách các đỉnh kề rồi viết các giải thuật duyệt theo 
chiều rộng.