24/05/2018, 16:57
Tìm đường đi và kiểm tra tính liên thông
Trong mục này ta xét ứng dụng các thuật toán tìm kiếm mô tả trong các mục trước vào việc giải bài toán cơ bản trên đồ thị: bài toán về tìm đường đi và bài toán về xác định tính liên thông của đô thị.7 Giả sử s và t là hai đỉnh nào đó của ...
Trong mục này ta xét ứng dụng các thuật toán tìm kiếm mô tả trong các mục trước vào việc giải bài toán cơ bản trên đồ thị: bài toán về tìm đường đi và bài toán về xác định tính liên thông của đô thị.7
Giả sử s và t là hai đỉnh nào đó của đồ thị. Hãy tìm đường đi từ s đến t.Như trên đã phân tích, thủ tục DFS(s) (BS(s)) sẽ cho thăm tất cả các đỉnh thuộc 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ì điều đó có nghĩa là không có đường đi từ s đến t, còn nếu Chuaxet[t]=false thì t thuộc cùng thành phần liên thông với s, hay nói một cách
