[myhanh]

TÌM ĐƯỜNG ĐI VÀ KIỂM TRA TÍNH LIÊN THÔNG
A.Bài toán tìm đường đi giữa hai đỉnh:
Giả sử s và t là hai đỉnh nào đó của một đồ thị hãy tìm đường đi từ s đến t.
Nhận xét:
-DFS(v) và BFS(v) sẽ cho phép thăm tất cả các đỉnh cùng một thành phần liên thông với s . Vì vậy sau khi thực hiện xong thủ tục nếu chuaxet[t]=true thì có nghĩa là không có đường đi từ s đến t. Ngược lại thì t thuộc cùng một thành phần liên thông với s.
-Dùng biến truoc[v] để ghi nhận đỉnh đi trước v trong đường đi tìm kiếm từ s đến t. Vì vậy cần sữa lại câu lệnh IF như sau:

DFS(v) -> IF chuaxet[u] THEN
                   BEGIN
                        truoc[u]:=v;
                        DFS(u);
                   END;
BFS(v) -> IF chuaxet[u] THEN
                   BEGIN
                        Queue <=u;
                         chuaxet[u]:=false;
                       truoc[u]:=p;
                 END;

Đường đi cần tìm kiếm sẽ được hồi phục theo qui tắc sau:
t <-p1:=truoc[t] <-p2:=truoc[p1]...<-s
* Chú ý: Đường đi tìm được theo tuấn toán tìm kiếm theo chiều rộng là đường đi ngắn nhất hiểu theo số cạnh từ s->t.