Buiminhbang
Tham gia ngày 6 tháng 5 năm 2013
Nội dung được xóa Nội dung được thêm vào
Không có tóm lược sửa đổi |
|||
Dòng 1:
== 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.
Dòng 95:
: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.<br />
:Đế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ả ==
{| class="wikitable"
|-
| Void DFS ( int v)<br />
:{
::Gắn nhãn v đã duyệt;<br />
::For ( u = 1; u <= n; u++)<br />
::: If( u tồn tại trong danh sách kề V)<br />
::::If( u có nhãn là 0)<br />
::::{
::::: Xử lí đỉnh u; //Gắn nhãn 1<br />
::::: DFS ( u);<br />
::::}
:}
|}
== 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 TP.HCM
# Tìm kiếm theo chiều sâu[[http://vi.wikipedia.org/wiki/T%C3%ACm_ki%E1%BA%BFm_theo_chi%E1%BB%81u_s%C3%A2u]]
== Liên kết ngoài ==
[http://www.youtube.com/watch?v=5AN55O8cF8E Video demo thuật toán DFS]
| |||