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 (2 votes)
Ả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

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.

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

 
Không nên cloning database, dev-stage-production workflow

Không nên cloning database, dev-stage-production workflow

However, in a dev-stage-production workflow, the database is often still periodically cloned back upstream:

Hướng dẫn Reloading a View + arguments với Ajax trong Drupal 7

Hướng dẫn Reloading a View + arguments với Ajax trong Drupal 7

If we drill down this file and analyze it, we will understand some of the Views' ajax functionality. Lets take a case and see how we can reuse Views' Ajax.

Thành phần cơ bản của Drupal Terminology

Thành phần cơ bản của Drupal Terminology

 The faster you learn to understand and speak Drupaleze, the easier it will be to communicate with other Drupal developers more effectively. To that end, here are a list of terms commonly used in the Drupal world:

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

 

Diet con trung