Chương 3

CÁC THUẬT TOÁN TÌM KIẾM

TRÊN ĐỒ THỊ VÀ ỨNG DỤNG

3.1 Tìm kiếm theo chiều sâu trên đồ thị

Depth First Search

(cid:131) B1. Xuất phát từ 1 đỉnh cho trước nào đó.

(cid:131) B2. Xử lý đỉnh này và đánh dấu để không xử lý lần sau.

(cid:131) 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.

(cid:131) B4. Quay lại B2 cho đến khi không còn đỉnh trong danh sách.

VD:

(cid:131) Bắt đầu từ 1. Đưa các đỉnh kề với 1 vào DS: 2, 4, 5

2

1

3

(cid:131) 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

6

4

5

17/03/2011

Lý thuyết đồ thị

2

3.1 Tìm kiếm theo chiều sâu trên đồ 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

17/03/2011

Lý thuyết đồ thị

3

3.1 Tìm kiếm theo chiều sâu trên đồ thị

// s la dinh xuat phat

void DFS(DOTHI g, int s) {

int danhdau[maxV]; Stack st; //Khoi tao for (int i = 1; i<=g.nV; i++)

danhdau[i] = 0;

// chua co dinh nao duoc xet // Khoi tao Stack

// Dua s vao Stack //Trong khi Stack chua rong

Khoitao(st); // Bat dau Push(st,s); while (!isEmpty(st)) {

// Lay v ra khoi Stack // Neu v chua xet

int v = Pop (st); if (danhdau[v] != 1) {

“;danhdau[v] = 1;

cout<=1; i--)

if (!danhdau[i] && g.mtke[v][i] != 0)

Push(st,i);

}

}

}

17/03/2011

Lý thuyết đồ thị

4

3.1 Tìm kiếm theo chiều sâu trên đồ thị

2

1

3

(cid:131) Đưa 1 vào Stack

(cid:131) Lấy 1 ra xử lý, đưa 5, 4, 2 vào Stack

(cid:131) Lấy 2 ra xử lý, đưa 5, 3 vào Stack

6

4

5

(cid:131) Lấy 3 ra xử lý, đưa 6, 5 vào Stack

(cid:131) Lấy 5 ra xử lý, đưa 4 vào Stack

4 5 (cid:131) Lấy 4 ra xử lý. Không đưa gì vào Stack

6 3 (cid:131) Lấy 6 ra xử lý. Không đưa gì vào Stack

Stack

25 (cid:131) Lấy 5 ra. Không xử lý (vì đã xử lý rồi)

4 (cid:131) Lấy 4 ra. Không xử lý

5 1

(cid:131) Lấy 5 ra. Không xử lý

1 2 3 5 4 6

Thứ tự duyệt:

17/03/2011

Lý thuyết đồ thị

5

3.1 Tìm kiếm theo chiều sâu trên đồ thị

(cid:131)Áp dụng DFS, hãy thể hiện thứ tự duyệt các đỉnh trong

đồ thị sau:

u

0 t v

s x

Đáp án: 0 1 2 3 4 9 5 6 7 8 10

Đáp án: t u s v Đỉnh x không được duyệt

17/03/2011

Lý thuyết đồ thị

6

3.2 Tìm kiếm theo chiều rộng trên đồ thị

Breadth First Search

(cid:131) B1. Xuất phát từ 1 đỉnh cho trước nào đó.

(cid:131) B2. Xử lý đỉnh này và đánh dấu để không xử lý lần sau.

(cid:131) 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.

(cid:131) B4. Quay lại B2 cho đến khi không còn đỉnh trong danh sách.

VD:

(cid:131) Bắt đầu từ 1. Đưa các đỉnh kề với 1 vào DS: 2, 4, 5

2

1

3

(cid:131) 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

6

4

5

17/03/2011

Lý thuyết đồ thị

7

3.2 Tìm kiếm theo chiều rộng trên đồ 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

17/03/2011

Lý thuyết đồ thị

8

3.2 Tìm kiếm theo chiều rộng trên đồ thị

// s la dinh xuat phat

void BFS(DOTHI g, int s) {

int danhdau[maxV]; Queue q; //Khoi tao for (int i = 1; i<=g.nV; i++)

danhdau[i] = 0;

// chua co dinh nao duoc xet // Khoi tao Queue

// Dua s vao Queue //Trong khi Queue chua rong

Khoitao(q); // Bat dau Push(q,s); while (!isEmpty(q)) {

// Lay v ra khoi Queue // Neu v chua xet

int v = Pop (q); if (danhdau[v] != 1) {

“; danhdau[v] = 1;

cout<

if (!danhdau[i] && g.mtke[v][i] != 0)

Push(q,i);

}

}

}

17/03/2011

Lý thuyết đồ thị

9

3.2 Tìm kiếm theo chiều rộng trên đồ thị

2

1

3

(cid:131) Đưa 1 vào Queue

(cid:131) Lấy 1 ra xử lý, đưa 2, 4, 5 vào Queue

6

4

5

(cid:131) Lấy 2 ra xử lý, đưa 3, 5 vào Queue

(cid:131) Lấy 4 ra xử lý, đưa 5 vào Queue

6

(cid:131) Lấy 5 ra xử lý, đưa 3 vào Queue 3

(cid:131) Lấy 3 ra xử lý. Đưa 6 vào Queue

(cid:131) Lấy 5 ra. Không xử lý (vì đã xử lý rồi) 5 5

Queue

(cid:131) Lấy 5 ra. Không xử lý 3

5 (cid:131) Lấy 3 ra. Không xử lý

4 (cid:131) Lấy 6 ra xử lý. Không đưa gì vào Queue

1 2

1 2 4 5 3 6

Thứ tự duyệt:

17/03/2011

Lý thuyết đồ thị

10

3.2 Tìm kiếm theo chiều rộng trên đồ thị

(cid:131)Áp dụng BFS, hãy thể hiện thứ tự duyệt các đỉnh trong

đồ thị sau:

u

0 t v

s x

Đáp án: 0 1 3 9 2 4 5 6 8 10 7

Đáp án: t u s v Đỉnh x không được duyệt

17/03/2011

Lý thuyết đồ thị

11

3.3 Tìm đường đi và kiểm tra tính liên thông

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.

17/03/2011

Lý thuyết đồ thị

12

3.3 Tìm đường đi và kiểm tra tính liên thông

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

17/03/2011

Lý thuyết đồ thị

13

3.3 Tìm đường đi và kiểm tra tính liên thông

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;

}

17/03/2011

Lý thuyết đồ thị

14