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

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.
1 + 0 =
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

 
Nokia N9 Preview and First Look

Nokia N9 Preview and First Look

Technology has spread its arms to endless horizons where everyday new inventions come into existence in this world.

5 tính năng và thủ thuật cho Safari 5 Hidden Features and Tricks of Safari

5 tính năng và thủ thuật cho Safari 5 Hidden Features and Tricks of Safari

Safari là một trình duyệt web tốt, có tốc độ lướt web nhanh, có nền tảng là WebKit và mang lại nhiều tính năng tuyệt vời của Apple

Thiết kế Out Of The Box

Thiết kế Out Of The Box

Bạn đã chán với layout với các cột và các hộp truyền thống. Trong bài này tôi xin giới thiệu một số mẫu thiết kế vượt khỏi những kiểu thiết kế cũ đem lại cảm giác rất ấn tượng, bí quyết ở cách sử dụng hình nền và bố trí văn bản hợp lý đã làm cho trang website thực sự thu hút.

Tomdesgin.vn

 

Drupal Services