Trong bài viết này, ta sẽ tìm hiểu về thuật toán BFS, là một thuật toán tìm kiếm theo chiều rộng trên đồ thị cùng các hình ảnh minh họa. Ngoài ra, ta sẽ triển khai thuật toán BFS bằng ngôn ngữ lập trình C.
Breadth First Traversal hoặc Breadth First Search là một thuật toán đệ quy để tìm kiếm tất cả các đỉnh của đồ thị hoặc cấu trúc dữ liệu dạng cây. Traversal có nghĩa là duyệt qua các phần tử hay truy cập tất cả các nút của biểu đồ.
Thuật toán BFS
Việc triển khai BFS tiêu chuẩn sẽ thực hiện chia mỗi đỉnh của biểu đồ thành một trong hai loại:
- Đã được duyệt.
- Không đượ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 thực hiện quá trình duyệt theo vòng tròn.
Cách thuật toán 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 đồ ở phía cuối của hàng đợi.
- Lấy phần tử đầu tiên của hàng đợi 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 đã truy cập vào phía sau hàng đợi.
- Tiếp tục lặp lại bước 2 và 3 cho đến khi hàng đợi trống rỗng.
Biểu đồ có thể có hai phần bị ngắt kết nối khác nhau, vì vậy để đảm bảo rằng chúng ta đã duyệt qua mọi đỉnh, chúng ta cũng có thể sử dụng thuật toán BFS trên mọi nút.
Ví dụ về thuật toán BFS
- Ta sẽ cùng xem cách hoạt động của thuật toán tìm kiếm theo chiều rộng với một ví dụ. 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 0, thuật toán BFS 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ử tại phần đầu của hàng đợi, tức là 1 và đi đến các nút liền kề của nó. Vì 0 đã được truy cập, chúng ta sẽ truy cập 2.
- Đỉnh 2 có một đỉnh liền kề chưa được duyệt ở nút có giá trị là 4, vì vậy chúng ta sẽ thêm đỉnh đó vào phía sau của hàng đợi và duyệt qua nút có giá trị là 3, ở phía đầu của hàng đợi.
- Chỉ còn lại 4 trong hàng đợi vì nút liền kề duy nhất của 3 tức là 0 đã được truy cập. Truy cập vào phần tử cuối cùng còn lại trong ngăn xếp để kiểm tra xem nó có nút liền kề mà chưa được duyệt hay không
- Vì hàng đợi trống rỗng, chúng ta đã hoàn thành thuật toán duyệt theo chiều rộng của biểu đồ (BFS).
Đoạn giả mã cho thuật toán BFS như sau:
|
1 2 3 4 5 |
Tạo một hàng đợi Q Đánh dấu v là đã duyệt và đặt v vào Q Trong khi Q không rỗng Loại bỏ phần đầu u của Q Đánh dấu và thêm vào tất cả các nút liền kề của u mà chưa được duyệt |
Ví dụ: Triển khai thuật toán BFS 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 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
#include <stdio.h> #include <stdlib.h> #define MAX 40 struct queue { int element[MAX]; int front; int rear; }; struct queue* create_queue(); void add_element_into_queue(struct queue* q, int); int remove_element_from_queue(struct queue* q); void print(struct queue* q); int isEmpty(struct queue* q); void print_queue(struct queue* q); struct node { int vertex; struct node* next; }; struct node* create_node(int); struct Graph { int numVertices; struct node** adjLists; int* traversed; }; // Giải thuật BFS void bfs(struct Graph* graph, int start_vertex) { struct queue* q = create_queue(); graph->traversed[start_vertex] = 1; add_element_into_queue(q, start_vertex); while (!isEmpty(q)) { print_queue(q); int currentVertex = remove_element_from_queue(q); printf("%d đã được duyệt\n", currentVertex); struct node* temp = graph->adjLists[currentVertex]; while (temp) { int adjVertex = temp->vertex; if (graph->traversed[adjVertex] == 0) { graph->traversed[adjVertex] = 1; add_element_into_queue(q, adjVertex); } temp = temp->next; } } } struct node* create_node(int v) { struct node* new_node = malloc(sizeof(struct node)); new_node->vertex = 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; } struct queue* create_queue() { struct queue* q = malloc(sizeof(struct queue)); q->front = -1; q->rear = -1; return q; } int isEmpty(struct queue* q) { if (q->rear == -1) return 1; else return 0; } void add_element_into_queue(struct queue* q, int value) { if (q->rear == MAX - 1) printf("\nHàng đợi đầy."); else { if (q->front == -1) q->front = 0; q->rear++; q->element[q->rear] = value; } } int remove_element_from_queue(struct queue* q) { int item; if (isEmpty(q)) { printf("Hàng đợi rỗng"); item = -1; } else { item = q->element[q->front]; q->front++; if (q->front > q->rear) { printf("Đặt lại hàng đợi"); q->front = q->rear = -1; } } return item; } void print_queue(struct queue* q) { int i = q->front; if (isEmpty(q)) { printf("Hàng đợi rỗng"); } else { printf("\nCác phần tử trong hàng đợi là: "); for (i = q->front; i < q->rear + 1; i++) { printf("%d ", q->element[i]); } } } int main() { struct Graph* graph = create_graph(6); add_edge(graph, 1, 2); add_edge(graph, 1, 3); add_edge(graph, 2, 3); add_edge(graph, 2, 5); add_edge(graph, 2, 4); add_edge(graph, 3, 5); add_edge(graph, 4, 5); bfs(graph, 1); return 0; } |
Kết quả:
|
1 2 3 4 5 |
Các phần tử trong hàng đợi là: 1 Đặt lại hàng đợi1 đã được duyệt Các phần tử trong hàng đợi là: 3 2 3 đã được duyệt Các phần tử trong hàng đợi là: 2 5 2 đã được duyệt Các phần tử trong hàng đợi là: 5 4 5 đã được duyệt Các phần tử trong hàng đợi là: 4 Đặt lại hàng đợi4 đã đượ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 BFS được biểu diễn dưới dạng O(V + E), trong đó V là số nút và E là số cạnh.
- Độ phức tạp không gian của thuật toán là O(V).
Ứng dụng của thuật toán
- Để xây dựng chỉ số dựa theo chỉ số tìm kiếm.
- Để định vị GPS.
- Sử dụng trong các thuật toán tìm đường dẫn.
- Sử dụng trong thuật toán Ford-Fulkerson để tìm luồng tối đa trong mạng.
- Phát hiện một vòng lặp chu kỳ trong một biểu đồ vô hướng.
- Được sử dụng trong cây khung nhỏ nhất.
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 rộng trên đồ thị (BFS). 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 Tarjan trong tìm thành phần liên thông mạnh | Bài tiếp theo: Thuật toán DFS – Tìm kiếm theo chiều sâu trên đồ thị |
