Khác biệt giữa bản sửa đổi của “Duyệt đồ thị”
Nội dung được xóa Nội dung được thêm vào
Không có tóm lược sửa đổi |
n Tại sao trang này lại trong thể loại:bản mẫu viết bài?? |
||
Dòng 125: | Dòng 125: | ||
[http://www.youtube.com/watch?v=5AN55O8cF8E Video demo thuật toán DFS] |
[http://www.youtube.com/watch?v=5AN55O8cF8E Video demo thuật toán DFS] |
||
{{Commonscat|Depth-first search}} |
{{Commonscat|Depth-first search}} |
||
[[Thể_loại:Bản mẫu viết bài]] |
|||
[[Thể loại:Giải thuật lý thuyết đồ thị]] |
[[Thể loại:Giải thuật lý thuyết đồ thị]] |
||
[[Thể loại:Giải thuật tìm kiếm]] |
[[Thể loại:Giải thuật tìm kiếm]] |
Phiên bản lúc 05:02, ngày 8 tháng 7 năm 2013
Bài viết hoặc đoạn này cần người am hiểu về thiếu đoạn mở đầu trợ giúp biên tập mở rộng hoặc cải thiện. |
Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. |
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(Depth Frist 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
Danh sách các đỉnh kề của đồ thị G=(V,E) có V={1,2,3,4,5} được lưu vào bảng như sau:
Đỉnh | Các đỉnh kề |
---|---|
1 | 2,3,4,5 |
2 | 3,4,5 |
3 | 1,2 |
4 | 1,2,5 |
5 | 1,2,4 |
- 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):
Đỉnh | Các đỉnh kề | Nhãn |
---|---|---|
1 | 2,3,4,5 | 0 |
2 | 3,4,5 | 1 |
3 | 1,2 | 0 |
4 | 1,2,5 | 0 |
5 | 1,2,4 | 0 |
- 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):
Đỉnh | Các đỉnh kề | Nhãn |
---|---|---|
1 | 2,3,4,5 | 0 |
2 | 3,4,5 | 1 |
3 | 1,2 | 1 |
4 | 1,2,5 | 0 |
5 | 1,2,4 | 0 |
- 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):
Đỉnh | Các đỉnh kề | Nhãn |
---|---|---|
1 | 2,3,4,5 | 1 |
2 | 3,4,5 | 1 |
3 | 1,2 | 1 |
4 | 1,2,5 | 0 |
5 | 1,2,4 | 0 |
- 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):
Đỉnh | Các đỉnh kề | Nhãn |
---|---|---|
1 | 2,3,4,5 | 1 |
2 | 3,4,5 | 1 |
3 | 1,2 | 1 |
4 | 1,2,5 | 1 |
5 | 1,2,4 | 0 |
- 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ả
Void DFS ( int v)
|
Xem thêm
Tài liệu tham khảo
- Nguyễn Tuấn Anh, Lý thuyết đồ thị và ứng dụng. NXB 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
Liên kết ngoài
Wikimedia Commons có thêm hình ảnh và phương tiện truyền tải về Duyệt đồ thị. |