Giải SGK Chuyên đề Tin học 12 Bài 14. Kĩ thuật duyệt đồ thị theo chiều sâu

Cách thực hiện duyệt các đỉnh của đồ thị:

- Duyệt theo chiều sâu (DFS): Bắt đầu từ một đỉnh, tiếp tục đi sâu vào đồ thị theo một nhánh cho đến khi không thể đi xa hơn, sau đó quay lại (backtrack) và tiếp tục với nhánh khác.

- Duyệt theo chiều rộng (BFS): Bắt đầu từ một đỉnh, duyệt tất cả các đỉnh kề với nó trước, sau đó mới chuyển sang duyệt các đỉnh ở mức độ sâu tiếp theo.

- Đánh dấu các đỉnh: Khi duyệt, đánh dấu các đỉnh đã thăm để tránh duyệt lại nhiều lần.

- Thứ tự duyệt: Thứ tự duyệt có thể khác nhau tùy thuộc vào cách đồ thị được biểu diễn và thuật toán sử dụng.

Ý tưởng chính của DFS:

DFS hoạt động bằng cách bắt đầu từ một đỉnh nguồn, đánh dấu nó là đã thăm, sau đó tiếp tục đi sâu vào các đỉnh kề chưa thăm cho đến khi không thể đi tiếp được nữa. Khi không thể đi tiếp, thuật toán quay lui về các đỉnh trước đó để tiếp tục tìm kiếm các đường đi mới.

Có, thứ tự các đỉnh trong danh sách kề ảnh hưởng đến thứ tự các đỉnh được duyệt của thuật toán DFS. Đây là do cách mà DFS hoạt động: nó sẽ duyệt các đỉnh kề theo thứ tự chúng xuất hiện trong danh sách kề của đỉnh hiện tại.

Cụ thể hơn:

Khi thuật toán DFS thăm một đỉnh v, nó sẽ duyệt qua tất cả các đỉnh kề của v. Nếu danh sách các đỉnh kề của v được sắp xếp theo một thứ tự nhất định, DFS sẽ thăm các đỉnh kề theo đúng thứ tự đó. Điều này có thể dẫn đến các đường đi và thứ tự duyệt khác nhau.

Quá trình duyệt theo chiều sâu (DFS) của đồ thị có hướng bắt đầu từ đỉnh 4 được mô tả như sau:

1. Bắt đầu tại đỉnh 4: Đánh dấu đỉnh 4 là đã thăm.

2. Thăm đỉnh kề: Chọn một trong các đỉnh kề với đỉnh 4 để thăm tiếp theo. Đỉnh 4 có cạnh đi ra đến đỉnh 3 và đỉnh 2.

o Nếu chọn đỉnh 3 trước:

a) Thăm đỉnh 3 và đánh dấu là đã thăm.

b) Tiếp tục thăm đỉnh kề của đỉnh 3 là đỉnh 6.

c) Thăm đỉnh 6 và đánh dấu là đã thăm.

d) Thăm đỉnh kề của đỉnh 6 là đỉnh 7 và đánh dấu là đã thăm.

e) Quay trở lại đỉnh 4 và thăm đỉnh 2, sau đó là đỉnh 7 nếu chưa được thăm.

* Nếu chọn đỉnh 2 trước:

a) Thăm đỉnh 2 và đánh dấu là đã thăm.

b) Thăm đỉnh kề của đỉnh 2 là đỉnh 7 và đánh dấu là đã thăm.

c) Quay trở lại đỉnh 4 và thăm đỉnh 3, sau đó là đỉnh 6 và đỉnh 7 nếu chưa được thăm.

Quá trình này tiếp tục cho đến khi tất cả các đỉnh có thể tiếp cận từ đỉnh xuất phát đã được thăm. Trong DFS, chúng ta sẽ đi sâu vào từng nhánh một cách càng sâu càng tốt trước khi quay trở lại (backtrack).

Khái niệm cơ bản của DFS DFS hoạt động dựa trên ý tưởng:

1. Bắt đầu từ một đỉnh ban đầu.

2. Đánh dấu đỉnh đó là đã thăm.

3. Duyệt qua tất cả các đỉnh kề chưa được thăm của đỉnh hiện tại.

4. Khi không còn đỉnh kề nào chưa thăm, quay lui về đỉnh trước đó để tiếp tục tìm kiếm.

5. Quá trình này tiếp tục cho đến khi tất cả các đỉnh có thể được thăm từ đỉnh ban đầu đều đã được thăm.

Triển khai DFS DFS có thể được triển khai bằng cách sử dụng đệ quy hoặc ngăn xếp.