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

 
Drupal Vs WordPress – CMS Nào Phù Hợp Cho Mình?

Drupal Vs WordPress – CMS Nào Phù Hợp Cho Mình?

Drupal và WordPress là mã nguồn mở hệ thống quản trị nội dung kỹ thuật số (CMS) mà có thể được sử dụng để quản lý trang web của bạn, thiết lập diễn đàn, viết blog hoặc cả bán hàng trực tuyến.

Samsung không có hứng thú với Firefox OS vừa ra mắt của Mozilla

Samsung không có hứng thú với Firefox OS vừa ra mắt của Mozilla

Một quan chức cấp cao của Samsung tuyên bố công khai tại MWC 2013 rằng Samsung không có hứng thú với việc tung ra các thiết bị chạy trên nền hệ điều hành Firefox OS vừa ra mắt của Mozilla.

Sony Ericsson Txt Pro Preview, a Full-touch Feature of Sony

Sony Ericsson Txt Pro Preview, a Full-touch Feature of Sony

In this competitive world of full-touch feature phones, every other service provider is manufacturing their best product for all the people in this world.

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

 

Diet con trung