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

1. Thuật toán tìm kiếm theo chiều sâu. (Depth First Search)

  • Ta viết một thủ tục đệ quy DFS(a) mô tả việc duyệt từ đỉnh a bằng cách thăm đỉnh a và tiếp tục quá trình duyệt DFS(b) với b là một đỉnh chưa thăm kề với a. Giải thuật tiếp tục cho tới khi gặp được đỉnh cần tìm hoặc tới một nút không có con. Khi đó giải thuật quay lui về đỉnh vừa mới tìm kiếm ở bước trước.
  • Để không một đỉnh nào bị liệt kê tới hai lần, ta sử dụng kỹ thuật đánh dấu, mỗi lần thăm một đỉnh, ta đánh dấu đỉnh đó lại để các bước duyệt đệ quy kế tiếp không duyệt lại đỉnh đó nữa

2 Thuật toán tìm kiếm theo chiều rộng. ( Breadth Fist Search)

  • Tư tưởng của giải thuật này là ” lên lịch trình” thăm các nút. Việc thăm một đỉnh sẽ lên lịch duyệt các đỉnh kề nó sao cho thứ tự duyệt là ưu tiên chiều rộng (đỉnh nào gần S hơn sẽ được duyệt trước)

 

 

The following two tabs change content below.

phuongtn