Bài giảng Lý thuyết đồ thị - Chương 3: Các thuật toán tìm kiếm trên đồ thị và ứng dụng - Nguyễn Trần Phi Phượng

Chương 3
CÁC THUẬT TOÁN TÌM KIẾM 
TRÊN ĐỒ THỊ VÀ ỨNG DỤNG
217/03/2011
3.1 Tìm kiếm theo chiều sâu trên đồ thị
Lý thuyết đồ thị
Depth First Search
ƒB1. Xuất phát từ 1 đỉnh cho trước nào đó.
ƒB2. Xử lý đỉnh này và đánh dấu để không xử lý lần sau.
ƒB3. Đưa tất cả các đỉnh kề với nó vào danh sách xử lý và chọn 1
đỉnh để xử lý tiếp theo.
ƒB4. Quay lại B2 cho đến khi không còn đỉnh trong danh sách.
VD:
ƒBắt đầu từ 1. Đưa các đỉnh kề với 1 vào DS: 2, 4, 5
ƒChọn 2 để xử lý. Đưa các đỉnh kề
với 2 vào DS: 3, 4, 5, 
Thứ tự: 1 2 3 5 4 6
1 2 3
4 5 6
317/03/2011
3.1 Tìm kiếm theo chiều sâu trên đồ thị
Lý thuyết đồ thị
Phân tích:
– Dùng cấu trúc Stack
– Sử dụng mảng đánh dấu là mảng 1 chiều:
• int danhdau[maxV];
• Quy ước:
– danhdau[i] = 0; đỉnh i chưa được xét
– danhdau[i] = 1; đỉnh i đã được xét
417/03/2011
3.1 Tìm kiếm theo chiều sâu trên đồ thị
Lý thuyết đồ thị
void DFS(DOTHI g, int s) // s la dinh xuat phat
{
int danhdau[maxV];
Stack st;
//Khoi tao
for (int i = 1; i<=g.nV; i++)
danhdau[i] = 0; // chua co dinh nao duoc xet
Khoitao(st); // Khoi tao Stack
// Bat dau
Push(st,s); // Dua s vao Stack
while (!isEmpty(st)) //Trong khi Stack chua rong
{
int v = Pop (st); // Lay v ra khoi Stack
if (danhdau[v] != 1) // Neu v chua xet
{
cout<<v<<“ “;danhdau[v] = 1;
for (i=g.nV; i>=1; i--)
if (!danhdau[i] && g.mtke[v][i] != 0)
Push(st,i);
}
}
}
517/03/2011
3.1 Tìm kiếm theo chiều sâu trên đồ thị
Lý thuyết đồ thị
ƒ Đưa 1 vào Stack
ƒ Lấy 1 ra xử lý, đưa 5, 4, 2 vào Stack
ƒ Lấy 2 ra xử lý, đưa 5, 3 vào Stack
ƒ Lấy 3 ra xử lý, đưa 6, 5 vào Stack
ƒ Lấy 5 ra xử lý, đưa 4 vào Stack
ƒ Lấy 4 ra xử lý. Không đưa gì vào Stack
ƒ Lấy 6 ra xử lý. Không đưa gì vào Stack
ƒ Lấy 5 ra. Không xử lý (vì đã xử lý rồi)
ƒ Lấy 4 ra. Không xử lý
ƒ Lấy 5 ra. Không xử lý
1 2 3
4 5 6
1
1
5
4
25
3
2 3
6
5
5
4
4 6
Stack
Thứ tự duyệt:
617/03/2011
3.1 Tìm kiếm theo chiều sâu trên đồ thị
Lý thuyết đồ thị
ƒÁp dụng DFS, hãy thể hiện thứ tự duyệt các đỉnh trong
đồ thị sau:
Đáp án: 0 1 2 3 4 9 5 6 7 8 10
u
vt
s x
Đáp án: t u s v
Đỉnh x không được duyệt
0
717/03/2011
3.2 Tìm kiếm theo chiều rộng trên đồ thị
Lý thuyết đồ thị
Breadth First Search
ƒB1. Xuất phát từ 1 đỉnh cho trước nào đó.
ƒB2. Xử lý đỉnh này và đánh dấu để không xử lý lần sau.
ƒB3. Đưa tất cả các đỉnh kề với nó vào danh sách xử lý và lần lượt xử
lý các đỉnh kề với đỉnh đang xét.
ƒB4. Quay lại B2 cho đến khi không còn đỉnh trong danh sách.
VD:
ƒBắt đầu từ 1. Đưa các đỉnh kề với 1 vào DS: 2, 4, 5
ƒChọn 2 để xử lý. Đưa các đỉnh kề
với 2 vào DS: 3, 4, 5, 
Thứ tự: 1 2 4 5 3 6
1 2 3
4 5 6
817/03/2011
3.2 Tìm kiếm theo chiều rộng trên đồ thị
Lý thuyết đồ thị
Phân tích:
– Dùng cấu trúc Queue
– Sử dụng mảng đánh dấu là mảng 1 chiều:
• int danhdau[maxV];
• Quy ước:
– danhdau[i] = 0; đỉnh i chưa được xét
– danhdau[i] = 1; đỉnh i đã được xét
917/03/2011
3.2 Tìm kiếm theo chiều rộng trên đồ thị
Lý thuyết đồ thị
void BFS(DOTHI g, int s) // s la dinh xuat phat
{
int danhdau[maxV];
Queue q;
//Khoi tao
for (int i = 1; i<=g.nV; i++)
danhdau[i] = 0; // chua co dinh nao duoc xet
Khoitao(q); // Khoi tao Queue
// Bat dau
Push(q,s); // Dua s vao Queue
while (!isEmpty(q)) //Trong khi Queue chua rong
{
int v = Pop (q); // Lay v ra khoi Queue
if (danhdau[v] != 1) // Neu v chua xet
{
cout<<v<<“ “; danhdau[v] = 1;
for (i=1; i<=g.nV; i++)
if (!danhdau[i] && g.mtke[v][i] != 0)
Push(q,i);
}
}
}
1017/03/2011
3.2 Tìm kiếm theo chiều rộng trên đồ thị
Lý thuyết đồ thị
ƒ Đưa 1 vào Queue
ƒ Lấy 1 ra xử lý, đưa 2, 4, 5 vào Queue
ƒ Lấy 2 ra xử lý, đưa 3, 5 vào Queue
ƒ Lấy 4 ra xử lý, đưa 5 vào Queue
ƒ Lấy 5 ra xử lý, đưa 3 vào Queue
ƒ Lấy 3 ra xử lý. Đưa 6 vào Queue
ƒ Lấy 5 ra. Không xử lý (vì đã xử lý rồi)
ƒ Lấy 5 ra. Không xử lý
ƒ Lấy 3 ra. Không xử lý
ƒ Lấy 6 ra xử lý. Không đưa gì vào Queue
1 2 3
4 5 6
1
1
5
4
2
5
3
2 4
6
5
5
3 6
Queue
Thứ tự duyệt:
3
1117/03/2011
3.2 Tìm kiếm theo chiều rộng trên đồ thị
Lý thuyết đồ thị
ƒÁp dụng BFS, hãy thể hiện thứ tự duyệt các đỉnh trong
đồ thị sau:
Đáp án: 0 1 3 9 2 4 5 6 8 10 7
u
vt
s x
Đáp án: t u s v
Đỉnh x không được duyệt
0
1217/03/2011
3.3 Tìm đường đi và kiểm tra tính liên thông
Lý thuyết đồ thị
Bài toán tìm đường đi giữa hai đỉnh.
Giả sử s và t là hai đỉnh nào đó của đồ thị. Hãy tìm đường đi
từ s đến t.
Thủ tục DFS(s) (BFS(s)) sẽ cho phép thăm tất cả các đỉnh
thuộc cùng một thành phần liên thông với s. Vì vậy, sau khi
thực hiện xong thủ tục, nếu danhdau[t]=0 thì không có đường đi
từ s đến t.
1317/03/2011
3.3 Tìm đường đi và kiểm tra tính liên thông
Lý thuyết đồ thị
Kiểm tra tính liên thông.
– Áp dụng cho đồ thị vô hướng
– Áp dụng DFS, bắt đầu từ đỉnh bất kỳ, nếu duyệt qua
được tất cả các đỉnh thì đồ thị là liên thông
– Cụ thể:
• Sử dụng thêm biến dem để đếm số đỉnh được duyệt
• Nếu duyệt xong mà đếm bằng g.nV (số đỉnh của đồ
thị) thì có nghĩa là tất cả các đỉnh được duyệt
1417/03/2011
3.3 Tìm đường đi và kiểm tra tính liên thông
Lý thuyết đồ thị
int danhdau[maxV]
void DFS_lt(DOTHI g, int s, int &dem) // s la dinh xuat phat
{
dem++;
danhdau[s] = 1;
for (int v = 1; v<=g.nV; v++)
if (danhdau[v] == 0)
DFS(g,v);
}
int isLienThong(DOTHI g)
{
if (g.type == 1)
return 0; // khong xet do thi co huong
int dem = 0;
for (int v = 1; v<= g.nV; v++)
danhdau[v] = 0;
DFS_lt(g,1,dem);
if (dem == g.nV)
return 1; // do thi lien thong
return 0;
}