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