Duyệt đồ thị¶

Cây biểu diễn quan hệ "một-nhiều", trong khi đồ thị có mức độ tự do cao hơn và có thể biểu diễn các quan hệ "nhiều-nhiều" bất kỳ. Do đó, chúng ta có thể coi cây là một trường hợp đặc biệt của đồ thị. Rõ ràng, thao tác duyệt cây cũng là một trường hợp đặc biệt của thao tác duyệt đồ thị.

Cả đồ thị và cây đều cần áp dụng các thuật toán tìm kiếm để thực hiện thao tác duyệt. Các phương pháp duyệt đồ thị cũng có thể được chia thành hai loại: duyệt theo chiều rộng và duyệt theo chiều sâu.

Tìm kiếm theo chiều rộng¶

Tìm kiếm theo chiều rộng tiến hành từ gần đến xa: bắt đầu từ một nút cho trước, nó luôn truy cập các đỉnh gần nhất trước rồi mới mở rộng ra bên ngoài theo từng lớp. Như thể hiện trong hình dưới đây, bắt đầu từ đỉnh phía trên bên trái, trước tiên duyệt qua tất cả các đỉnh liền kề của đỉnh đó, sau đó duyệt qua tất cả các đỉnh liền kề của đỉnh tiếp theo, và cứ tiếp tục như vậy cho đến khi tất cả các đỉnh đều đã được truy cập.

Triển khai mã nguồn¶

BFS thường được triển khai với sự trợ giúp của hàng đợi, như thể hiện trong mã nguồn dưới đây. Hàng đợi có tính chất "vào trước, ra trước" (first in, first out), điều này phù hợp với ý tưởng "từ gần đến xa" của BFS.

Thêm đỉnh bắt đầu startVet vào hàng đợi và bắt đầu vòng lặp.
Trong mỗi vòng lặp, lấy đỉnh ở đầu hàng đợi ra (pop) và ghi nhận là đã truy cập, sau đó thêm tất cả các đỉnh liền kề của đỉnh đó vào cuối hàng đợi.
Lặp lại bước 2. cho đến khi tất cả các đỉnh đều đã được truy cập.

Để tránh truy cập lại các đỉnh đã qua, chúng ta sử dụng một tập hợp băm (hash set) visited để ghi lại những đỉnh nào đã được truy cập.

Tip

Một tập hợp băm (hash set) có thể được xem như một bảng băm chỉ lưu trữ key mà không lưu trữ value. Nó hỗ trợ các thao tác chèn, xóa, tìm kiếm và cập nhật trên key trong thời gian \(O(1)\). Dựa trên tính duy nhất của key, tập hợp băm thường được sử dụng cho các tình huống như loại bỏ trùng lặp dữ liệu.

[file]{graph_bfs}-[class]{}-[func]{graph_bfs}

Mã nguồn này tương đối trừu tượng; bạn nên tham khảo hình minh họa dưới đây để hiểu sâu hơn.

Thứ tự duyệt theo chiều rộng có phải là duy nhất không?

Không duy nhất. Tìm kiếm theo chiều rộng chỉ yêu cầu duyệt theo thứ tự "gần đến xa", và thứ tự duyệt của các đỉnh ở cùng một khoảng cách có thể hoán đổi tùy ý. Lấy hình trên làm ví dụ, thứ tự truy cập của các đỉnh \(1\) và \(3\) có thể được hoán đổi cho nhau, tương tự như thứ tự truy cập của các đỉnh \(2\), \(4\) và \(6\).

Phân tích độ phức tạp¶

Độ phức tạp thời gian: Tất cả các đỉnh sẽ lần lượt được đưa vào hàng đợi và lấy ra khỏi hàng đợi một lần, tốn thời gian \(O(|V|)\); trong quá trình duyệt qua các đỉnh liền kề, vì đây là đồ thị vô hướng nên tất cả các cạnh sẽ được truy cập \(2\) lần, tốn thời gian \(O(2|E|)\); tổng cộng tốn thời gian \(O(|V| + |E|)\).

Độ phức tạp không gian: Danh sách res, tập hợp băm visited và hàng đợi que có thể chứa tối đa \(|V|\) đỉnh, chiếm dụng không gian \(O(|V|)\).

Tìm kiếm theo chiều sâu¶

Tìm kiếm theo chiều sâu là phương pháp duyệt ưu tiên đi xa nhất có thể, sau đó quay lui khi không còn đường đi. Như thể hiện trong hình dưới đây, bắt đầu từ đỉnh phía trên bên trái, truy cập một đỉnh liền kề của đỉnh hiện tại, tiếp tục cho đến khi gặp ngõ cụt, sau đó quay lại và tiếp tục đi xa nhất có thể trước khi lại quay lui, và cứ tiếp tục như vậy cho đến khi tất cả các đỉnh đều đã được duyệt.

Triển khai mã nguồn¶

Mô hình thuật toán "đi xa nhất có thể rồi quay lại" này thường được triển khai bằng đệ quy. Tương tự như tìm kiếm theo chiều rộng, trong tìm kiếm theo chiều sâu chúng ta cũng cần một tập hợp băm visited để ghi nhận các đỉnh đã duyệt nhằm tránh truy cập lại.

[file]{graph_dfs}-[class]{}-[func]{graph_dfs}

Quy trình thuật toán của tìm kiếm theo chiều sâu được thể hiện trong hình dưới đây.

Đường nét đứt thẳng biểu diễn việc đi xuống đệ quy (downward recursion), cho biết một phương thức đệ quy mới đã được bắt đầu để truy cập một đỉnh mới.
Đường nét đứt cong biểu diễn việc quay lui đi lên (upward backtracking), cho biết cuộc gọi đệ quy này đã quay trở lại điểm mà nó được gọi.

Để hiểu sâu hơn, bạn nên kết hợp hình minh họa bên dưới với mã nguồn để mô phỏng trong đầu (hoặc vẽ ra) toàn bộ quy trình DFS, bao gồm cả thời điểm mỗi cuộc gọi đệ quy bắt đầu và khi nào nó trả về.

Thứ tự duyệt theo chiều sâu có phải là duy nhất không?

Tương tự như tìm kiếm theo chiều rộng, thứ tự duyệt theo chiều sâu cũng không duy nhất. Cho trước một đỉnh, bất kỳ hướng khám phá nào cũng có thể được chọn trước; nghĩa là thứ tự của các đỉnh liền kề có thể được sắp xếp lại tùy ý mà vẫn tạo thành tìm kiếm theo chiều sâu.

Lấy việc duyệt cây làm ví dụ, "gốc \(\rightarrow\) trái \(\rightarrow\) phải" (root \(\rightarrow\) left \(\rightarrow\) right), "trái \(\rightarrow\) gốc \(\rightarrow\) phải" (left \(\rightarrow\) root \(\rightarrow\) right) và "trái \(\rightarrow\) phải \(\rightarrow\) gốc" (left \(\rightarrow\) right \(\rightarrow\) root) tương ứng với duyệt tiền thứ tự (pre-order), trung thứ tự (in-order) và hậu thứ tự (post-order). Chúng đại diện cho ba mức độ ưu tiên duyệt khác nhau, nhưng cả ba đều thuộc về tìm kiếm theo chiều sâu.

Phân tích độ phức tạp¶

Độ phức tạp thời gian: Tất cả các đỉnh sẽ được truy cập \(1\) lần, tốn thời gian \(O(|V|)\); tất cả các cạnh sẽ được truy cập \(2\) lần, tốn thời gian \(O(2|E|)\); tổng cộng tốn thời gian \(O(|V| + |E|)\).

Độ phức tạp không gian: Danh sách res và tập hợp băm visited có thể chứa tối đa \(|V|\) đỉnh, và độ sâu đệ quy cực đại là \(|V|\), do đó chiếm dụng không gian \(O(|V|)\).