Nền tảng Kiến thức - Hành trang tới Tương lai
Card image

Chương 1-Bài 11. Duyệt cây theo chiều sâu DFS (Depth First Search)

Tác giả: Dương Nguyễn Phú Cường #10963
Ngày đăng: Hồi xưa đó
Lượt xem: 421

Duyệt cây theo chiều sâu DFS (Depth First Search)

Để kiểm tra việc duyệt mỗi đỉnh đúng một lần, chúng ta sử dụng một mảng chuaxet[] gồm n phần tử (tương ứng với n đỉnh), nếu đỉnh thứ đã được duyệt, phần tử tương ứng trong mảng chuaxet[] có giá trị FALSE. Ngược lại, nếu đỉnh chưa được duyệt, phần tử tương ứng trong mảng có giá trị TRUE. Thuật toán có thể được mô tả bằng thủ tục đệ qui DFS () trong đó: chuaxet - là mảng các giá trị logic được thiết lập giá trị TRUE.
void DFS( int v){ 

 Thăm_Đỉnh(v);

 chuaxet[v]:= FALSE; 

 for ( u ∈ke(v) ) { 

  if (chuaxet[u] ) DFS(u); 

 } 

}
Thủ tục DFS() sẽ thăm tất cả các đỉnh cùng thành phần liên thông với mỗi đỉnh đúng một lần. Để đảm bảo duyệt tất cả các đỉnh của đồ thị (có thể có nhiều thành phần liên thông), chúng ta chỉ cần thực hiện duyệt như sau:
for (i=1; i≤n ; i++)

 chuaxet[i]:= TRUE; /* thiết lập giá trị ban đầu cho mảng chuaxet[]*/

for (i=1; i≤n ; i++)

 if (chuaxet[i] )

  DFS( i);

Đồ thị - Tìm kiếm theo chiều sâu DFS

Đồ thị - Tìm kiếm theo chiều sâu DFS

Kết quả duyệt: 1, 2, 4, 3, 6, 7, 8, 10, 5, 9, 13, 11, 12
STT
Đỉnh bắt đầu duyệt
Các đỉnh đã duyệt
Các đỉnh chưa duyệt
1 DFS(1) 1 2,3,4,5,6,7,8,9,10,11,12,13
2 DFS(2) 1,2 3,4,5,6,7,8,9,10,11,12,13
3 DFS(4) 1,2,4 3,5,6,7,8,9,10,11,12,13
4 DFS(3) 1,2,4,3 5,6,7,8,9,10,11,12,13
5 DFS(6) 1,2,4,3,6 5,7,8,9,10,11,12,13
6 DFS(7) 1,2,4,3,6,7 5,8,9,10,11,12,13
7 DFS(8) 1,2,4,3,6,7,8 5,9,10,11,12,13
8 DFS(10) 1,2,4,3,6,7,8,10 5,9,11,12,13
9 DFS(10) 1,2,4,3,6,7,8,10,5 9,11,12,13
10 DFS(9) 1,2,4,3,6,7,8,10,5,9 11,12,13
11 DFS(13) 1,2,4,3,6,7,8,10,5,9,13 11,12
12 DFS(11) 1,2,4,3,6,7,8,10,5,9,13,11 12
13 DFS(12) 1,2,4,3,6,7,8,10,5,9,13,11,12 Ѳ

DFS.IN

13
0    1    1    0    0    0    0    0    0    0    1    0    0
1    0    0    1    0    1    0    0    0    0    0    0    0
1    0    0    1    0    0    0    0    0    0    0    0    0
0    1    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    1    0    1    0    0    1    1    0    0    0    0    0
0    0    0    0    0    1    0    0    0    0    0    0    0
0    0    0    0    0    1    0    0    0    1    0    0    0
0    0    0    0    1    0    0    0    0    0    0    0    1
0    0    0    0    1    0    0    1    0    0    0    0    0
1    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    0    0    0    0    0    0    0    1    0    1    1    0

Chương trình cài đặt bằng C/C++

#include<iostream>

#include<conio.h>

using namespace std;

#define MAX  100 

#define TRUE 1 

#define FALSE 0 

int G[MAX][MAX], n, chuaxet[MAX]; 

void Init(){ 

 freopen("DFS.IN", "r", stdin); 

 cin>>n; 

 cout<<"So dinh cua ma tran n = "<<n<<endl;

 //nhap ma tran lien ke.

 for(int i=1; i<=n;i++){ 

  for(int j=1; j<=n;j++){ 

   cin>>G[i][j]; 

  } 

 } 

} 

/* Depth First Search */

void DFS(int G[][MAX], int n, int v, int chuaxet[]){ 

 cout<<"Duyet dinh : "<<v<<endl;

 int u; 

 chuaxet[v]=FALSE; 

 for(u=1; u<=n; u++){ 

  if(G[v][u]==1 && chuaxet[u]) 

   DFS(G,n, u, chuaxet); 

 } 

} 

void main(void){ 

 Init(); 

 for(int i=1; i<=n; i++) 

  chuaxet[i]=TRUE; 

 for(int i=1; i<=n;i++) 

  if(chuaxet[i]) 

   DFS( G,n, i, chuaxet); 

 _getch(); 

}

Tham khảo

Source code tham khảo


Chương trình học


  1. Lý thuyết đồ thị 31
    1. Các khái niệm cơ bản về Lý thuyết Đồ thị #11087
    2. Biểu diễn đồ thị trên máy tính bằng Ma trận kề #11112
    3. Biểu diễn đồ thị trên máy tính bằng Danh sách cạnh #11117
    4. Biểu diễn đồ thị trên máy tính bằng Danh sách kề #11116
    5. Lab 1 - Chuyển Danh sách cạnh sang Ma trận kề #11138
    6. Lab 1.2 - Chuyển Danh sách cạnh sang Danh sách kề #11144
    7. Lab 1.3 - Chuyển Ma trận kề sang Danh sách cạnh #11151
    8. Lab 1.4 - Chuyển Ma trận kề sang Danh sách kề #11154
    9. Lab 1.5 - Chuyển Danh sách kề sang Ma trận kề #11158
    10. Lab 1.6 - Chuyển Danh sách kề sang Danh sách cạnh #11161
    11. Duyệt cây theo chiều sâu DFS (Depth First Search) #10963
    12. Duyệt cây theo chiều rộng BFS (Breadth First Search) #11081
    13. Thuật toán Tìm đường đi giữa 2 đỉnh của Đồ thị bằng C/C++ #11079
    14. Lab 2 - Duyệt cây theo chiều sâu DFS (Depth First Search) #11167
    15. Lab 2.2 - Tìm đường đi bằng cách duyệt cây theo chiều sâu DFS (Depth First Search) #11168
    16. Lab 3 - Duyệt cây theo chiều rộng BFS (Breadth First Search) #11169
    17. Lab 3.2 - Tìm đường đi bằng cách duyệt cây theo chiều rộng BFS (Breadth First Search) #11170
    18. Lab 4 - Tìm các thành phần liên thông trên đồ thị vô hướng #11179
    19. Tìm đường đi ngắn nhất bằng Thuật toán Dijkstra #11403
    20. Lab 5 - Tìm đường đi ngắn nhất từ đỉnh S đến tất cả các đỉnh còn lại trên đồ thị (sử dụng thuật toán Dijkstra) #11418
    21. Lab 5.1 - Tìm đường đi ngắn nhất từ đỉnh S đến đỉnh T trên đồ thị (sử dụng thuật toán Dijkstra) #11423
    22. Thuật toán Kruskal – Tìm cây khung (bao trùm) nhỏ nhất #11485
    23. Lab 6 - Tìm cây khung (bao trùm) cực tiểu nhỏ nhất (sử dụng thuật toán Kruskal) #11486
    24. Thuật toán Prim - Tìm cây khung (bao trùm) nhỏ nhất #11516
    25. Lab 6.1 - Tìm cây khung (bao trùm) cực tiểu nhỏ nhất (sử dụng thuật toán PRIM) #11515
    26. Chu trình và đường đi Euler #11519
    27. Lab 7 - Tìm chu trình Euler #11520
    28. Lab 7.1 - Tìm đường đi Euler #11528
    29. Bài toán Luồng cực đại #11532
    30. Lab 8 - Tìm luồng cực đại - sử dụng thuật toán Ford - Fulkerson #11533
    31. Lab 8.1 - Tìm luồng cực đại - sử dụng thuật toán Edmonds - Karp (Shortest path) #11534
  2. Tài liệu tham khảo 2
    1. Kho sách, nguồn tài liệu tham khảo Lập trình C++ - Cấu trúc dữ liệu và Giải thuật #11100
    2. Bài tập Lý thuyết Đồ thị có lời giải #11547
  3. Quy hoạch động 1
    1. Lý thuyết các bài toán sử dụng Quy hoạch động #11567
Các bài học

Chương trình học

Bao gồm Module, Chương, Bài học, Bài tập, Kiểm tra...

Chương trình học


  1. Lý thuyết đồ thị 31
    1. Các khái niệm cơ bản về Lý thuyết Đồ thị #11087
    2. Biểu diễn đồ thị trên máy tính bằng Ma trận kề #11112
    3. Biểu diễn đồ thị trên máy tính bằng Danh sách cạnh #11117
    4. Biểu diễn đồ thị trên máy tính bằng Danh sách kề #11116
    5. Lab 1 - Chuyển Danh sách cạnh sang Ma trận kề #11138
    6. Lab 1.2 - Chuyển Danh sách cạnh sang Danh sách kề #11144
    7. Lab 1.3 - Chuyển Ma trận kề sang Danh sách cạnh #11151
    8. Lab 1.4 - Chuyển Ma trận kề sang Danh sách kề #11154
    9. Lab 1.5 - Chuyển Danh sách kề sang Ma trận kề #11158
    10. Lab 1.6 - Chuyển Danh sách kề sang Danh sách cạnh #11161
    11. Duyệt cây theo chiều sâu DFS (Depth First Search) #10963
    12. Duyệt cây theo chiều rộng BFS (Breadth First Search) #11081
    13. Thuật toán Tìm đường đi giữa 2 đỉnh của Đồ thị bằng C/C++ #11079
    14. Lab 2 - Duyệt cây theo chiều sâu DFS (Depth First Search) #11167
    15. Lab 2.2 - Tìm đường đi bằng cách duyệt cây theo chiều sâu DFS (Depth First Search) #11168
    16. Lab 3 - Duyệt cây theo chiều rộng BFS (Breadth First Search) #11169
    17. Lab 3.2 - Tìm đường đi bằng cách duyệt cây theo chiều rộng BFS (Breadth First Search) #11170
    18. Lab 4 - Tìm các thành phần liên thông trên đồ thị vô hướng #11179
    19. Tìm đường đi ngắn nhất bằng Thuật toán Dijkstra #11403
    20. Lab 5 - Tìm đường đi ngắn nhất từ đỉnh S đến tất cả các đỉnh còn lại trên đồ thị (sử dụng thuật toán Dijkstra) #11418
    21. Lab 5.1 - Tìm đường đi ngắn nhất từ đỉnh S đến đỉnh T trên đồ thị (sử dụng thuật toán Dijkstra) #11423
    22. Thuật toán Kruskal – Tìm cây khung (bao trùm) nhỏ nhất #11485
    23. Lab 6 - Tìm cây khung (bao trùm) cực tiểu nhỏ nhất (sử dụng thuật toán Kruskal) #11486
    24. Thuật toán Prim - Tìm cây khung (bao trùm) nhỏ nhất #11516
    25. Lab 6.1 - Tìm cây khung (bao trùm) cực tiểu nhỏ nhất (sử dụng thuật toán PRIM) #11515
    26. Chu trình và đường đi Euler #11519
    27. Lab 7 - Tìm chu trình Euler #11520
    28. Lab 7.1 - Tìm đường đi Euler #11528
    29. Bài toán Luồng cực đại #11532
    30. Lab 8 - Tìm luồng cực đại - sử dụng thuật toán Ford - Fulkerson #11533
    31. Lab 8.1 - Tìm luồng cực đại - sử dụng thuật toán Edmonds - Karp (Shortest path) #11534
  2. Tài liệu tham khảo 2
    1. Kho sách, nguồn tài liệu tham khảo Lập trình C++ - Cấu trúc dữ liệu và Giải thuật #11100
    2. Bài tập Lý thuyết Đồ thị có lời giải #11547
  3. Quy hoạch động 1
    1. Lý thuyết các bài toán sử dụng Quy hoạch động #11567

Bài học trước Bài học tiếp theo