Thư Viện Tài Liệu Tổng Hợp

TaiLieuTongHop.Com - Kho tài liệu tổng hợp hoàn toàn miễn phí dành cho mọi người

Hãy sử dụng chức năng tìm kiếm bên dưới để tìm tài liệu trước khi post yêu cầu liên diễn đàn!

Loading

VanMau.VN - Thư viện văn mẫu Việt Nam
+ Viết bài mới  + Trả lời bài viết
 
LinkBack Ðiều Chỉnh Xếp Bài
  #1  
Old 04-11-2012, 01:52 PM
Senior Member
 
Tham gia: Mar 2012
Tổng số bài gởi: 1,184


Các thuật toán tìm kiếm trên đồ thị

Các thuật toán tìm kiếm trên đồ thị


Thuật toán tìm kiếm theo chiều sâu

Tư tưởng chính của thuật toán là: Giả sử chúng ta đang xét trên đồ thị G(V,E). Từ một đỉnh u V hiện thời nào đó ta sẽ thăm tới đỉnh kề v của u và quá trình được lặp lại đối với đỉnh v. ở bước tổng quát, giả sử hiện tại đang xét đỉnh u0, chúng ta sẽ có hai khả năng sẽ xảy ra:

-Nếu như tồn tại một đỉnh v0 kề với u0 mà chưa được thăm thì đỉnh v0 đó sẽ trở thành đỉnh đã thăm và quá trình tìm kiếm lại bắt đầu từ đỉnh v0 đó.

-Ngược lại, nếu mọi đỉnh kề với u0 đều đã thăm thì ta sẽ quay trở lại đỉnh mà trước đó ta đến đỉnh u0 để tiếp tục quá trình tìm kiếm.

Như vậy, trong quá trình thăm đỉnh bằng thuật toán tìm kiếm theo chiều sâu, đỉnh được thăm càng muộn càng sớm được duyệt xong (Cơ chế Last In First Out - Vào sau ra trước). Do đó, ta có thể tổ chức quá trình này bằng một thủ tục đệ quy như sau:

Procedure DFS(u);
Begin
Visit(u);
Daxet[u]:=True;
For v Kề(u do
if not Daxet[v] then DFS(v);
End;
Và thủ tục duyệt hệ thống toàn bộ đỉnh của đồ thị sẽ là:
Procedure Find;
Begin
Fillchar(Daxet,SizeOf(Daxet),False);
For u V do
If not Daxet[u] then DFS(u);
End;

Dễ nhận thấy rằng, mỗi lần gọi DFS(u) thì toàn bộ các đỉnh cùng thành phần liên thông với u sẽ được viếng thăm. Thủ tục Visit(u) là thao tác trên đỉnh u trong từng bài toán đặt ra cụ thể.

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

Thuật toán này thực ra là sự cải biến về thứ tự duyệt đỉnh trên đồ thị của tìm kiếm theo chiều sâu bằng cách thay vì dùng một STACK thì ta lại dùng một hàng đợi QUEUE để kết nạp đỉnh được thăm. Như vậy, đỉnh được thăm càng sớm sẽ càng sớm trở thành duyệt xong (cơ chế First In First Out - Vào trước ra trước). Thủ tục được mô tả dưới đây:

Procedure BFS(u);
Begin
Queue:=Empty
Kết nạp u vào Queue;
Daxet[u]:=True;
While Queue<>Empty do
Begin
Lấy v từ Queue;
Visit(v);
For w Kề(v) do
If not Daxet[w] then
Begin
Kết nạp w vào Queue;
Daxet[w]:=True;
End;
End;
End;
Ta có thủ tục tìm kiếm theo chiều rộng là:
Procedure Find;
Begin
Fillchar(Daxet,SizeOf(Daxet),False);
For u V do
If not Daxet[u] then BFS(u);
End;

Tương tự như thuật toán tìm kiếm theo chiều sâu, ở thuật toán này mỗi lần gọi thủ tục BFS(u) thì mọi đỉnh cùng thành phần liên thông với u sẽ được thăm. Thủ tục Visit(u) như đã nói ở trên.
Để hiểu rõ hơn về thuật toán, các bạn có thể xem thêm bài viết "Thuật toán Loang" của cùng tác giả ở số báo 2(7) năm 2000. Xin chân thành cảm ơn.

Từ hai thuật toán trên, rất nhiều bài toán cơ bản trên đồ thị được giải quyết rất dễ dàng. Vì khuôn khổ bài báo, xin trình bầy một số bài toán kinh điển. Một số vấn đề khác, sẽ trình bày ở một bài báo khác.

Download và Xem Tài Liệu đầy đủ :

[Thành viên đã đăng kí mới được xem link. ]

__________________
** **
** G.Su Thanh **
xem xong an nut Thanks nhe bạn!!!
------------------------------------------------------------------------------------------------
Trả Lời Với Trích Dẫn