[Thuật toán] Tìm đường đi giữa hai đỉnh của đồ thị.

Bài toán: Cho đồ thị G=(V, E). Trong đó V là tập đỉnh, E là tập cạnh của đồ thị. Hãy tìm đường đi từ đỉnh s ∈ Vtới đỉnh t ∈ V.
Thủ tục BFS(s) hoặc DFS(s) cho phép ta duyệt các đỉnh cùng một thành phần liên thông với s. Như vậy, nếu trong số các đỉnh liên thông với s chứa t thì chắc chắn có đường đi từ s đến t. Nếu trong số các đỉnh liên thông với s không chứa t thì không tồn tại đường đi từ s đến t. Do vậy, chúng ta chỉ cần gọi tới thủ tục DFS(s) hoặc BFS(s) và kiểm tra xem đỉnh t có thuộc thành phần liên thông với s hay không. Điều này được thực hiện đơn giản thông qua mảng trạng thái chuaxet[]. Nếu chuaxet[t] =False thì có nghĩa t cùng thành phần liên thông với s. Ngược lại chuaxet[t] = True thì t không cùng thành phần liên thông với s.
Để ghi nhận đường đi từ s đến t, ta sử dụng một mảng truoc[] thiết lập giá trị ban đầu là 0.Trong quá trình duyệt, ta thay thế giá trị của truoc[v] để ghi nhận đỉnh đi trước đỉnh v trong đường đi tìm kiếm từ s đến v. Khi đó, trong thủ tục DFS(v) ta chỉ cần thay đổi lại như sau:

void DFS( int v){ 
 chuaxet[v]:= FALSE; 
 for ( u ∈ke(v) ) { 
  if (chuaxet[u] ) { 
   truoc[u]=v; 
   DFS(u); 
  } 
 } 
}

Đối với thủ tục BFS(v) được thay đổi lại như sau:

void BFS(int u){ 
 queue = φ; 
 u <= queue; /*nạp u vào hàng đợi*/
 chuaxet[u] = false;/* đổi trạng thái của u*/
 while (queue ≠ φ) { /* duyệt tới khi nào hàng đợi rỗng*/
  queue<=p; /*lấy p ra từkhỏi hàng đợi*/
  for (v ∈ke(p) ) {/* đưa các đỉnh v kềvới p nhưng chưa được xét vào hàng đợi*/
   if (chuaxet[v] ) { 
    v<= queue; /*đưa v vào hàng đợi*/
    chuaxet[v] = false;/* đổi trạng thái của v*/
    truoc[v]=p; 
   } 
  } 
 } /* end while*/
}/* end BFS*/

Kết quả đường đi được đọc ngược lại thông qua thủ tục Result() như sau:

void Result(void){ 
 if(truoc[t]==0){ 
  <Không có đường đi từs đến t>; 
  return; 
 } 
 j = t; 
 while(truoc[j]!=s){ 
  <thăm đỉnh j>; 
  j=truoc[j]; 
 } 
 <thăm đỉnh s>; 
} 

Ví dụ. Tìm đường đi từ đỉnh 1 đến đỉnh 7 bằng thuật toán tìm kiếm theo chiều rộng với đồ thị dưới đây:

Tìm đường đi giữa đỉnh 1 đến đỉnh 7 của đồ thị

Ta có, BFS(1) = 1,2,3,11,4,6,12,13,7,8,9,10,5. Rõ ràng chuaxet[7] = True nên có đường đi từ đỉnh 1 đến đỉnh 7. Bây giờ ta xác định giá trị trong mảng truoc[] để có kết quả đường đi đọc theo chiều ngược lại. Truoc[7] = 6; truoc[6] = 2; truoc[2] =1=> đường đi từ đỉnh 1 đến đỉnh 7 là 1 =>2=>6=>7.
Chương trình cài đặt.

#include<iostream>
#include<conio.h>
using namespace std;
#define MAX  100 
#define TRUE  1 
#define FALSE  0
int n;//số đỉnh của đồ thị.
int truoc[MAX], chuaxet[MAX], queue[MAX];//mảng đánh dấu.
int A[MAX][MAX];// ma trận kề của đồ thị.
int s;//đỉnh đầu.
int t;//đỉnh cuối. 

void Init(void){ 
 freopen("lienth.IN", "r",stdin); 
 cin>>n; 
 cout<<"So dinh do thi: "<<n<<endl; 
 cin>>s>>t;
 cout<<"Dinh dau:"<<s<<endl;
 cout<<"Dinh cuoi:"<<t<<endl;
 for(int i=1; i<=n;i++){ 
  for(int j=1; j<=n;j++){ 
   cin>>A[i][j]; 
  }
 } 
 for(int i=1; i<=n;i++){ 
  chuaxet[i]=TRUE; 
  truoc[i]=0; 
 }
 fclose(stdin);
} 
void Result(void){ 
 if(truoc[t]==0){ 
  cout<<"Khong co duong di tu "<<s<< " den "<<t; 
  return; 
 } 
 cout<<"Duong di tu "<<s<<" den "<<t<<" la: "; 
 int j = t;
 cout<<t<<"<="; 
 while(truoc[j]!=s){ 
  cout<<truoc[j]<<"<="; 
  j=truoc[j]; 
 } 
 cout<<s; 
} 
/* Breadth First Search */
void BFS(int s) { 
 int dauQ, cuoiQ, u;
 dauQ=1;cuoiQ=1;//khởi tạo queue.
 queue[dauQ]=s;chuaxet[s]=FALSE; //thêm đỉnh đầu vào queue.
 while (dauQ<=cuoiQ){//queue chưa rỗng.
  u=queue[dauQ];//lấy đỉnh u trong queue.
  dauQ=dauQ+1; 
  for (int p=1; p<=n;p++){ 
   if(A[u][p] && chuaxet[p]){ 
    cuoiQ=cuoiQ+1;
    queue[cuoiQ]=p; 
    chuaxet[p]=FALSE;
    truoc[p]=u; 
   } 
  } 
 } 
} 

void main(void){ 
 Init();
 BFS(s); 
 Result();
 getch(); 
}

Ma trận liền kề được tải về tại đây.
Output của chương trình.

So dinh cua do thi: 13
Dinh dau: 1
Dinh Cuoi: 7
Duong di tu 1 den 7 la: 7<=6<=2<=1