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
n Tại sao trang này lại trong thể loại:bản mẫu viết bài?? |
nKhông có tóm lược sửa đổi |
||
Dòng 25:
| 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.
<big>'''Thực hiện DFS(2):'''</big><br />
[[File:Duyet dinh 2.png|thumb|dothi2]]
Dòng 44:
| 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.
<big>'''Thực hiện DFS(3):'''</big><br />
[[File:Dothi3.png|thumb|Duyet_dinh3]]
Dòng 61:
| 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.
<big>'''Thực hiện DFS(1):'''</big><br />
[[File:Dothi4.png|thumb|Duyet_dinh1]]
Dòng 78:
| 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.
<big>'''Thực hiện DFS(4):'''</big><br />
[[File:Dothi5.png|thumb|Duyet_dinh4]]
Dòng 95:
| 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ả ==
Dòng 102:
| Void DFS ( int v)<br />
:{
::Gắn nhãn v đã duyệt;
::For ( u = 1; u <= n; u++)
::: If( u tồn tại trong danh sách kề V)
::::If( u có nhãn là 0)
::::{
::::: Xử lí đỉnh u; //Gắn nhãn 1
::::: DFS ( u);
::::}
Dòng 125:
[http://www.youtube.com/watch?v=5AN55O8cF8E Video demo thuật toán DFS]
{{Commonscat|Depth-first search}}
[[Thể loại:Giải thuật lý thuyết đồ thị]]
[[Thể loại:Giải thuật tìm kiếm]]
| |||