Thuật toán về tìm đường đi giữa hai đỉnh của đồ thị bằng C/C++

Thuật toán về tìm đường đi giữa hai đỉ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:

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

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ề 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

 

Bạn thấy bài viết này như thế nào?: 
Average: 10 (1 vote)
Ảnh của Tommy Tran

Tommy Tran owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 

Tìm hiểu các câu lệnh trong Turbo Pascal, Borland Pascal

Ngưng thực hiện chương trình và trở về hệ điều hành.

Python - Chia sẻ file cực nhanh trong mạng nội bộ với 1 dòng lệnh

Python - Chia sẻ file cực nhanh trong mạng nội bộ với 1 dòng lệnh

Người dùng Linux thực ra không thiếu lựa chọn để chia sẻ file. Ta có thể dùng chia sẻ FTP, NFS mounting truyền thống của Unix, có thể tạo SSH server và dùng SFTP truy cập an toàn

5 Thương vụ mua lại "khôn ngoan" nhất của Apple

5 Thương vụ mua lại "khôn ngoan" nhất của Apple

Cùng ngược dòng thời gian để điểm lại những thương vụ "làm nên lịch sử" của Apple!