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

Bình luận (0)

 

Add Comment

Filtered HTML

  • Các địa chỉ web và email sẽ tự động được chuyển sang dạng liên kết.
  • Các thẻ HTML được chấp nhận: <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Tự động ngắt dòng và đoạn văn.

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.
Image CAPTCHA
Enter the characters shown in the image.

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

 
Cuộc chiến iOS và Android - Ai sẽ giành chiến thắng ?

Cuộc chiến iOS và Android - Ai sẽ giành chiến thắng ?

Ai sẽ giành chiến thắng trong cuộc chiến hệ điều hành cho điện thoại: Apple iOS hay là Google Android ?

Black SEO tốt hay xấu ?

Black SEO tốt hay xấu ?

Nếu bạn là người nguyên cứu về SEO, black SEO có thể mở mang tầm mắt của bạn. Nếu bạn là người thực hiện SEO...

3 Modules giúp Debug Emails trong Drupal 7

3 Modules giúp Debug Emails trong Drupal 7

Debugging email issues in Drupal can be really painful. Problems can exist in multiple areas; like Drupal itself or your mail server.

Công ty diệt chuột T&C

 

Diet con trung