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

 
[Download] Visual Foxpro 9.0

[Download] phần mềm Visual Foxpro 9.0

Visual FoxPro, ký hiệu vắn tắt là VFP, là một hệ quản trị cơ sở dữ liệu (Database Management System -DBMS) trực quan.

HTML Injection – The Cross-Site Scripting (XSS)

HTML Injection – The Cross-Site Scripting (XSS)

XSS – Có lẽ mọi người đã biết. Mình chỉ xin tổng hợp lại một số kiến thức cơ bản dưới đây .

Martina Colombari tiết lộ sở thích sex của cựu danh thủ Costacurta - CLB AC Milan

Hoa hậu nước Ý năm 1991 Martina Colombari vừa hé lộ cuộc sống riêng tư với chồng là cựu danh thủ Alessandro Costacurta, và thừa nhận chuyện “sex” với cầu thủ này đã huỷ hoại

Tomdesgin.vn

 

Drupal Services