Chương 6: Các thuật toán tìm kiếm trên đồ thị
CHƯƠNG VI: CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ
Có nhiều thuật toán trên đồ thị được xây dựng để duyệt tất cả các đỉnh của đồ thị sao cho
mỗi đỉnh được viếng thăm đúng một lần. Những thuật toán như vậy được gọi là thuật toán tìm
kiếm trên đồ thị. Chúng ta cũng sẽ làm quen với hai thuật toán tìm kiếm cơ bản, đó là duyệt theo
chiều sâu DFS (Depth First Search) và duyệt theo chiều rộng BFS (Breath First Search). Trên cơ
sở của hai phép duyệt cơ bản, ta có thể áp dụng chúng để giải quyết một số bài toán quan trọng
của lý thuyết đồ thị. Tóm lại, những nội dung chính được đề cập trong chương này bao gồm:
9 Thuật toán tìm kiếm theo chiều sâu trên đồ thị.
9 Thuật toán tìm kiếm theo chiều rộng trên đồ thị.
9 Tìm các thành phần liên thông của đồ thị.
9 Tìm đường đi giữa hai đỉnh bất kì của đồ thị.
9 Tìm đường đi và chu trình Euler
9 Tìm đường đi và chu trình Hamilton
Bạn đọc có thể tìm hiểu sâu hơn về tính đúng đắn và độ phức tạp của các thuật toán trong
các tài liệu [1] và [2].
6.1. THUẬT TOÁN TÌM KIẾM THEO CHIỀU SÂU (DFS)
Tư tưởng cơ bản của thuật toán tìm kiếm theo chiều sâu là bắt đầu tại một đỉnh v
0
nào đó,
chọn một đỉnh u bất kỳ kề với v
0
và lấy nó làm đỉnh duyệt tiếp theo. Cách duyệt tiếp theo được
thực hiện tương tự như đối với đỉnh v
0
với đỉnh bắt đầu là u.
Để kiểm tra việc duyệt mỗi đỉnh đúng một lần, chúng ta sử dụng một mảng chuaxet[] gồm
n phần tử (tương ứng với n đỉnh), nếu đỉnh thứ i đã được duyệt, phần tử tương ứng trong mảng
chuaxet[] có giá trị FALSE. Ngược lại, nếu đỉnh chưa được duyệt, phần tử tương ứng trong mảng
có giá trị TRUE. Thuật toán có thể được mô tả bằng thủ tục đệ qui DFS () trong đó: chuaxet - là
mảng các giá trị logic được thiết lập giá trị TRUE.

13
12
Hình 6.1. Đồ thị vô hướng G.

Đỉnh bắt đầu duyệt Các đỉnh đã duyệt Các đỉnh chưa duyệt
DFS(1) 1 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
DFS(2) 1, 2 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
DFS(4) 1, 2, 4 3, 5, 6, 7, 8, 9, 10, 11, 12, 13
DFS(3) 1,2,4, 3 5, 6, 7, 8, 9, 10, 11, 12, 13
DFS(6) 1,2,4,3, 6 5, 7, 8, 9, 10, 11, 12, 13
DFS(7) 1,2,4,3, 6,7 5, 8, 9, 10, 11, 12, 13
DFS(8) 1,2,4,3, 6,7,8 5, 9, 10, 11, 12, 13
DFS(10) 1,2,4,3, 6,7,8,10 5, 9, 11, 12, 13

120
Chương 6: Các thuật toán tìm kiếm trên đồ thị
DFS(5) 1,2,4,3, 6,7,8,10,5 9, 11, 12, 13
DFS(9) 1,2,4,3, 6,7,8,10,5,9 11, 12, 13
DFS(13) 1,2,4,3, 6,7,8,10,5,9,13 11, 12
DFS(11) 1,2,4,3, 6,7,8,10,5,9,13,11 12
DFS(11) 1,2,4,3, 6,7,8,10,5,9,13,11,12
φ

Kết quả duyệt: 1, 2, 4, 3, 6, 7, 8, 10, 5, 9, 13, 11, 12
Dưới đây là văn bản chương trình. Trong đó các hàm:
void Init(int G[][MAX], int *n): dùng để đọc dữ liệu là từ tệp DFS.IN là biểu diễn của đồ
thị dưới dạng ma trận kề như đã đề cập trong bài tập 5.4. A là ma trận vuông lưu trữ biểu diễn của
đồ thị
void DFS(int G[][MAX], int n, int v, int chuaxet[]): là thuật toán duyệt theo chiều sâu với
đồ thị G gồm n đỉnh và đỉnh bắt đầu duyệt là v.

void DFS(int G[][MAX], int n, int v, int chuaxet[]){
int u;
printf("%3d",v);chuaxet[v]=FALSE;
for(u=1; u<=n; u++){
if(G[v][u]==1 && chuaxet[u])
DFS(G,n, u, chuaxet);
}
}
void main(void){
int G[MAX][MAX], n, chuaxet[MAX];
Init(G, &n);
for(int i=1; i<=n; i++)
chuaxet[i]=TRUE;
printf("\n\n");
for(i=1; i<=n;i++)
if(chuaxet[i])
DFS( G,n, i, chuaxet);
getch();
}

6.2. THUẬT TOÁN TÌM KIẾM THEO CHIỀU RỘNG (Breadth First Search)
Để ý rằng, với thuật toán tìm kiếm theo chiều sâu, đỉnh thăm càng muộn sẽ trở thành đỉnh
sớm được duyệt xong. Đó là kết quả tất yếu vì các đỉnh thăm được nạp vào stack trong thủ tục đệ
qui. Khác với thuật toán tìm kiếm theo chiều sâu, thuật toán tìm kiếm theo chiều rộng thay thế
việc sử dụng stack bằng hàng đợi queue. Trong thủ tục này, đỉnh được nạp vào hàng đợi đầu tiên
là v, các đỉnh kề với v ( v
1
, v
2
,..., v

for (u=1; u≤n; u++)
chuaxet[u] = TRUE;
for (u∈V )
if (chuaxet[u] )
BFS(u);
}

123
Chương 6: Các thuật toán tìm kiếm trên đồ thị
Ví dụ. Áp dụng thuật toán tìm kiếm theo chiều rộng với đồ thị trong hình 6.2 sau:
2 6
8
7
1 4 5
3 10
11 9

12 13

Hình 6.2. Đồ thị vô hướng G=<V,E>

Các đỉnh đã duyệt Các đỉnh trong hàng đợi Các đỉnh còn lại
φ φ
1,2,3,4,5,6,7,8,9,10,11,12,13
1 2, 3, 11 4,5,6,7,8,9,10,12,13
1, 2 3, 11, 4, 6 5,7,8,9,10,12,13
1, 2, 3 11, 4, 6 5,7,8,9,10,12,13

fp=fopen("BFS.IN", "r");
if(fp==NULL){
printf("\n Khong co file input");
delay(2000);return;
}
fscanf(fp,"%d", n);
printf("\n So dinh do thi:%d",*n);
printf("\n Ma tran ke cua do thi:");
for(i=1; i<=*n;i++){
printf("\n");
for(j=1; j<=*n;j++){
fscanf(fp,"%d", &G[i][j]);
printf("%3d", G[i][j]);
}
}
for(i=1; i<=*n;i++) chuaxet[i]=0;
}
void BFS(int G[][MAX], int n, int i, int chuaxet[], int QUEUE[MAX]){
int u, dauQ, cuoiQ, j;
dauQ=1; cuoiQ=1;QUEUE[cuoiQ]=i;chuaxet[i]=FALSE;
/* thiết lập hàng đợi với đỉnh đầu là i*/
while(dauQ<=cuoiQ){
u=QUEUE[dauQ];

125
Chương 6: Các thuật toán tìm kiếm trên đồ thị
printf("%3d",u);dauQ=dauQ+1; /* duyệt đỉnh đầu hàng đợi*/
for(j=1; j<=n;j++){
if(G[u][j]==1 && chuaxet[j] ){
cuoiQ=cuoiQ+1;

126
Chương 6: Các thuật toán tìm kiếm trên đồ thị
void BFS(int u){
queue = φ;
u <= queue; /*nạp u vào hàng đợi*/
solt = solt+1; chuaxet[u] = solt; /*solt là biến toàn cục thiết lập giá trị 0*/
while (queue ≠ φ ) {
queue<=p; /* lấy p ra từ stack*/
for v ∈ ke(p) {
if (chuaxet[v] ) {
v<= queue; /*nạp v vào hàng đợi*/
chuaxet[v] = solt; /* v có cùng thành phần liên thông với p*/
}
}
}
}
Để duyệt hết tất cả các thành phần liên thông của đồ thị, ta chỉ cần gọi tới thủ tục lienthong
như dưới đây:
void Lien_Thong(void){
for (i=1; i≤ n; i++)
chuaxet[i] =0;
for(i=1; i<=n; i++)
if(chuaxet[i]==0){
solt=solt+1;
BFS(i);
}
}
Để ghi nhận từng đỉnh của đồ thị thuộc thành phần liên thông nào, ta chỉ cần duyệt các đỉnh
có cùng chung giá trị trong mảng chuaxet[] như dưới đây:
void Result( int solt){

Đỉnh 3, 6,7 cùng có giá trị 2 trong mảng chuaxet[] thuộc thành phần liên thông thứ 2;
Đỉnh 8, 9 cùng có giá trị 3 trong mảng chuaxet[] thuộc thành phần liên thông thứ 3.
Văn bản chương trình được thể hiện như sau:
#include <stdio.h>
#include <conio.h>
#include <io.h>
#include <stdlib.h>
#include <dos.h>

128
Chương 6: Các thuật toán tìm kiếm trên đồ thị
#define MAX 100
#define TRUE 1
#define FALSE 0
/* Breadth First Search */
void Init(int G[][MAX], int *n, int *solt, int *chuaxet){
FILE *fp; int i, j;
fp=fopen("lienth.IN", "r");
if(fp==NULL){
printf("\n Khong co file input");
delay(2000);return;
}
fscanf(fp,"%d", n);
printf("\n So dinh do thi:%d",*n);
printf("\n Ma tran ke cua do thi:");
for(i=1; i<=*n;i++){
printf("\n");
for(j=1; j<=*n;j++){
fscanf(fp,"%d", &G[i][j]);
printf("%3d", G[i][j]);

cuoiQ=cuoiQ+1;
QUEUE[cuoiQ]=j;
chuaxet[j]=*solt;
}
}
}
}
void Lien_Thong(void){
int G[MAX][MAX], n, chuaxet[MAX], QUEUE[MAX], solt,i;
clrscr();Init(G, &n,&solt, chuaxet);
printf("\n\n");
for(i=1; i<=n; i++)
if(chuaxet[i]==0){
solt=solt+1;
BFS(G, n, i, &solt, chuaxet, QUEUE);
}
Result(chuaxet, n, solt);
getch();

130
Chương 6: Các thuật toán tìm kiếm trên đồ thị
}
void main(void){
Lien_Thong();
}

6.4. TÌM ĐƯỜNG ĐI GIỮA HAI ĐỈNH BẤT KỲ CỦA ĐỒ THỊ
Bài toán: Cho đồ thị G=(V, E). Trong đó V là tập đỉnh, E là tập cạnh của đồ thị. Hãy tìm
đường đi từ đỉnh s
∈


131