Giáo án điện tử chuyên đề Khoa học máy tính 12 chân trời Bài 3.4: Duyệt đồ thị theo chiều sâu

CHÀO MỪNG

CẢ LỚP ĐẾN BUỔI HỌC NÀY!

KHỞI ĐỘNG

Cho đồ thị G1 như ở Hình 1. Hãy tìm đường đi ngắn nhất từ đỉnh H đến đỉnh D bằng thuật toán duyệt đồ thị theo chiều rộng.

Hình 1. Đồ thị G1

Hình 1. Đồ thị G1

KHỞI ĐỘNG

Gợi ý:

Đường đi ngắn nhất là đường đi qua ít đỉnh nhất.

BÀI 3.4:

DUYỆT ĐỒ THỊ THEO CHIỀU SÂU

NỘI DUNG BÀI HỌC

Duyệt đồ thị theo chiều sâu

Thuật toán duyệt đồ thị theo chiều sâu

1

2

1.

DUYỆT ĐỒ THỊ THEO CHIỀU SÂU

1. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU

Nêu cách duyệt đồ thị theo chiều sâu.

1. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU

Duyệt đồ thị theo chiều sâu (DFS – Depth First Search) bắt đầu từ việc “duyệt theo chiều sâu từ đỉnh u” chưa được duyệt: duyệt đỉnh u, sau đó lần lượt xét các đỉnh kề v của đinh u, nếu có đỉnh v chưa được duyệt thì “duyệt theo chiều sâu từ đỉnh v”, ngược lại quay lui về bước duyệt trước đó. Lặp lại cách duyệt này cho đến khi tất cả các đỉnh của đồ thị đã được duyệt.

1. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU

Duyệt đồ thị theo chiều sâu có thể được thực hiện bằng cách sử dụng ngăn xếp. Giả sử quá trình duyệt bắt đầu từ đỉnh u chưa được duyệt. Khởi tạo ngăn xếp rỗng, sau đó duyệt đỉnh u và thêm đỉnh u vào ngăn xếp. Xem đỉnh p ở đỉnh ngăn xếp, nếu có đỉnh kề v chưa duyệt của đỉnh p thì duyệt đỉnh v và thêm đỉnh v vào ngăn xếp, ngược lại, lấy đỉnh p ra khỏi ngăn xếp. Lặp lại quá trình lấy ra và thêm vào ngăn xếp cho đến khi ngăn xếp rỗng.

1. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU

Minh họa duyệt đồ thị theo chiều sâu

1. Duyệt đỉnh A, thêm đỉnh A vào ngăn xếp.

đã duyệt

Stack

2. Xem đỉnh A ở đỉnh ngăn xếp. Đỉnh kề B của đỉnh A chưa duyệt. Duyệt đỉnh B và thêm đỉnh này vào ngăn xếp.

đã duyệt

Stack

3. Xem đỉnh B ở đỉnh ngăn xếp. Đỉnh kề C của đỉnh B chưa duyệt. Duyệt đỉnh C và thêm đỉnh này vào ngăn xếp.

đã duyệt

Stack

4a. Xem đỉnh C ở đỉnh ngăn xếp. Đỉnh kề D của đỉnh C chưa duyệt. Duyệt đỉnh D và thêm đỉnh này vào ngăn xếp.

đã duyệt

Stack

4b. Xem đỉnh D ở đỉnh ngăn xếp. Đỉnh D không có đỉnh kề chưa duyệt. Lấy đỉnh D ra khỏi ngăn xếp.

đã duyệt

Stack

5. Xem đỉnh C ở đỉnh ngăn xếp. Đỉnh kề E của đỉnh C chưa duyệt. Duyệt đỉnh E và thêm đỉnh này vào ngăn xếp.

đã duyệt

Stack

6a. Xem đỉnh E ở đỉnh ngăn xếp. Đỉnh kề F của đỉnh E chưa duyệt. Duyệt đỉnh F và thêm đỉnh này vào ngăn xếp.

đã duyệt

Stack

6b. Xem đỉnh F ở đỉnh ngăn xếp. Đỉnh F không có đỉnh kề chưa duyệt. Lấy đỉnh F ra khỏi ngăn xếp.

đã duyệt

Stack

7a. Xem đỉnh E ở đỉnh ngăn xếp. Đỉnh kề G của đỉnh E chưa duyệt. Duyệt đỉnh G và thêm đỉnh này vào ngăn xếp.

đã duyệt

Stack

7b. Xem đỉnh G ở đỉnh ngăn xếp. Đỉnh G không có đỉnh kề chưa duyệt. Lấy đỉnh G ra khỏi ngăn xếp.

đã duyệt

Stack

8. Xem đỉnh E ở đỉnh ngăn xếp. Đỉnh kề H của đỉnh E chưa duyệt. Duyệt đỉnh H và thêm đỉnh này vào ngăn xếp.

đã duyệt

Stack

9a. Xem đỉnh H ở đỉnh ngăn xếp. Đỉnh H không có đỉnh kề chưa duyệt. Lấy đỉnh H ra khỏi ngăn xếp.

đã duyệt

Stack

9b. Xem đỉnh E ở đỉnh ngăn xếp. Đỉnh E không có đỉnh kề chưa duyệt. Lấy đỉnh E ra khỏi ngăn xếp.

đã duyệt

Stack

9c. Xem đỉnh C ở đỉnh ngăn xếp. Đỉnh C không có đỉnh kề chưa duyệt. Lấy đỉnh C ra khỏi ngăn xếp.

đã duyệt

Stack

9d. Xem đỉnh B ở đỉnh ngăn xếp. Đỉnh B không có đỉnh kề chưa duyệt. Lấy đỉnh B ra khỏi ngăn xếp.

đã duyệt

Stack

9e. Xem đỉnh A ở đỉnh ngăn xếp. Đỉnh A không có đỉnh kề chưa duyệt. Lấy đỉnh A ra khỏi ngăn xếp.

đã duyệt

9g. Ngăn xếp rỗng. Kết thúc. Thứ tự duyệt đồ thị theo chiều sâu là A, B, C, D, E, F, G, H.

Em hãy minh họa duyệt đồ thị theo chiều sâu của đồ thị G2 ở Hình 2 (tương tự như Bảng 1) bắt đầu từ đỉnh 2.

HOẠT ĐỘNG LÀM (SGK TR.68)

Hình 2. Đồ thị G2

Hình 2. Đồ thị G2

HOẠT ĐỘNG LÀM (SGK TR.68)

Có nhiều kết quả duyệt đồ thị, thứ tự sau là một VD: 2, 0, 4, 1, 5, 3.

GHI NHỚ

Duyệt đồ thị theo chiều sâu bắt đầu từ việc duyệt theo chiều sâu đỉnh u chưa được duyệt. Duyệt đỉnh u, sau đó lần lượt xét các đỉnh kề v của đỉnh u, nếu đỉnh v chưa được duyệt thì duyệt theo chiều sâu bắt đầu từ đỉnh v. Lặp lại cách duyệt này cho đến khi tất cả các đỉnh của đồ thị đã được duyệt.

2. THUẬT TOÁN DUYỆT ĐỒ THỊ THEO CHIỀU SÂU

--------------- Còn tiếp ---------------