使用C 中的廣度優先搜尋演算法
廣度優先搜尋演算法(BFS)是一種圖搜尋演算法,它從圖的起點開始,依序存取和探索各個節點,直到找到目標節點或遍歷完整個圖。 BFS使用佇列來實現,首先將起點節點入隊,然後將其相鄰節點入隊,依序進行下去,直到佇列為空。
以下是使用C 實作廣度優先搜尋演算法的範例程式碼:
#include <iostream> #include <queue> #include <vector> using namespace std; // 图的节点 struct Node { int id; bool visited; vector<Node*> neighbors; Node(int _id) : id(_id), visited(false) {} }; // 广度优先搜索算法 void BFS(Node* start) { // 使用队列保存要访问的节点 queue<Node*> q; // 标记起点已经被访问 start->visited = true; q.push(start); while (!q.empty()) { Node* current = q.front(); q.pop(); cout << current->id << " "; // 遍历当前节点的相邻节点 for (Node* neighbor : current->neighbors) { // 如果相邻节点未被访问,则标记为已访问并入队 if (!neighbor->visited) { neighbor->visited = true; q.push(neighbor); } } } } int main() { // 创建图的节点 Node* A = new Node(1); Node* B = new Node(2); Node* C = new Node(3); Node* D = new Node(4); Node* E = new Node(5); // 构建节点之间的连接关系 A->neighbors.push_back(B); A->neighbors.push_back(C); B->neighbors.push_back(A); B->neighbors.push_back(D); C->neighbors.push_back(A); C->neighbors.push_back(D); D->neighbors.push_back(B); D->neighbors.push_back(C); D->neighbors.push_back(E); E->neighbors.push_back(D); // 从节点A开始进行广度优先搜索 cout << "BFS traversal starting from node A: "; BFS(A); return 0; }
以上程式碼中,我們首先定義了一個圖的節點結構Node
,其中包含節點的ID、是否曾造訪過和相鄰節點的指標清單。然後,我們實作了廣度優先搜尋演算法BFS###,使用佇列來保存要存取的節點。在每次循環中,我們取出佇列的首個節點,將其ID輸出,並遍歷其相鄰節點,將未被訪問過的節點加入佇列。最後,在
main函數中建立了一個簡單的圖,並從節點A開始進行廣度優先搜尋。
以上是如何使用C++中的廣度優先搜尋演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!