Giáo trình Cấu trúc dữ liệu - Nguyễn Văn Linh

1 
Với cách biểu diễn đồ thị bằng ma trận kề như trên chúng ta có thể định nghĩa chỉ số của 
đỉnh là số nguyên chỉ đỉnh đó (theo cách đánh số các đỉnh) và ta cài đặt các phép toán 
FIRST, NEXT và VERTEX như sau: 
const null=0; 
int A[n,n]; //mảng biểu diễn ma trận kề 
 Trang 136
Cấu trúc dữ liệu Chương V: Đồ thị 
int FIRST(int v) //trả ra chỉ số [1..n] của đỉnh đầu tiên 
kề với v ∈ 1..n 
{ 
int i; 
 for (i=1; i<=n; i++) 
 if (a[v-1,i-1] == 1) 
return (i); //trả ra chỉ số đỉnh của đồ thị 
 return (null); 
 } 
int NEXT(int v; int i) //trả ra đỉnh [1..n] sau đỉnh i 
mà kề với v; i, v ∈ 1..n 
{ 
int j; 
for (j=i+1; j<=n; j++) 
 if (a[v-1,j-1] == 1) 
return(j) 
 return(null); 
} 
Còn VERTEX(i) chỉ đơn giản là trả ra chính i. 
Vòng lặp trên các đỉnh kề với v có thể cài đặt như sau 
i=FIRST(v); 
while (inull) 
{ w = VERTEX(i); 
 //thao tác trên w 
 i =NEXT(v,i); 
} 
 Trang 137
Cấu trúc dữ liệu Chương V: Đồ thị 
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ì A[i,j]=a. Ví dụ ma trận kề của đồ thị hình V.2 là:
j 
i 
1 2 3 4 
1 50 45 
2 50 10 75 
3 45 10 30 
4 75 30 
Ở đây các cặp đỉnh không có cạnh nối thì ta để trống, nhưng trong các ứng dụng ta có thể 
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ố thì các cặp thành phố không có cạnh nối ta gán cho nó khoảng cách 
bằng µ, còn khoảng cách từ một đỉnh đến chính nó là 0. 
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ó 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ả số 
cạnh của đồ thị rất nhỏ chúng ta cũng phải cần một mảng nxn phần tử để 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 thích 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 HEAD một chiều có n phần tử để 
biểu diễn cho đồ thị có n đỉnh. HEAD[i] là con trỏ trỏ tới danh sách các đỉnh kề với đỉnh i. 
ví dụ đồ thị hình V.1a có biểu diễn như sau: 
1 2 3 * 
2 4 * 
3 2 * 
4 3 * 
Mảng HEAD 
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 hoá 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, tương tự như duyệt tiền tự một cây, và duyệt theo chiều rộng, tương tự như phép duyệt 
cây theo mức. 
 Trang 138
Cấu trúc dữ liệu Chương V: Đồ thị 
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 (unvisited). 
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 mark 
có n phần tử để đánh dấu các đỉnh của đồ thị là đã duyệt hay chưa. 
//đánh dấu chưa duyệt tất cả các đỉnh 
for (v =1; v <=n; v++) mark[v-1]=unvisited; 
//duyệt theo chiều sâu từ đỉnh đánh số 1 
for (v = 1; v<=n; v++) 
 if (mark[v-1] == unvisited) 
 dfs(v); //duyệt theo chiều sâu đỉnh v 
Thủ tục dfs ở trong giải thuật ở trên có thể được viết như sau: 
void dfs(vertex v) // v ∈ [1..n] 
{ 
vertex w; 
 mark[v-1]=visited; 
 for (mỗi đỉnh w là đỉnh kề với v) 
 if (mark[w-1] == unvisited) 
 dfs(w); 
} 
Ví dụ: Duyệt theo chiều sâu đồ thị trong hình V.3. Giả sử ta bắt đầu duyệt từ đỉnh A, tức 
là dfs(A). Giải thuật sẽ đánh dấu là A đã được duyệt, rồi chọn đỉnh đầu tiên trong danh sách 
các đỉnh kề với A, đó là G. Tiếp tục duyệt đỉnh G, G có hai đỉnh kề với nó là B và C, theo 
thứ tự đó thì đỉnh kế tiếp được duyệt là đỉnh B. B có một đỉnh kề đó là A, nhưng A đã được 
duyệt nên phép duyệt dfs(B) đã hoàn tất. Bây giờ giải thuật sẽ tiếp tục với đỉnh kề với G mà 
 Trang 139
Cấu trúc dữ liệu Chương V: Đồ thị 
còn chưa duyệt là C. C không có đỉnh kề nên phép duyệt dfs(C) kết thúc vậy dfs(A) cũng 
kết thúc. Còn lại 3 đỉnh chưa được duyệt là D,E,F và theo thứ tự đó thì D được duyệt, kế 
đến là F. Phép duyệt dfs(D) kết thúc và còn một đỉnh E chưa được duyệt. Tiếp tục duyệt E 
và kết thúc. Nếu ta in các đỉnh của đồ thị trên theo thứ tự được duyệt ta sẽ có danh sách sau: 
AGBCDFE. 
Ví dụ duyệt theo chiều sâu đồ thị hình V.4 bắt đầu từ đỉnh A: Duyệt A, A có các đỉnh kề 
là B,C,D; theo thứ tự đó thì B được duyệt. B có 1 đỉnh kề chưa duyệt là F, nên F được 
duyệt. F có các đỉnh kề chưa duyệt là D,G; theo thứ tự đó thì ta duyệt D. D có các đỉnh kề 
chưa 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 được tiếp tục duyệt 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 nút đều đã được duyệt nên đồ thị đã được duyệt xong. Vậy thứ tự các đỉnh 
được duyệt là ABFDCEG. 
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 (unvisited). 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 đỉ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 để lưu trữ các nút 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 mark để đánh 
dấu một nút là đã duyệt hay chưa, tương tự như duyệt theo chiều sâu. Giải thuật duyệt theo 
chiều rộng được viết như sau: 
//đánh dấu chưa duyệt tất cả các đỉnh 
for (v = 1; v<= n; v++) mark[v-1] = unvisited; 
//n là số đỉnh của đồ thị 
//duyệt theo chiều rộng từ đỉnh đánh số 1 
for (v = 1; v<=n; v++) 
 if (mark[v-1] == unvisited) 
 bfs(v); 
Thủ tục bfs được viết như sau: 
void bfs(vertex v) // v ∈ [1..n] 
 Trang 140
Cấu trúc dữ liệu Chương V: Đồ thị 
{ 
QUEUE of vertex Q; 
vertex x,y; 
 mark[v-1] = visited; 
 ENQUEUE(v,Q); 
 while !(EMPTY_QUEUE(Q)) 
{
 x = FRONT(Q); 
 DEQUEUE(Q); 
 for (mỗi đỉnh y kề với x) 
 if (mark[y-1] == unvisited) 
 { 
 mark[y-1] = visited; {duyệt y} 
 ENQUEUE(y,Q); 
 }
 } 
} 
Ví dụ duyệt theo chiều rộng đồ thị hình V.3. Giả sử bắt đầu duyệt từ A. A chỉ có một 
đỉnh kề G, nên ta duyệt G. Kế đến duyệt tất cả các đỉnh kề với G; đó là B,C. Sau đó duyệt 
tất cả các đỉnh kề với B, C theo thứ tự đó. Các đỉnh kề với B, C đều đã được duyệt, nên ta 
tiếp tục duyệt các đỉnh chưa được duyệt. Các đỉnh chưa được duyệt là D, E, F. Duyệt D, kế 
đến là F và cuối cùng là E. Vậy thứ tự các đỉnh được duyệt là: AGBCDFE. 
Ví dụ duyệt theo chiều rộng đồ thị hình V.4. 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 là duyệt các đỉnh kề của 
B, C, D theo thứ tự đó. Vậy các nút được duyệt tiếp theo là F, E,G. Có thể minh hoạ hoạt 
động của hàng trong phép duyệt trên như sau: 
Duyệt A nghĩa là đánh dấu visited và đưa nó vào hàng: 
A 
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, duyệt B, C, D và đưa chúng vào hàng, bây giờ hàng chứa các đỉnh B, C, D. 
 Trang 141
Cấu trúc dữ liệu Chương V: Đồ thị 
B 
C 
D 
Kế đến B được lấy ra khỏi hàng và các đỉnh kề với B mà chưa được duyệt, đó là F, sẽ 
được duyệt, và F được đưa vào hàng đợi. 
C 
D 
F 
Kế đến thì C được lấy ra khỏi hàng 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 có thêm đỉnh nào được duyệt. 
D 
F 
Kế đến thì D được lấy ra khỏi hàng 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. 
F 
E 
G 
 Trang 142
Cấu trúc dữ liệu Chương V: Đồ thị 
Tiếp tục, F được lấy ra khỏi hàng. 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. 
E 
G 
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à giải thuật 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 các bạn 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... Các bài 
toán này cùng với các giải thuật của nó đã được trình bày chi tiết trong giáo trình về Qui 
Hoạch Động, vì thế ở đây ta không đi vào quá chi tiết các giải thuật này. Phần này chỉ xem 
như là phần nêu các ứng dụng cùng với giải thuật để giải quyết các bài toán đó nhằm giúp 
bạn đọc có thể vận dụng được các giải thuật vào việc cài đặt để giải các bài toán nêu trên. 
1. Bài toán tìm đuờng đi ngắn nhất từ một đỉnh của đồ thị (the single source 
shorted path problem) 
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à đường đi 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 đỉnh nguồn v đã biết. Khởi đầu S={v}, sau đó tại 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á 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 hoá giải thuật, 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 là C[i,j] là giá (có thể xem như độ dài) của cung 
(i,j), nếu i và j không nối nhau thì C[i,j]=∞. Ta dùng mảng 1 chiều D có n phần tử để lưu độ 
dài của đường đi ngắn nhất từ mỗi đỉnh của đồ thị đến v. Khởi đầu khoảng cách này chính 
là độ dài cạnh (v,i), tức là D[i]=C[v,i]. Tại mỗi bước của giải thuật thì D[i] sẽ được cập 
nhật lại để lưu độ dài đường đi ngắn nhất từ đỉnh v tới đỉnh i, đường đi này chỉ đi qua các 
đỉnh đã có trong S. 
Để cài đặt giải thuật 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. Dưới dây là giải thuật Dijkstra để giải bài toán trên. 
void Dijkstra() 
{ 
 Trang 143
Cấu trúc dữ liệu Chương V: Đồ thị 
 S = [1]; //Tập hợp S chỉ chứa một đỉnh nguồn 
 for (i =2; i<=n; i++) 
 D[i-1] = C[0,i-1]; //khởi đầu các giá trị cho D 
 for (i=1; i<n; i++) 
 { 
 Lấy đỉnh w trong V-S sao cho D[w-1] nhỏ nhất; 
 Thêm w vào S; 
 for (mỗi đỉnh u thuộc V-S) 
 D[u-1] = min(D[u-1], D[w-1] + C[w-1,u-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 P. Mảng này sẽ lưu P[u]=w với u 
là đỉnh "trước" đỉnh w trong đường đi. Lúc khởi đầu P[u]=1 với mọi u. 
Giải thuật Dijkstra được viết lại như sau: 
void Dijkstra() 
{
 S =[1]; //S chỉ chứa một đỉnh nguồn 
 for(i=2; i<=n; i++) 
 { 
 P[i-1] =1; //khởi tạo giá trị cho P 
 D[i-1] =C[0,i-1]; //khởi đầu các giá trị cho D 
 } 
 for (i=1; i<n; i++) 
 { 
 Lấy đỉnh w trong V-S sao cho D[w-1] nhỏ nhất; 
 Thêm w vào S; 
 for (mỗi đỉnh u thuộc V-S) 
 if (D[w-1] + C[w-1,u-1] < D[u-1]) 
 Trang 144
Cấu trúc dữ liệu Chương V: Đồ thị 
 { 
 D[u-1] =D[w-1] + C[w-1,u-1]; 
 P[u-1] =w; 
 } 
 } 
} 
Ví dụ: áp dụng giải thuật Dijkstra cho đồ thị hình V.5 
Kết quả khi áp dụng giải thuật 
Lần lặp S W D[2] D[3] D[4] D[5]
Khởi đầu {1} - 10 ∞ 30 100
1 {1,2} 2 10 60 30 100
2 {1,2,4} 4 10 40 30 90 
3 {1,2,3,4} 3 10 40 30 50 
4 {1,2,3,4,5} 5 10 40 30 50 
Mảng P có giá trị như sau: 
P 1 2 3 4 5 
 1 4 1 3 
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 
50. 
2. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh 
Giả sử đồ thị G có n đỉnh được đánh số từ 1 đến n. Khoảng cách hay giá giữa các cặp đỉnh 
được cho trong mảng C[i,j]. Nếu hai đỉnh i,j không được nối thì C[i,j]= ¥. Giải thuật Floyd 
xác định đường đi ngắn nhất giữa hai cặp đỉnh bất kỳ bằng cách lặp k lần, ở lần lặp thứ k sẽ 
 Trang 145
Cấu trúc dữ liệu Chương V: Đồ thị 
xác định khoảng cách ngắn nhất giữa hai đỉnh i,j theo công thức: Ak[i,j]=min(Ak-1[i,j], Ak-
1[i,k]+Ak-1[k,j]). Ta cũng dùng mảng P để lưu các đỉnh trên đường đi. 
float A[n,n], C[n,n]; 
int P[n,n]; 
void Floyd() 
{ 
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]; 
 P[i-1,j-1]=0; 
} 
 for (i=1; i<=n; i++) 
 A[i-1,i-1]=0; 
 for (k=1; k<=n; k++) 
 for (i=1; i<=n; i++) 
 for (j=1; j<=n; j++) 
 if (A[i-1,k-1] + A[k-1,j-1] < A[i-1,j-1) 
{
 A[i-1,j-1] = A[i-1,k-1] + A[k-1,j-1]; 
 P[i-1,j-1] = k; 
 } 
}
3. Bài toán tìm bao đóng chuyển tiếp (transitive closure) 
Trong một số trường hợp ta chỉ cần xác định có hay không có đường đi nối giữa hai đỉnh i,j 
bất kỳ. Giải thuật Floyd có thể đặc biệt hoá để giải bài toán này. Bây giờ khoảng cách giữa 
 Trang 146
Cấu trúc dữ liệu Chương V: Đồ thị 
i,j là không quan trọng mà ta chỉ cần biết i,j có nối nhau không do đó ta cho C[i,j]=1 (~true) 
nếu i,j được nối nhau bởi một cạnh, ngược lại C[i,j]=0 (~false). Lúc này mảng 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 của đồ thị G có biểu diễn ma trận kề là C. Giải thuật Floyd sửa 
đổi như trên gọi là giải thuật Warshall. 
int A[n,n], C[n,n]; 
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++) 
 for (j=1; j<=n; j++) 
if (A[i-1,j-1] == 0) then 
A[i-1,j-1] =A[i-1,k-1] && A[k-1,j-1]; 
} 
4. 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 G 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á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ố 1..n. Giải thuật Prim để giải bài toán này như sau: 
Bắt đầu, tập ta khởi tạo tập 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 ∈ V-U. Thêm v vào U và (u,v) vào T. Khi giải thuật kết thúc thì (U,T) là một 
cây phủ tối tiểu. 
 Trang 147
Cấu trúc dữ liệu Chương V: Đồ thị 
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 
V.6. 
¾ Bước khởi đầu: U={1}, T=∅. 
¾ Bước kế tiếp ta có cạnh (1,3)=1 là cạnh ngắn nhất thoả mãn điều kiện trong giải 
thuật Prim nên: U={1,3}, T={(1,3)}. 
¾ Kế tiếp thì cạnh (3,6)=4 là cạnh ngắn nhất thoả mãn điều kiện trong giải thuật Prim 
nên: U={1,3,6}, T={(1,3),(3,6)}. 
¾ Kế tiếp thì cạnh (6,4)=2 là cạnh ngắn nhất thoả mãn điều kiện trong giải thuật Prim 
nên: U={1,3,6,4}, T={(1,3),(3,6),(6,4)}. 
¾ Tiếp tục, cạnh (3,2)=5 là cạnh ngắn nhất thoả mãn điều kiện trong giải thuật Prim 
nên: U={1,3,6,4,2}, T={(1,3),(3,6),(6,4),(3,2)}. 
¾ Cuối cùng, cạnh (2,5)=3 là cạnh ngắn nhất thoả mãn điều kiện trong giải thuật Prim 
nên: U={1,3,6,4,2,5}, T={(1,3),(3,6),(6,4),(3,2),(2,5)}. Giải thuật dừng và ta có cây 
bao trùm như trong hình V.7. 
Giải thuật Prim được viết lại như sau: 
void Prim(graph G, set_of_edges *T) 
{ 
 set_of_vertices U; //tập hợp các đỉnh 
 vertex u,v; //u,v là các đỉnh 
 T = ∅; 
 U = [1]; 
 Trang 148
Cấu trúc dữ liệu Chương V: Đồ thị 
 while (U≠V) do // V là tập hợp các đỉnh của G 
 { 
gọi (u,v) là cạnh ngắn nhất sao cho u ∈ U và v ∈ V-U; 
 U = U ∪ [v]; 
 T = T ∪ [(u,v)]; 
 } 
} 
Bài toán cây bao trùm tối thiểu còn có thể được giải bằng giải thuật Kruskal như sau: 
Khởi đầu ta cũng cho T= ∅ giống như trên, ta thiết lập đồ thị khởi đầu G'=(V,T). 
Xét các cạnh của G theo thứ tự độ dài tăng dần. Với mỗi cạnh được xét ta sẽ đưa nó vào T 
nếu nó không làm cho G' có chu trình. 
Ví dụ áp dụng giải thuật Kruskal để tìm cây bao trùm cho đồ thị hình V.6. 
Các cạnh của đồ thị được xếp theo thứ tự tăng dần là. 
(1,3)=1, (4,6)=2, (2,5)=3, (3,6)=4, (1,4)=(2,3)=(3,4)=5, (1,2)=(3,5)= (5,6)=6. 
Ò Bước khởi đầu T= ∅ 
Ò Lần lặp 1: T={(1,3)} 
Ò Lần lặp 2: T={(1,3),(4,6)} 
Ò Lần lặp 3: T={(1,3),(4,6),(2,5)} 
Ò Lần lặp 4: T={(1,3),(4,6),(2,5),(3,6)} 
Ò Lần lặp 5: 
 Cạnh (1,4) không được đưa vào T vì nó sẽ tạo ra chu trình 1,3,6,4,1. 
 Kế tiếp cạnh (2,3) được xét và được đưa vào T. 
T={(1,3),(4,6),(2,5),(3,6),(2,3)} 
Không còn cạnh nào có thể được đưa thêm vào T mà không tạo ra chu trình. Vậy ta có cây 
bao trùm tối thiểu cũng giống như trong hình V.7. 
 Trang 149
Cấu trúc dữ liệu Chương V: Đồ thị 
BÀI TẬP 
1. Viết biểu diễn đồ thị V.8 bằng: 
- Ma trận kề. 
- Danh sách các đỉnh kề. 
2. Duyệt đồ thị hình V.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ừ f 
3. Áp dụng giải thuật Dijkstra cho đồ thị hình V.8, với đỉnh nguồn là 
a. 
4. Viết biểu diễn đồ thị V.9 bằng: 
 Ma trận kề. 
 Danh sách các đỉnh kề. 
5. Duyệt đồ thị hình V.9 (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 V.9, với đỉnh nguồn là A. 
7. Tìm cây bao trùm tối thiểu của đồ thị hình V.9 bằng 
 Giải thuật Prim. 
 Giải thuật Kruskal. 
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). 
 Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh (Floyd). 
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. 
 Trang 150
Cấu trúc dữ liệu Chương V: Đồ thị 
 Duyệt theo chiều sâu. 
10. Cài đặt đồ thị vô 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). 
 Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh (Floyd). 
 Tìm cây bao trùm tối thiểu (Prim, Kruskal). 
 Cài đặt thuật toán Greedy cho bài toán tô màu đồ thị (Gợi ý: xem giải thuật trong 
chương 1) 
11. Cài đặt đồ thị vô 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. 
 Duyệt theo chiều sâu. 
12. Hãy viết một chương trình, trong đó, cài đặt đồ thị vô hướng bằng cấu trúc ma trận 
kề rồi viết các thủ tục/hàm sau: 
Nhập toạ độ n đỉnh của đồ thị. 
Giả sử đồ thị là đầy đủ, tức là hai đỉnh bất kỳ đều có cạnh nối, và giả sử giá của mỗi cạnh 
là độ dài của đoạn thẳng nối hai cạnh. Hãy tìm: 
Đường đi ngắn nhất từ một đỉnh cho trước (Dijkstra). 
Đường đi ngắn nhất giữa tất cả các cặp đỉnh (Floyd). 
Cây bao trùm tối thiểu (Prim, Kruskal). 
Thể hiện đồ thị lên màn hình đồ hoạ, các cạnh thuộc cây bao trùm tối thiểu được vẽ bằng 
một màu khác với các cạnh khác. 
 Trang 151