Trong bài viết này, ta sẽ cùng tìm hiểu về thuật toán tìm kiếm theo chiều sâu trên đồ thị, thuật toán DFS, cùng với các hình ảnh ví dụ minh họa. Ngoài ra, ta sẽ triển khai thuật toán DFS bằng ngôn ngữ lập trình C.
Tìm kiếm theo chiều sâu trên đồ thị là một thuật toán đệ quy để tìm kiếm tất cả các đỉnh của một đồ thị hoặc cấu trúc dữ liệu cây.
Thuật toán DFS
Việc triển khai DFS tiêu chuẩn chia mỗi đỉnh của biểu đồ thành một trong hai loại:
- Đã được duyệt.
- Chưa được duyệt.
Mục đích của thuật toán là đánh dấu mỗi đỉnh là đã duyệt trong khi tránh việc duyệt theo vòng tròn chu kỳ.
Thuật toán DFS hoạt động như sau:
- Bắt đầu bằng cách đặt bất kỳ một trong các đỉnh của biểu đồ lên trên một ngăn xếp.
- Lấy ra phần tử trên cùng của ngăn xếp và thêm nó vào danh sách đã truy cập.
- Tạo danh sách các nút liền kề của đỉnh đó. Thêm những nút mà không có trong danh sách đã được duyệt vào đầu ngăn xếp.
- Tiếp tục lặp lại các bước 2 và 3 cho đến khi ngăn xếp trống rỗng.
Ví dụ về tìm kiếm theo chiều sâu trên đồ thị
- Ta sẽ cùng xem cách hoạt động của thuật toán tìm kiếm theo chiều sâu trên đồ thị cùng với một ví dụ như sau. Chúng ta sẽ sử dụng một đồ thị vô hướng với 5 đỉnh.
- Chúng ta sẽ bắt đầu từ đỉnh 2, thuật toán DFS bắt đầu bằng cách đưa nó vào danh sách đã duyệt và đưa tất cả các đỉnh liền kề của nó vào ngăn xếp.
- Tiếp theo, chúng ta sẽ truy cập phần tử ở trên cùng của ngăn xếp, tức là 3 và đi đến các nút liền kề của nó. Vì 2 đã được truy cập, chúng ta sẽ truy cập nút có giá trị là 4.
- Đỉnh 4 có một đỉnh liền kề mà chưa được duyệt là 6, vì vậy chúng ta sẽ thêm đỉnh đó vào đầu ngăn xếp và duyệt nó.
- Sau khi chúng ta truy cập vào phần tử 5 cuối cùng, nó không có bất kỳ nút liền kề nào chưa được truy cập, vì vậy chúng ta đã hoàn thành quá trình duyệt theo chiều sâu của đồ thị.
Đoạn giả mã của thuật toán DFS bao gồm như sau:
Trong hàm init(), lưu ý rằng chúng ta sẽ thực thi hàm DFS trên mọi nút. Điều này là do biểu đồ có thể có hai phần không kết nối khác nhau, vì vậy để đảm bảo rằng chúng ta bao phủ mọi đỉnh, chúng ta cũng có thể chạy thuật toán DFS trên mọi nút.
1 2 3 4 5 6 7 8 9 10 11 |
DFS(G, u) Gán u.visited = true Dùng vòng lặp for với v ∈ G.Adj[u] Nếu v.visited == false DFS(G,v) Hàm init(){ Dùng vòng lặp for cho mỗi giá trị u ∈ G u.visited = false Dùng vòng lặp for cho mỗi giá trị u ∈ G DFS(G, u) } |
Ví dụ: Triển khai thuật toán DFS bằng ngôn ngữ lập trình C.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <stdio.h> #include <stdlib.h> struct node { int data; struct node* next; }; struct node* create_node(int v); struct Graph { int numVertices; int* traversed; struct node** adjLists; }; void DFS(struct Graph* graph, int data) { struct node* adjList = graph->adjLists[data]; struct node* temp = adjList; graph->traversed[data] = 1; printf("%d đã được duyệt \n", data); while (temp != NULL) { int connecteddata = temp->data; if (graph->traversed[connecteddata] == 0) { DFS(graph, connecteddata); } temp = temp->next; } } struct node* create_node(int v) { struct node* new_node = malloc(sizeof(struct node)); new_node->data = v; new_node->next = NULL; return new_node; } struct Graph* create_graph(int vertices) { struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->traversed = malloc(vertices * sizeof(int)); int i; for (i = 0; i < vertices; i++) { graph->adjLists[i] = NULL; graph->traversed[i] = 0; } return graph; } void add_edge(struct Graph* graph, int src, int dest) { struct node* new_node = create_node(dest); new_node->next = graph->adjLists[src]; graph->adjLists[src] = new_node; new_node = create_node(src); new_node->next = graph->adjLists[dest]; graph->adjLists[dest] = new_node; } void print(struct Graph* graph) { int v; for (v = 0; v < graph->numVertices; v++) { struct node* temp = graph->adjLists[v]; printf("\nDanh sách liền kề của đỉnh %d\n ", v); while (temp) { printf("%d ", temp->data); temp = temp->next; } printf("\n"); } } int main() { struct Graph* graph = create_graph(6); add_edge(graph, 2, 3); add_edge(graph, 2, 4); add_edge(graph, 3, 4); add_edge(graph, 4, 5); print(graph); DFS(graph, 4); return 0; } |
Kết quả:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Danh sách liền kề của đỉnh 0 Danh sách liền kề của đỉnh 1 Danh sách liền kề của đỉnh 2 4 3 Danh sách liền kề của đỉnh 3 4 2 Danh sách liền kề của đỉnh 4 5 3 2 Danh sách liền kề của đỉnh 5 4 4 đã được duyệt 5 đã được duyệt 3 đã được duyệt 2 đã được duyệt |
Độ phức tạp của thuật toán
- Độ phức tạp về thời gian của thuật toán DFS được biểu diễn dưới dạng
, trong đó V là số nút và E là số cạnh.
- Độ phức tạp về không gian của thuật toán là
.
Ứng dụng của thuật toán
- Để tìm đường đi.
- Để kiểm tra xem biểu đồ có phải là đồ thị hai phía hay không.
- Để tìm các thành phần được kết nối chặt chẽ hay liên thông mạnh của một biểu đồ.
- Để phát hiện các vòng lặp chu kỳ trong một đồ thị.
Trên đây là khái niệm và ví dụ cơ bản về thuật toán tìm kiếm theo chiều sâu của đồ thị (DFS). Hy vọng mọi người có thể áp dụng vào trong chương trình của mình. Nếu mọi người có đóng góp gì thêm thì có thể để các bình luận bên dưới bài viết này. Mọi người hãy tiếp tục theo dõi các bài tiếp theo và cập nhật các bài mới nhất trên tek4 nhé!
P/s: Cảm ơn mọi người!
Bài trước: Thuật toán BFS – Tìm kiếm theo chiều rộng trên đồ thị | Bài tiếp theo: Biểu diễn đồ thị bằng ma trận kề và danh sách kề |