Bài 14. Kĩ thuật duyệt đồ thị theo chiều sâu

KĨ THUẬT DUYỆT ĐỒ THỊ THEO CHIỀU SÂU

Sau bài học này em sẽ:

Chúng ta đã biết bài toán và thuật toán duyệt (tìm kiếm) dữ liệu trên các cấu trúc dữ liệu khác nhau:

Vậy với dữ liệu của đồ thị, việc duyệt các đỉnh của đồ thị sẽ được thực hiện như thế nào? Quan sát hai đồ thị ở Hình 14.1 và thảo luận với bạn cách thực hiện duyệt trên các đỉnh của đồ thị đó.

1. Bài toán duyệt đồ thị

Bài toán duyệt đồ thị là: cần duyệt (đánh dấu) tất cả các đỉnh bằng cách đi theo các cạnh của đồ thị. Có hai cách (thuật toán) duyệt đồ thị là duyệt theo chiều sâu và duyệt theo chiều rộng.

Hoạt động 1. Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu

Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu (DFS – Depth First Search).

Ý tưởng của cách duyệt này, như tên của thuật toán, là mỗi khi xuất phát từ một đỉnh chưa được duyệt, cần đi dọc theo các cạnh theo hướng "sâu" nhất có thể, tức là luôn cố gắng duyệt theo hướng "ra xa" khỏi đỉnh ban đầu, đi tới đỉnh nào thì đánh dấu (duyệt) đỉnh đó, duyệt cho đến khi không đi được nữa thì quay lại đỉnh trước để tìm cách đi khác, cứ như vậy cho đến khi không tìm được đường đi nào nữa thì dừng lại. Quá trình như vậy lặp lại cho đến khi tất cả các đỉnh của đồ thị đã được đánh dấu.

Chúng ta tìm hiểu thuật toán duyệt theo chiều sâu qua ví dụ đồ thị vô hướng trong Hình 14.1a. Giả sử bắt đầu duyệt từ đỉnh 0. Mũi tên màu đỏ chỉ hướng đi theo cạnh:

Hình 14.2. Chi tiết các bước duyệt theo chiều sâu, bắt đầu từ đỉnh 0

Chi tiết các bước duyệt đồ thị trên được mô tả trong Bảng 14.1.

Bảng 14.1. Các bước duyệt đồ thị

STT	Đỉnh hiện thời	Danh sách đinh kề	Duyệt (đánh dấu)	Tìm đỉnh chưa duyệt trong Adj	Trang thái
0	5	Tìm thấy 5	Duyệt tiếp
2	5	0 1 4 6 7	5	Tim thấy 1	Duyệt tiếp
3	5 6	Duyệt tiếp
4	6	1 3 5 7	6	Tim thấy 3	Duyệt tiếp
5	3	2 4 6	3	Tim thấy 2	Duyệt tiếp
6	2	3 7	2	Tìm thấy 7	Duyệt tiếp
2 5 6	7	Không thấy	Quay lại 2
8	2	3 7	Không thấy	Quay lại 3
9	3	2 46	Tim thấy 4	Duyệt tiếp
10	4	3 5 7	Không thấy	Quay lại 3
11	3	2 4 6	Không thấy	Quay lai 6
12	1 3 5 7	Không thấy	lại 1 Quay
13	5 6	Không thấy	Quay lại 5
14	5	Không thấy	Quay lại 0
15	0	5

Lưu ý: Màu đỏ là các đỉnh đã được duyệt (đánh dấu) trước đó. In đậm là đỉnh đầu tiên trong danh sách kề chưa được duyệt, đỉnh này được đánh dấu "tìm thấy" để thực hiện bước đi tiếp theo. Nếu tất cả các đỉnh trong danh sách đỉnh kề đều đã duyệt (màu đỏ) thì thực hiện quay lại đỉnh của bước trước đó.

Như vậy, thứ tự các đỉnh được duyệt là: 0 5 1 6 3 2 7 4.

Thuật toán duyệt như trên được gọi là duyệt theo chiều sâu (DFS – Depth First Search). Thuật toán duyệt này áp dụng cho cả đồ thị vô hướng và có hướng.

2. Thuật toán duyệt theo chiều sâu DFS

Hoạt động 2. Tìm hiểu thuật toán duyệt DFS

Quan sát, thảo luận và tìm hiểu thuật toán duyệt theo chiều sâu trên đồ thị bất kì.

Cho trước đồ thị G = (V, E) vô hướng hoặc có hướng. Chúng ta sẽ thiết kế thuật toán duyệt đồ thị theo ý tưởng thực hiện trong Hoạt động 1. Ban đầu, tất cả các đỉnh của đồ thị là chưa đánh dấu. Thuật toán DFS(Adj,u) thực hiện công việc duyệt đồ thị theo chiều sâu bắt đầu từ đỉnh u chưa đánh dấu.

Đoạn mã giả sau thực hiện các công việc: thiết lập tất cả các đỉnh của đồ thị là chưa đánh dấu, sau đó bắt đầu duyệt đồ thị G theo chiều sâu có sử dụng thuật toán DFS(Adj,u) để bắt đầu duyệt từ đỉnh u.

DFS_Traversal(G):

1. Thiết lập tất cả các đỉnh u thuộc V là chưa đánh dấu
2. Với mỗi đỉnh u thuộc V
3. Nếu u chưa đánh dấu: DFS(Adj,u)

Hàm đệ quy DFS(Adj,u) thực hiện thuật toán duyệt theo chiều sâu bắt đầu từ đỉnh u chưa đánh dấu như sau:

DFS(Adj,u):

1. Đánh dấu đỉnh u
2. Với mỗi v là đỉnh kề của đỉnh u
3. Nếu đỉnh v chưa đánh dấu: DFS(Adj,v)

Mảng mark[] dùng để đánh dấu các đỉnh: mark[v] = False nghĩa là đỉnh v chưa được đánh dấu. mark[v] = True nghĩa là đỉnh v đã được đánh dấu. Ban đầu, mark[v] = False với mọi đỉnh v.

Hàm đệ quy DFS(Adj,u) trong Python dùng để duyệt đồ thị theo chiều sâu bắt đầu từ đỉnh u chưa đánh dấu như sau:

def DFS(Adj,u):
mark[u] = True
for v in Adj[u]:
if not mark[v]:  # Đỉnh v chưa đánh dấu
DFS(Adj,v)

Giải thích: Dòng lệnh 2 cho biết đỉnh u đã được đánh dấu. Lệnh 3 kiểm tra các đỉnh kề v của đỉnh u. Nếu có đỉnh v chưa được đánh dấu thì gọi đệ quy cho đỉnh này. Đây chính là ý tưởng của duyệt đồ thị theo chiều sâu đã mô tả trong Hoạt động 1. Khi kết thúc thực hiện hàm DFS(Adj,u) thì tất cả các đỉnh mà có đường đi từ đỉnh u đều được đánh dấu.

Hàm DFS_Traversal(V, Adj) sẽ duyệt đồ thị theo chiều sâu với bộ dữ liệu (V, Adj) như sau:

def DFS_Traversal(V, Adj):  # Duyệt đồ thị (V, Adj) theo chiều sâu
mark = [False]*len(V)  # Tất cả các đỉnh là chưa được đánh dấu
for u in V:  # Duyệt các đỉnh của đồ thị
if not mark[u]:  # Đỉnh u chưa được đánh dấu
DFS(Adj,u)  # Duyệt theo chiều sâu bắt đầu từ u

Chương trình sau đây sẽ tạo đồ thị từ tệp danh sách kề, sau đó duyệt đồ thị này bằng hàm DFS_Traversal():

fname = 'graph.inp'
V, Adj = BuildGraph(fname)  # Tạo đồ thị từ tệp danh sách kề
DFS_Traversal(V, Adj)  # Duyệt đồ thị theo chiều sâu

Phân tích thời gian của DFS:

Từ đó suy ra kết quả sau: Độ phức tạp thời gian duyệt theo chiều sâu là O(V+E) nếu đồ thị có hướng và là O(V+2E) nếu đồ thị vô hướng.

Thuật toán duyệt đồ thị theo chiều sâu DFS có thể mô tả bằng hàm đệ quy DFS thực hiện duyệt theo chiều sâu từ đỉnh u.

def DFS(Adj,u):
mark[u] = True  # Đánh dấu đỉnh u
print(u)  # In đỉnh u
for v in Adj[u]:
if not mark[v]:
DFS(Adj,v)

Sử dụng hàm trên áp dụng duyệt các phần tử của đồ thị Hình 14.1a trong phần khởi động. Kiểm tra thứ tự các đỉnh đã duyệt có trùng khớp với thứ tự các đỉnh đã duyệt (bằng tay) trong Hoạt động 1 hay không.

Hoạt động 3. Tìm hiểu thuật toán duyệt không đệ quy DFS

Tìm hiểu một cách cài đặt khác của thuật toán duyệt theo chiều sâu DFS không sử dụng kĩ thuật đệ quy.

Thuật toán không đệ quy DFS sử dụng ngăn xếp để duyệt theo chiều sâu, bắt đầu từ đỉnh u như sau:

def DFS(Adj,u):
S = Stack()  # Khởi tạo Stack rỗng
push(S,u)
while not isEmptyStack(S):
v = pop(S)
if not mark[v]:
mark[v] = True
for w in Adj[v]:
push(S,w)

Chương trình sau sẽ đọc dữ liệu từ tệp đầu vào và thực hiện lệnh duyệt theo chiều sâu bắt đầu từ đỉnh 0:

from Stack import *
fname = 'graph.inp'
V, Adj = BuildGraph(fname)
mark = [False]*len(V)
DFS(Adj,0)

Với dữ liệu của danh sách kề Adj ở Bảng 14.1, khi thực hiện hàm duyệt DFS(Adj,0), kết quả thứ tự duyệt các đỉnh của đồ thị là: 0 5 7 6 3 4 2 1.

Có thể thiết lập hàm duyệt theo chiều sâu áp dụng tổng quát đồ thị G với bộ dữ liệu (V, Adj) như sau:

def DFS_Traversal(V, Adj):
mark = [False]*len(V)
for u in V:
if not mark[u]:
DFS(Adj,u)

Chương trình đọc dữ liệu từ tệp đầu vào và duyệt đồ thị theo chiều sâu như sau:

from Stack import *
fname = 'graph.inp'
V, Adj = BuildGraph(fname)
mark = [False]*len(V)
DFS_Traversal(V, Adj)

Thuật toán duyệt không đệ quy theo chiều sâu sử dụng ngăn xếp tương tự thuật toán tìm đỉnh chưa duyệt theo thứ tự ngược lại của danh sách kề Adj.

VẬN DỤNG

def DFS(Adj,u):
if not mark[u]:
mark[u] = True
for v in Adj[u]:
DFS(Adj,v)