Thuật toán đồ thị BFS (Với mã bằng C, C ++, Java và Python)

Mục lục

Thuật toán BFS
Ví dụ về BFS
Mã giả BFS
Ví dụ về Python, Java và C / C ++
Độ phức tạp của thuật toán BFS
Ứng dụng thuật toán BFS

Trong hướng dẫn này, bạn sẽ tìm hiểu về thuật toán tìm kiếm đầu tiên theo chiều rộng. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của thuật toán bfs trong C, C ++, Java và Python.

Traversal có nghĩa là truy cập tất cả các nút của biểu đồ. 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.

Thuật toán BFS

Triển khai BFS tiêu chuẩn đặt mỗi đỉnh của biểu đồ thành một trong hai loại:

Đã đến thăm
Không được thăm

Mục đích của thuật toán là đánh dấu mỗi đỉnh là đã thăm trong khi tránh các chu kỳ.

Các 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 sau hàng đợi.
Lấy mục đầ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 người 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.

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 tôi bao phủ mọi đỉnh, chúng tôi cũng có thể chạy thuật toán BFS trên mọi nút

Ví dụ về BFS

Hãy xem cách hoạt động của thuật toán Tìm kiếm đầu tiên theo chiều rộng với một ví dụ. Chúng tôi sử dụng một đồ thị vô hướng với 5 đỉnh.

Đồ thị vô hướng với 5 đỉnh

Chúng ta 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 Đã thăm và đưa tất cả các đỉnh liền kề của nó vào ngăn xếp.

Truy cập đỉnh bắt đầu và thêm các đỉnh liền kề của nó vào hàng đợi

Tiếp theo, chúng ta truy cập phần tử ở phía trước 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 tôi truy cập 2 thay thế.

Truy cập hàng xóm đầu tiên của nút bắt đầu 0, là 1

Đỉnh 2 có một đỉnh liền kề không được chờ đợi ở 4, vì vậy chúng tôi thêm đỉnh đó vào phía sau của hàng đợi và thăm 3, ở phía trước của hàng đợi.

Lượt truy cập 2 đã được thêm vào hàng đợi trước đó để thêm hàng xóm

4 vẫn còn trong 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. Chúng tôi đến thăm nó.

Truy cập mục cuối cùng còn lại trong ngăn xếp để kiểm tra xem nó có những người hàng xóm không được mời không

Vì hàng đợi trống, chúng tôi đã hoàn thành Duyệt đầu tiên theo chiều rộng của biểu đồ.

Mã giả BFS

 tạo một hàng đợi Q đánh dấu v như đã thăm và đặt v vào Q trong khi Q không trống, loại bỏ phần đầu u của dấu Q và xếp hàng tất cả các hàng xóm (không được mời) của u

Ví dụ về Python, Java và C / C ++

Mã cho Thuật toán tìm kiếm đầu tiên theo chiều rộng với một ví dụ được hiển thị bên dưới. Mã đã được đơn giản hóa để chúng ta có thể tập trung vào thuật toán hơn là các chi tiết khác.

Python Java C C +

 # BFS algorithm in Python import collections # BFS algorithm def bfs(graph, root): visited, queue = set(), collections.deque((root)) visited.add(root) while queue: # Dequeue a vertex from queue vertex = queue.popleft() print(str(vertex) + " ", end="") # If not visited, mark it as visited, and # enqueue it for neighbour in graph(vertex): if neighbour not in visited: visited.add(neighbour) queue.append(neighbour) if __name__ == '__main__': graph = (0: (1, 2), 1: (2), 2: (3), 3: (1, 2)) print("Following is Breadth First Traversal: ") bfs(graph, 0)

 // BFS algorithm in Java import java.util.*; public class Graph ( private int V; private LinkedList adj(); // Create a graph Graph(int v) ( V = v; adj = new LinkedList(v); for (int i = 0; i < v; ++i) adj(i) = new LinkedList(); ) // Add edges to the graph void addEdge(int v, int w) ( adj(v).add(w); ) // BFS algorithm void BFS(int s) ( boolean visited() = new boolean(V); LinkedList queue = new LinkedList(); visited(s) = true; queue.add(s); while (queue.size() != 0) ( s = queue.poll(); System.out.print(s + " "); Iterator i = adj(s).listIterator(); while (i.hasNext()) ( int n = i.next(); if (!visited(n)) ( visited(n) = true; queue.add(n); ) ) ) ) public static void main(String args()) ( Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)"); g.BFS(2); ) )

 // BFS algorithm in C #include #include #define SIZE 40 struct queue ( int items(SIZE); int front; int rear; ); struct queue* createQueue(); void enqueue(struct queue* q, int); int dequeue(struct queue* q); void display(struct queue* q); int isEmpty(struct queue* q); void printQueue(struct queue* q); struct node ( int vertex; struct node* next; ); struct node* createNode(int); struct Graph ( int numVertices; struct node** adjLists; int* visited; ); // BFS algorithm void bfs(struct Graph* graph, int startVertex) ( struct queue* q = createQueue(); graph->visited(startVertex) = 1; enqueue(q, startVertex); while (!isEmpty(q)) ( printQueue(q); int currentVertex = dequeue(q); printf("Visited %d", currentVertex); struct node* temp = graph->adjLists(currentVertex); while (temp) ( int adjVertex = temp->vertex; if (graph->visited(adjVertex) == 0) ( graph->visited(adjVertex) = 1; enqueue(q, adjVertex); ) temp = temp->next; ) ) ) // Creating a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Creating a graph struct Graph* createGraph(int vertices) ( struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; i adjLists(i) = NULL; graph->visited(i) = 0; ) return graph; ) // Add edge void addEdge(struct Graph* graph, int src, int dest) ( // Add edge from src to dest struct node* newNode = createNode(dest); newNode->next = graph->adjLists(src); graph->adjLists(src) = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjLists(dest); graph->adjLists(dest) = newNode; ) // Create a queue struct queue* createQueue() ( struct queue* q = malloc(sizeof(struct queue)); q->front = -1; q->rear = -1; return q; ) // Check if the queue is empty int isEmpty(struct queue* q) ( if (q->rear == -1) return 1; else return 0; ) // Adding elements into queue void enqueue(struct queue* q, int value) ( if (q->rear == SIZE - 1) printf("Queue is Full!!"); else ( if (q->front == -1) q->front = 0; q->rear++; q->items(q->rear) = value; ) ) // Removing elements from queue int dequeue(struct queue* q) ( int item; if (isEmpty(q)) ( printf("Queue is empty"); item = -1; ) else ( item = q->items(q->front); q->front++; if (q->front> q->rear) ( printf("Resetting queue "); q->front = q->rear = -1; ) ) return item; ) // Print the queue void printQueue(struct queue* q) ( int i = q->front; if (isEmpty(q)) ( printf("Queue is empty"); ) else ( printf("Queue contains "); for (i = q->front; i rear + 1; i++) ( printf("%d ", q->items(i)); ) ) ) int main() ( struct Graph* graph = createGraph(6); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 1, 4); addEdge(graph, 1, 3); addEdge(graph, 2, 4); addEdge(graph, 3, 4); bfs(graph, 0); return 0; )

 // BFS algorithm in C++ #include #include using namespace std; class Graph ( int numVertices; list* adjLists; bool* visited; public: Graph(int vertices); void addEdge(int src, int dest); void BFS(int startVertex); ); // Create a graph with given vertices, // and maintain an adjacency list Graph::Graph(int vertices) ( numVertices = vertices; adjLists = new list(vertices); ) // Add edges to the graph void Graph::addEdge(int src, int dest) ( adjLists(src).push_back(dest); adjLists(dest).push_back(src); ) // BFS algorithm void Graph::BFS(int startVertex) ( visited = new bool(numVertices); for (int i = 0; i < numVertices; i++) visited(i) = false; list queue; visited(startVertex) = true; queue.push_back(startVertex); list::iterator i; while (!queue.empty()) ( int currVertex = queue.front(); cout << "Visited " << currVertex << " "; queue.pop_front(); for (i = adjLists(currVertex).begin(); i != adjLists(currVertex).end(); ++i) ( int adjVertex = *i; if (!visited(adjVertex)) ( visited(adjVertex) = true; queue.push_back(adjVertex); ) ) ) ) int main() ( Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); g.BFS(2); return 0; )