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( );

}