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

 
Zing.vn đứng đầu top 100 website Việt Nam

Zing.vn đứng đầu top 100 website Việt Nam

Theo số liệu từ DoubleClick Ad Planner - một công cụ miễn phí dành cho chiến lược quảng cáo trực tuyến do Google cung cấp, trong tháng 1-2012, lượng người dùng Internet tại Việt Nam là 23 triệu (chiếm 26% dân số Việt Nam) và lượt xem là 18,4 tỉ.

Steve Jobs chưa từng bị Apple sa thải

Steve Jobs chưa từng bị Apple sa thải

Chúng ta đều tin rằng Steve Jobs đã từng bị đuổi khỏi Ban giám đốc Apple và John Sculley – người mà Steve Jobs đưa về công ty - là người điều hành công ty thay ông.

Cập nhật hứơng dẫn SEO với 301 Redirect

Cập nhật hứơng dẫn SEO với 301 Redirect

Ắt hẳn khi thực hiện seo từ khóa, bạn sẽ gặp phải trường hợp một URL bạn đã chăm chút để đạt thứ hạng cao trên công cụ tìm kiếm, nhưng giờ URL đó lại bị thay đổi (do cập nhật website, ngôn ngữ mới, trang gốc bị xóa…). Bài viết này sẽ giúp bạn thực hiện điều đó.

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

 

Diet con trung