Chương 2-Bài 13. Thuật toán Tìm đường đi giữa 2 đỉnh của Đồ thị bằng C/C++

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: 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ề lienth.IN

13
1 7
0    1    1    0    0    0    0    0    0    0    1    0    0
1    0    0    1    0    1    0    0    0    0    0    0    0
1    0    0    1    0    0    0    0    0    0    0    0    0
0    1    1    0    0    1    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0    1    1    0    0    0
0    1    0    1    0    0    1    1    0    0    0    0    0
0    0    0    0    0    1    0    0    0    0    0    0    0
0    0    0    0    0    1    0    0    0    1    0    0    0
0    0    0    0    1    0    0    0    0    0    0    0    1
0    0    0    0    1    0    0    1    0    0    0    0    0
1    0    0    0    0    0    0    0    0    0    0    1    1
0    0    0    0    0    0    0    0    0    0    1    0    1
0    0    0    0    0    0    0    0    1    0    1    1    0

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