Duyệt Theo Chiều Sâu (Depth First Search)

3. Các phép duyệt đồ thị

3.1. Duyệt theo chiều sâu (Depth First Search)

3.1.1. Phép duyệt.

Hình 7.7: Ma trận danh sách kề của đồ thị vô hướng

A

C D

B

Hình 7.8: Ma trận danh sách kề của đồ thị định hướng

A

C D

129

Xuất phát từ một đỉnh v được thăm, tiếp theo đỉnh w chưa được thăm kề với v được chọn và một phép duyệt theo chiều sâu xuất phát từ w lại được thực hiện với các đỉnh w1 kề với w,… khi hết một nhánh thì được chuyển sang nhánh khác. Phép duyệt theo nguyên tắc này được gọi là duyệt theo chiều sâu.

Phép duyệt sẽ kết thúc khi không có một đỉnh nào kề với đỉnh đã được thăm mà chưa được thăm

Giả thiết, với đồ thị hình 7.9 và đỉnh xuất phát là v1, thì phép duyệt theo chiều sâu sẽ được một dãy các đỉnh sau:

v1, v2 (cũng có thể v3), v4 (cũng có thể v5), v5, v3, v7 do v7 không có đỉnh kề nào chưa được thăm nên phải quay lại v3 và cuối cùng là v6.

3.1.2. Giải thuật.

Để kiểm tra việc duyệt mỗi đỉnh đúng một lần ta dùng một mảng mart gồm n phần tử tương ứng với n đỉnh của đồ thị. Khởi đầu gán giá trị 0 cho tất cả các phần tử của mảng, mỗi khi có một đỉnh i được thăm ta sẽ gán mart[i]=1.

Giải thuật được mô tả bằng hàm đệ qui DFS (Depth First Search) như sau: void DFS(int v)

{ thăm đỉnh v: mart[v]=1

for mỗi đỉnh w kề với v

if (mart[w]==0) { mart[w]=1;

DFS(w);}

3.1.3. Ứng dụng của giải thuật.

Nhiều giải thuật sử dụng giải thuật duyệt theo chiều sâu: - Xác định các thành phần liên thông của đồ thị - Sắp xếp tô pô cho đồ thị.

Hình 7.9: Đồ thị không định hướng, liên thông

1 2 4 5 3 6 7

130

- Xác định các thành phần liên thông mạnh của đồ thị có hướng - …