Chương 3
CÁC THUẬT TOÁN TÌM KIẾM
TRÊN ĐỒ THỊ VÀ ỨNG DỤNG
2
17/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ướcnàođó.
B2. Xửlý đỉnh này và đánh dấuđể không xửlý lầnsau.
B3. Đưatấtcảcác đỉnh kềvới nó vào danh sách xửlý và chọn1
đỉnh để xửlý tiếp theo.
B4.QuaylạiB2chođến khi không còn đỉnh trong danh sách.
VD:
Bắtđầutừ1. Đưa các đỉnh kềvới 1 vào DS: 2, 4, 5
Chọn2để xửlý. Đưa các đỉnh kề
với 2 vào DS: 3, 4, 5, …
Thứtự:123546
123
4 5 6
3
17/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ấulàmảng 1 chiều:
• int danhdau[maxV];
•Quyước:
– danhdau[i] = 0; đỉnh i chưađượcxét
– danhdau[i] = 1; đỉnh i đãđượcxét
4
17/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);
}
}
}
5
17/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ấy1raxửlý, đưa 5, 4, 2 vào Stack
Lấy2raxửlý, đưa 5, 3 vào Stack
Lấy3raxửlý, đưa 6, 5 vào Stack
Lấy5raxửlý, đưa 4 vào Stack
Lấy4raxửlý. Không đưa gì vào Stack
Lấy6raxử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ý
123
4 5 6
1
1
5
4
25
3
2 3
6
5
5
4
4 6
Stack
Thứtựduyệt: