Trong nội dung bài viết này, ta vẫn tò mò về thuật toán BFS, là một trong những thuật toán thù search tìm theo hướng rộng lớn bên trên đồ vật thị cùng các hình ảnh minc họa. Ngoài ra, ta đang thực thi thuật toán BFS bằng ngôn từ thiết kế C.

Bạn đang xem: Code thuật toán tìm kiếm theo chiều rộng

Breadth First Traversal hoặc Breadth First Search là một trong những thuật tân oán đệ quy nhằm tìm kiếm kiếm tất cả những đỉnh của thứ thị hoặc cấu tạo dữ liệu dạng cây. Traversal có nghĩa là chăm bẵm qua các phần tử hay truy vấn toàn bộ các nút của biểu thứ.

1. Khái niệm

Việc triển khai BFS tiêu chuẩn chỉnh đã tiến hành chia từng đỉnh của biểu vật thành 1 trong nhì loại:

Đã được duyệt y.Không được chuẩn y.

Mục đích của thuật tân oán là đánh dấu mỗi đỉnh là vẫn để mắt tới trong những lúc tránh thực hiện quy trình để mắt theo vòng tròn.

Cách thuật toán hoạt động nlỗi sau:

Bắt đầu bằng phương pháp đặt ngẫu nhiên một trong những đỉnh của biểu đồ vật làm việc phía cuối của mặt hàng đợi.Lấy thành phần đầu tiên của sản phẩm ngóng và thêm nó vào list vẫn truy vấn.Tạo danh sách những nút tiếp giáp của đỉnh đó. Thêm rất nhiều nút ít nhưng mà không tồn tại trong danh sách đang truy cập vào vùng sau mặt hàng hóng.Tiếp tục tái diễn bước 2 với 3 cho tới Khi sản phẩm đợi trống trống rỗng.

Biểu đồ dùng có thể có hai phần bị ngắt liên kết khác biệt, vì chưng vậy nhằm đảm bảo rằng chúng ta vẫn để ý qua phần nhiều đỉnh, chúng ta cũng hoàn toàn có thể áp dụng thuật toán BFS bên trên số đông nút ít.

2. lấy ví dụ như về thuật toán thù BFS

Ta đang cùng coi phương pháp hoạt động vui chơi của thuật tân oán tìm kiếm theo hướng rộng lớn với một ví dụ. Chúng ta vẫn thực hiện một vật dụng thị vô hướng với 5 đỉnh.

*

Chúng ta sẽ bắt đầu tự đỉnh 0, thuật toán thù BFS ban đầu bằng phương pháp đưa nó vào list sẽ ưng chuẩn cùng gửi toàn bộ các đỉnh cạnh bên của nó vào ngăn xếp.

*

Tiếp theo, bọn họ vẫn truy cập phần tử tại vị trí đầu của sản phẩm hóng, Tức là 1 với đi mang lại những nút gần kề của nó. Vì 0 đã làm được truy vấn, chúng ta sẽ truy vấn 2.

*

Đỉnh 2 gồm một đỉnh tiếp giáp không được chăm chút sinh sống nút có giá trị là 4, vì vậy chúng ta sẽ thêm đỉnh kia vào phía đằng sau của hàng ngóng với thông qua qua nút ít có giá trị là 3, ở phía đầu của hàng đợi.

*

*

Chỉ còn sót lại 4 vào hàng hóng bởi vì nút ít gần cạnh nhất của 3 có nghĩa là 0 đã có được truy cập. Truy ctràn vào bộ phận sau cuối còn sót lại trong ngăn uống xếp nhằm soát sổ xem nó bao gồm nút ít giáp mà lại chưa được chú tâm hay không

*

Vì mặt hàng hóng trống rỗng, bọn họ đã xong thuật toán chuẩn y theo chiều rộng của biểu thiết bị (BFS).

Đoạn mang mã đến thuật toán BFS nlỗi sau:

Tạo một hàng hóng QĐánh vết v là đang chuyên chú với đặt v vào QTrong lúc Q không rỗng Loại cho chỗ đầu u của Q Đánh vết cùng cấp dưỡng toàn bộ những nút tiếp giáp của u mà lại không được duyệtVí dụ: Triển knhì thuật toán BFS bởi ngôn từ lập trình sẵn C.

Xem thêm: Lời Bài Hát Mùa Xuân Lá Khô (Trần Thiện Thanh), Mùa Xuân Lá Khô

#include #include #define MAX 40struct queue int element; 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 BFSvoid bfs(struct Graph* graph, int start_vertex) struct queue* q = create_queue(); graph->traversed = 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 ", currentVertex); struct node* temp = graph->adjLists; while (temp) int adjVertex = temp->vertex; if (graph->traversed == 0) graph->traversed = 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 adjLists = NULL; graph->traversed = 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; graph->adjLists = new_node; new_node = create_node(src); new_node->next = graph->adjLists; graph->adjLists = 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(" Hàng hóng đầy."); else if (q->front == -1) q->front = 0; q->rear++; q->elementrear> = value; int remove_element_from_queue(struct queue* q) int item; if (isEmpty(q)) printf("Hàng đợi rỗng"); thành công = -1; else cửa nhà = q->elementfront>; q->front++; if (q->front > q->rear) printf("Đặt lại sản phẩm đợi"); q->front = q->rear = -1; return item;void print_queue(struct queue* q) int i = q->front; if (isEmpty(q)) printf("Hàng chờ rỗng"); else printf(" Các bộ phận vào hàng chờ là: "); for (i = q->front; i rear + 1; i++) printf("%d ", q->element); 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ả:

Các thành phần trong sản phẩm ngóng là: 1 Đặt lại hàng đợi1 đã được duyệtCác phần tử trong hàng đợi là: 3 2 3 đã có được duyệtCác bộ phận vào hàng hóng là: 2 5 2 đã có duyệtCác thành phần trong mặt hàng chờ là: 5 4 5 đã được duyệtCác bộ phận trong mặt hàng đợi là: 4 Đặt lại sản phẩm đợi4 đã làm được duyệt

3. Độ phức hợp của thuật toán

Độ tinh vi về thời gian của thuật toán thù BFS được biểu diễn bên dưới dạng O(V + E), trong các số đó V là số nút ít với E là số cạnh.Độ tinh vi không gian của thuật toán là O(V).

4. Ứng dụng của thuật toán

Để thi công chỉ số dựa trên chỉ số search kiếm.Để xác định GPS.Sử dụng trong những thuật toán search đường truyền.Sử dụng vào thuật tân oán Ford-Fulkerson để search luồng tối nhiều trong mạng.Phát hiện tại một vòng lặp chu kỳ luân hồi vào một biểu trang bị vô hướng.Được sử dụng vào cây form nhỏ dại tuyệt nhất.Trên đây là định nghĩa với ví dụ cơ bạn dạng về thuật toán thù tìm tìm theo chiều rộng bên trên thứ thị (BFS). Hy vọng đầy đủ fan rất có thể áp dụng vào trong lịch trình của mình. Nếu phần lớn người có góp sức gì thêm thì có thể nhằm những bình luận bên dưới nội dung bài viết này. Mọi fan hãy tiếp tục quan sát và theo dõi những bài tiếp theo sau cùng update những bài bác mới nhất trêndotacard.vnnhé!