Thực hành Lý thuyết đồ thị - Thành phần liên thông (P3)

Thực hành Lý thuyết đồ thị - Thành phần liên thông (P3)

Để tìm số thành phần liên thông, thì mỗi lầ duyệt hãy gán cho mỗi thành phần liên thông một chỉ số vào giá trị của mảng ChuaXet, thay vì luôn ghi giá trị là 1. Các đỉnh của cùng thành phần liên thông sẽ có giá trị lưu trong ChuaXet giống nhau.

Các bước tiến hành:

1.  Truyền tham so nSoTPLT ve thành phần liên thông đang duyệt cho các hàm duyệt, cụ thể là:

  • void DFS0DeQuy(int v, int nSoTPLT)
  • void BFS0DeQuy(int v, int nSoTPLT)
  • void DFS0DeQuy(int v, int nSoTPLT)

2. Thay thế chỉ số index cho các thành phần liên thông trong các hàm duyệt:

Thay thế các dòng gán ChuaXeti = 0 thành ChuaXet[i ] = nSoTPLT.

Ví dụ:

ChuaXet[v] = nSoTPLT;                    //Xem dinh nay la da xet.

Chỉnh sửa lại hàm main ( ) để in ra tất cả các đỉnh của từng thành phần liên thông

int main(int argc, char* argv[])

{

     int nSoTPLT = 0;

 

     DocMTKe("D:\\Graph_1.TXT", A, V);

     XuatMTKe(A, V);

 

     for (int v=0; v<V; v++)

                 if (ChuaXet[v] == 0)

                             DFS0DeQuy(v, ++nSoTPLT);

 

     for (int tp=1; tp<=nSoTPLT; tp++)

     {

                 cout<<"\nTPLT thu "<<tp<<" gom dinh:";

                 for (v=0; v<V; v++)

                             if (ChuaXet[v] == tp)

                                         cout<<v+1<<" ";

                 cout<<"\n";

     }

}

Tìm đường đi

+ Khai báo mảng lưu vết :

int DinhTruoc[MaxV];

+ Bổ sung để hàm duyệt DFS lưu vết tìm đường đi:

//Thu tuc duyet DFS, duyet theo chieu sau su dung ky thuat de quy.

void DFS(int v)

{

     ChuaXet[v] = nSoTPLT;

     for ( int u=0; u<V; u++ )

                 if ( A[v][u]!=0 )                       //The hien u la dinh ke cua v

                             if ( ChuaXet[u]==0 )

                             {

                                         DinhTruoc[u]  = v;

                                         DFS( u );         //Dinh u chua duoc duyet qua==> Duyet u

                             }

}

Hoàn thiện hàm main ( ) để tìm đường đi từ s đến t.

int main(int argc, char* argv[])

{

     int nSoTPLT = 0;

 

     DocMTKe("D:\\1.TXT", A, V);

     XuatMTKe(A, V);

 

     int s, t;

     cout<<"Nhap dinh bat dau, dinh ket thuc:";  cin>>s>>t;

     s--;   t--;

     DFS(s);

 

     int DuongDi[MaxV], k = 0;

     DuongDi[k++] = t;

     while ( DinhTruoc[ DuongDi[k-1] ] != s)

                 DuongDi[k++] = DinhTruoc[ DuongDi[k-1] ];

     DuongDi[k++] = s;

 

     cout<<"\nDuong di tu "<<s<<" den "<<t<<" la: ";

     for ( int i=k-1; i>=0; i-- )

                 cout<<DuongDi[ i ] +1<<"  ";

     getch( );

}
Tags: 
Bạn thấy bài viết này như thế nào?: 
Average: 10 (2 votes)
Ả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: [email protected]
  • Telegram Messenger: https:/t.me/tommytran0401

Bình luận (0)

 

Add Comment

Plain text

  • No HTML tags allowed.
  • Các địa chỉ web và email sẽ tự động được chuyển sang dạng liên kết.
  • Tự động ngắt dòng và đoạn văn.
CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
3 + 14 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.

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

 
Giới thiệu quảng cáo PPC-PPA là gì?

Giới thiệu quảng cáo PPC-PPA là gì?

SEM là từ viết tắt của Search Engine Marketing, dịch và hiểu theo nghĩa tiếng Việt là phương pháp tiếp thị thông qua các công cụ tìm kiếm. SEM là một hình thức Internet Marketing và là một phương pháp marketing nhằm tăng sự hiện diện của bạn hay doanh nghiệp, tổ chức thông qua công cụ tìm kiếm.

Jurgen Klopp và thách thức đưa bóng đá nâng tầm gegenpressing

Jurgen Klopp và thách thức đưa bóng đá nâng tầm gegenpressing

Ngay sau khi chính thức giành đủ số điểm để trở thành nhà vô địch mới của Giải ngoại hạng Anh mùa 2019-2020, #Liverpool của Klopp đã nhận thất bại bốn bàn không gỡ

Cải thiện performance trong Drupal 8 nhờ New Quicklink module

Cải thiện performance trong Drupal 8 nhờ New Quicklink module

First, links in the user’s viewport are detected. These are links that the user might want to visit next. When the browser goes idle, the content from the links begins to be saved in the cache

Wordpress Freelancer

 

Wordpress Freelancer