Thuật toán tìm kiếm theo chiều rộng và chiều sâu

[asimothat]

Hôm nay học toán rời rạc có một bài toán mà đáp số thầy trò khác nhau . Mình đọc sách làm kết quả khác với thầy giáo . Mong mọi người chỉ dẫn
Tìm thuật toán tìm kiếm theo chiều rộng và chiều sâu.
Cho graph 1(2,6) ; 2(1,3) ; 3(2,4,5) ; 4(3,8) ; 5(3,8) ; 6(1,7) ; 7(6) ; 8(4,5) .

Thầy tìm được tìm kiếm theo chiều rộng 1;2;6;3;7;4;5;8
Mình tìm được là 1;2;3;4;8;5.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[huynhcongbang]

Trước hết, vẽ cái hình minh họa cho dễ thấy:



Ý tưởng của hai thuật toán tìm theo chiều sâu (depth-first-search hay thường viết gọn là dfs) và tìm theo chiều rộng (breadth-first-search hay thường viết gọn là bfs) là ngược nhau.
Có thể nói tóm tắt là:
*Tìm theo chiều sâu: duyệt graph từ đỉnh đầu (root), xét các đỉnh kề với nó và cho vào danh sách v (đánh dấu là đã duyệt rồi) và mỗi lần đi như thế thì càng xa đỉnh đầu càng tốt.
*Tìm theo chiều rộng: cũng như trên nhưng đổi thành thì càng gần đỉnh đầu càng tốt.
Nếu so sánh về mặt implement thì tất nhiên một bên sẽ dùng stack, một bên dùng queue.

Nếu tìm theo chiều rộng thì kết quả chính là cách của thầy bạn giải đấy.
Có thể giải thích thế này:
-Đầu tiên root=1, cho vào v.
-Đỉnh kề với root là 2 và 6, duyệt 2 trước và đưa 2 vào danh sách v.
-Do điều kiện của bfs là duyệt càng gần root càng tốt nên ngay tại 2, ta không đi tiếp mà chuyển qua đỉnh kề root tiếp theo là 6, cho 6 vào v.
-Kế đến ta cũng không đi tiếp tại 6 mà quay về root, tại đây không còn đỉnh nào kề nữa nên chuyển qua 2, ta có 2 đỉnh kề là 1 và 3. Do 1 đã nằm trong v rồi nên duyệt 3 và cứ thế mà tiếp tục.

Cách duyệt của bạn dùng là dfs nhưng sau khi duyệt xong 5, ta quay về root, đỉnh kề với root vẫn còn là 6, ta duyệt tiếp 6 và 7 và hoàn tất chu trình là: 1;2;3;4;8;5;6;7.

Nếu bạn đang học Cấu trúc dữ liệu và thuật toán dùng Java thì test thử là biết ngay mà! Dưới đây là 2 chương trình bfs và dfs, bạn xem thử nha!
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]