Bài toán tìm kiếm đường đi trên đồ thị
G = (V, U) là đơn đồ thị (có hướng hoặc vô hướng). V = {1,. ., n} là tập các đỉnh, U là tập cạnh (cung). Với s, t € V, tìm tất cả các đường đi từ s đến t. Các thuật toán tìm kiếm cơ bản : Thuật toán DFS : Tìm kiếm theo chiều sâu. Thuật ...
G = (V, U) là đơn đồ thị (có hướng hoặc vô hướng). V = {1,. ., n} là tập các đỉnh, U là tập cạnh (cung). Với s, t € V, tìm tất cả các đường đi từ s đến t.
Các thuật toán tìm kiếm cơ bản :
Thuật toán DFS : Tìm kiếm theo chiều sâu.
Thuật toán BFS : Tìm kiếm theo chiều rộng.
Ý tưởng
Thuật toán DFS tiến hành tìm kiếm trong đồ thị theo chiều sâu. Thuật toán thực hiện việc thăm tất cả các đỉnh có thể đạt được cho tới đỉnh t từ đỉnh s cho trước. Đỉnh được thăm càng muộn sẽ càng sớm được duyệt xong (cơ chế LIFO -Vào Sau Ra Trước). Nên thuật toán có thể tổ chức bằng một thủ tục đệ quy quay lui
Mô tả thuật toán
Input G = (V,U), s, t
Output Tất cả các đường đi từ s đến t (nếu có). DFS ( int s) ?
for ( u = 1; u <= n; u++)
{
if (chấp nhận được)
{
Ghi nhận nó;
if (u ≠ t) DFS(u);
else In đường đi;
bỏ việc ghi nhận;
}
}
Ý tưởng
Thuật toán BFS tiến hành tìm kiếm trên đồ thị theo chiều rộng. Thuật toán thực hiện việc thăm tất cả các đỉnh có thể đạt được cho tới đỉnh t từ đỉnh s cho trước theo từng mức kề. Đỉnh được thăm càng sớm thì sẽ càng sớm được duyệt xong (cơ chế FIFO - Vào Trước Ra Trước).
Mô tả thuật toán
Input G = (V,E), s, t € V;
Output
Đường đi từ s đến t.
Mô tả :
- . . .
Thuật toán có không quá n bước lặp; một trong hai trường hợp sau xảy ra :
- Nếu với mọi i, t ? Ai : không có đường đi từ s đến t;
- Ngược lại, t ? A(m) với m nào đó. Khi đó tồn tại đường đi từ s tới t, và đó là
một đường đi ngắn nhất từ s đến t.
Trong trường hợp này, ta xác định được các đỉnh trên đường đi bằng cách
quay ngược lại từ t đến các đỉnh trước t trong từng các tập trước cho đến khi gặp s.
Minh hoạ :
Cho đơn đồ thị có hướng :
