Duyệt đồ thị


Giới thiệu 
Khi giải quyết nhiều bài toán lý thuyết đồ thị, ta luôn phải duyệt qua tất cả các đỉnh của đồ thị đó. Cho nên, cần có thuật toán duyệt toàn bộ các đỉnh của đồ thị này. Gọi chung là thuật toán duyệt đồ thị. Trong đó có thuật toán duyệt theo chiều sâu và duyệt theo chiều rộng.

Thuật toán duyệt theo chiều sâu(Deep-First Search-DFS)

Nội dung thuật toán 
Cho G = (V,E) là đồ thị có tập các đỉnh V và tập các cạnh E. v là một đỉnh trong V va u là đỉnh kề của v, sao cho u cũng thuộc V. Khi đó ta dán nhãn cho tất cả các đỉnh của đồ thị là 0. Chọn một đỉnh v thuộc tập V để bắt đầu duyệt. Gán nhãn đỉnh v này la 1-v đã được duyệt. Chọn đỉnh u trong tập V kề với đỉnh v mà nhãn là 0. Duyệt qua đỉnh u và gán nhãn u là 1. Tiếp tục quá trình duyệt đến khi tất cả các đỉnh đồ thị có nhãn là 1.

Ví dụ áp dụng

=(V,E) có V={1,2,3,4,5} được lưu vào bảng như sau:

Trước tiên, ta gán nhãn tất cả các đỉnh là 0 (chưa duyệt). Khi đỉnh nào được duyệt qua thì ta cập nhật lại nhãn cho đỉnh đó là 1.
 Các bước duyệt theo chiều sâu:
Chọn một đỉnh từ danh sách các đỉnh của G. Ở đây ta chọn đỉnh 2 làm đỉnh đầu tiên để bắt đầu duyệt.
Thực hiện DFS(2):pro

Gán nhãn cho đỉnh 2 là 1 khi duyệt qua nó, tìm thấy các đỉnh kề của đỉnh 2 có đỉnh 3 có nhãn là 0(chưa được duyệt).Lặp lại quá trình với đỉnh 3.
Thực hiện DFS(3):

Gán nhãn cho đỉnh 3 là 1 khi duyệt qua nó, tìm thấy các đỉnh kề của đỉnh 3 có đỉnh 1 có nhãn là 0(chưa được duyệt).Lặp lại quá trình với đỉnh 1.
Thực hiện DFS(1):

Gán nhãn cho đỉnh 1 là 1 khi duyệt qua nó, tìm thấy các đỉnh kề của đỉnh 1 có đỉnh 4 có nhãn là 0(chưa được duyệt).Lặp lại quá trình với đỉnh 4.
Thực hiện DFS(4):

Gán nhãn cho đỉnh 4 là 1 khi duyệt qua nó, tìm thấy các đỉnh kề của đỉnh 4 có đỉnh 5 có nhãn là 0(chưa được duyệt).Lặp lại quá trình với đỉnh 5.
Đến đây, tất cả các đỉnh đã duyệt qua nên ta dừng thuật toán. Xuất ra dãy các đỉnh đã duyệt như sau: 2,3,1,4,5.

Mã giả

Xem thêm
 Tìm kiếm theo chiều sâu

Tham khảo
 Nguyễn Tuấn Anh, Lý thuyết đồ thị và ứng dụng. Nhà xuất bản Giáo dục Việt Nam 2012
 Dương Anh Đức, Nhập môn Cấu Trúc Dữ Liệu và Giải Thuật, Đại Học Khoa Học Tự Nhiên

Tham khảo

Liên kết ngoài 
Video demo thuật toán DFS

Giải thuật lý thuyết đồ thị
Giải thuật tìm kiếm
Giới thiệu Khi giải quyết nhiều bài toán lý thuyết đồ thị , ta luôn phải duyệt qua tất cả các đỉnh của đồ thị đó . Cho nên , cần có thuật toán duyệt toàn bộ các đỉnh của đồ thị này . Gọi chung là thuật toán duyệt đồ thị . Trong đó có thuật toán duyệt theo chiều sâu và duyệt theo chiều rộng . Thuật toán duyệt theo chiều sâu(Deep-First Search-DFS) Nội dung thuật toán Cho G = (V , E) là đồ thị có tập các đỉnh V và tập các cạnh E . v là một đỉnh trong V va u là đỉnh kề của v , sao cho u cũng thuộc V . Khi đó ta dán nhãn cho tất cả các đỉnh của đồ thị là Chọn một đỉnh v thuộc tập V để bắt đầu duyệt . Gán nhãn đỉnh v này lav đã được duyệt . Chọn đỉnh u trong tập V kề với đỉnh v mà nhãn là Duyệt qua đỉnh u và gán nhãn u là Tiếp tục quá trình duyệt đến khi tất cả các đỉnh đồ thị có nhãn là Ví dụ áp dụng =(V , E) có V={1,2 ,3 ,4,5} được lưu vào bảng như sau : Trước tiên , ta gán nhãn tất cả các đỉnh là(chưa duyệt) . Khi đỉnh nào được duyệt qua thì ta cập nhật lại nhãn cho đỉnh đó là Các bước duyệt theo chiều sâu : Chọn một đỉnh từ danh sách các đỉnh của G . Ở đây ta chọn đỉnhlàm đỉnh đầu tiên để bắt đầu duyệt . Thực hiện DFS(2) : pro Gán nhãn cho đỉnhlàkhi duyệt qua nó , tìm thấy các đỉnh kề của đỉnhcó đỉnhcó nhãn làchưa được duyệt) . Lặp lại quá trình với đỉnh Thực hiện DFS(3) : Gán nhãn cho đỉnhlàkhi duyệt qua nó , tìm thấy các đỉnh kề của đỉnhcó đỉnhcó nhãn làchưa được duyệt) . Lặp lại quá trình với đỉnh Thực hiện DFS(1) : Gán nhãn cho đỉnhlàkhi duyệt qua nó , tìm thấy các đỉnh kề của đỉnhcó đỉnhcó nhãn làchưa được duyệt) . Lặp lại quá trình với đỉnh Thực hiện DFS(4) : Gán nhãn cho đỉnhlàkhi duyệt qua nó , tìm thấy các đỉnh kề của đỉnhcó đỉnhcó nhãn làchưa được duyệt) . Lặp lại quá trình với đỉnh Đến đây , tất cả các đỉnh đã duyệt qua nên ta dừng thuật toán . Xuất ra dãy các đỉnh đã duyệt như sau : 3 ,1,4,5 . Mã giả Xem thêm Tìm kiếm theo chiều sâu Tham khảo Nguyễn Tuấn Anh , Lý thuyết đồ thị và ứng dụng . Nhà xuất bản Giáo dục Việt Nam Dương Anh Đức , Nhập môn Cấu Trúc Dữ Liệu và Giải Thuật , Đại Học Khoa Học Tự Nhiên Tham khảo Liên kết ngoài Video demo thuật toán DFS Giải thuật lý thuyết đồ thị Giải thuật tìm kiếm