Thực hành Lý thuyết đồ thị - Duyệt đồ thị (P2)

Thực hành Lý thuyết đồ thị - Duyệt đồ thị (P2)

Sử dụng các phương pháp duyệt đồ thị để cài đặt thành các hàm duyệt đồ thị:

  • Duyệt theo chiều sâu có sử dụng đệ quy
  • Duyệt theo chiều sâu không sử dụng đệ quy, sử dụng STACK thay thế
  • Duyệt theo chiều rộng sử dụng cấu trúc QUEUE

Xem thêm thuật toán tìm thành phần liên thông

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

Source code các hàm

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

void DFS(int v)

{

     ChuaXet[v] = 1;

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

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

                             if ( ChuaXet[u]==0 )

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

}

//Thu tuc duyet DFS, duyet theo chieu sau su dung STACK de khu de quy.

void DFS0DeQuy(int v)

{

     int STACK[MaxV], topS = 0;            //Khoi tao STACK voi mot STACT rong

     STACK[topS++] = v;             //Dua dinh v vao dinh STACK

     ChuaXet[v] = 0;                      //Xem nhu da duyet dinh v

     while(topS > 0)                          //Lap trong khi STACK khac rong

     {

                 v = STACK[--topS];      //Lay mot dinh v tu dinh cua STACK ra

                

                 for (int u=V-1; u>=0; u--)

                             if (A[v][u] != 0)                       //Xet dinh u ke voi dinh v

                                         if ( ChuaXet[u]==0 )

                                         {

                                                     STACK[topS++] = u; //Dua u vao dinh STACK

                                                     ChuaXet[u] = 1;          //Xem dinh nay la da xet.

                                         }

     }

}

//Thu tuc duyet DFS, duyet theo chieu rong su dung QUEUE de chay khong de quy.

void BFS0DeQuy(int v)

{

     int QUEUE[MaxV], topQ=0, bottomQ=0;    //Khoi dau voi mot QUEUE rong

     QUEUE[topQ++] = v;            //Dua dinh v vao QUEUE, xem no nhu la da xet

     ChuaXet[v] = 1;

     while ( bottomQ < topQ )       //Lap trong khi QUEUE khac rong

     {

                 v = QUEUE[bottomQ++];     //Lay dinh v tu day cua QUEUE

    

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

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

                                         if ( ChuaXet[u]==0 )

                                         {

                                                     QUEUE[topQ++] = u;      // Dua u vao dinh cua QUEUE

                                                     ChuaXet[u] = 1;

                                         }

     }

}

Xây dựng hàm main( ) tiến hành gọi thuật toán duyệt đồ thị:

+ Gọi hàm đọc, xuất ma trận kề của đồ thị

+ Gọi hàm duyệt đồ thị với đỉnh bất kỳ, ví dụ như đỉnh đầu tiên ( đỉnh 0 )

+ In ra các thành phần đã duyệt được trong đồ thị bơi

Source code hàm main( )

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

{

     DocMTKe("D:\\Dothi_1.txt", A, V);

     XuatMTKe(A, V);

 

     memset(ChuaXet, 0, sizeof(ChuaXet) );

     DFS0DeQuy(v);

 

     printf( "Các dinh da duyet: " );

                 if (ChuaXet[j] == tp)

                             printf( "%d  ", v+1 );

     getch ( );

}

Tạo mới file đồ thị D:\\Graph_1.TXT  ở dạng ma trận kề, ví dụ:

13

0   1   0   1   0   0   0   0   0   0   0   1   0

1   0   0   1   0   0   0   0   0   0   0   0   0

0   0   0   0   0   0   1   0   0   0   0   0   0

1   1   0   0   0   1   1   0   0   0   0   0   0

0   0   0   0   0   1   0   1   1   0   0   0   0

0   0   0   0   1   0   1   0   0   0   0   0   1

0   0   1   1   0   1   0   0   0   0   0   0   0

0   0   0   0   1   0   0   0   1   0   0   0   0

0   0   0   0   1   0   0   1   0   0   0   0   0

0   0   0   0   0   0   0   0   0   0   1   1   0

0   0   0   0   0   0   0   0   0   1   0   1   0

1   0   0   0   0   0   0   0   0   1   1   0   0

0   0   0   0   0   1   0   0   0   0   0   0   0

Bạn thấy bài viết này như thế nào?: 
Average: 10 (1 vote)
Ảnh của Khanh Hoang

Khanh Hoang - Kenn

Kenn is a user experience designer and front end developer who enjoys creating beautiful and usable web and mobile experiences.

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 + 3 =
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

 
Nhóm Mua có thể hoạt động trở lại?

www.Nhommua.com có thể hoạt động trở lại?

Những ngày qua, tình hình công ty Nhóm Mua không có nhiều chuyển biến mới, khiến những lo ngại của người dùng và các nhà cung cấp về khả năng hoạt động trở lại của công ty này ngày càng giảm sút.

Google chuẩn bị cắt giảm nhân sự và cơ cấu lại Motorola

Google cơ cấu lại công ty con Motorola Mobility

Google vừa cho biết đã gởi hồ sơ lên Ủy ban Chứng khoán và Hối đoái về kế hoạch cắt giảm nhân sự và cơ cấu lại công ty con Motorola Mobility của họ.

Thiết kế Drupal website: www.PopSci.com

Thiết kế Drupal website: www.PopSci.com

Made with Drupal 5 this site is still an awesome example of successful implementation. The owners of this site are not going to upgrade it until D8 is in production.

Wordpress Freelancer

 

Wordpress Freelancer