广度优先搜索代码如何写

广度优先搜索可以使用队列来实现。以下是一个基本的伪代码：

BFS(start_node, end_node):
    queue = [start_node]
    visited = set()
    while queue:
        node = queue.pop(0)
        if node == end_node:
            return "找到了"
        visited.add(node)
        for neighbor in node.neighbors:
            if neighbor not in visited:
                queue.append(neighbor)
    return "未找到"

其中，`start_node`是起点，`end_node`是终点，`queue`是队列，`visited`是已访问的节点集合。首先将起点加入队列，然后进入循环，每次从队列中取出一个节点进行处理。如果该节点为终点，则搜索成功。否则，将该节点加入已访问集合，然后遍历该节点的所有邻居节点，如果邻居节点未被访问过，则将其加入队列中。如果队列为空，则搜索失败。

相关问题

c++广度优先搜索代码如何写

以下是一个简单的C++广度优先搜索代码示例：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int N = 100010;

int n, m;
vector<int> g[N];
bool st[N];

void bfs(int u) {
    queue<int> q;
    q.push(u);
    st[u] = true;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        cout << t << " "; // 输出遍历的节点
        for (int i = 0; i < g[t].size(); i++) {
            int v = g[t][i];
            if (!st[v]) {
                q.push(v);
                st[v] = true;
            }
        }
    }
}

int main() {
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        if (!st[i]) {
            bfs(i);
        }
    }
    return 0;
}

上述代码中，`g[]`数组存储了无向图的邻接表，`st[]`数组记录了每个节点是否被遍历过。`bfs()`函数实现了广度优先搜索，从起点 `u` 出发，将其加入队列中，然后不断从队列中取出节点进行遍历。对于每个遍历到的节点，将它的未访问过的邻居加入队列中。最后，对于所有未被访问过的节点，逐一进行广度优先搜索遍历。

c++广度优先搜索代码

C++中的广度优先搜索（BFS）是一种用于图形遍历的算法。它从给定的起始节点开始，逐层遍历图形中的节点，直到找到目标节点或遍历完整个图形。下面是一个简单的C++代码示例来实现广度优先搜索：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 图形的节点结构
struct Node {
    int value;
    vector<Node*> neighbors;
};

// 广度优先搜索函数
void BFS(Node* startNode, int targetValue) {
    queue<Node*> q;
    vector<Node*> visited;

    q.push(startNode);
    visited.push_back(startNode);

    while (!q.empty()) {
        Node* currentNode = q.front();
        q.pop();

        if (currentNode->value == targetValue) {
            cout << "目标节点已找到！" << endl;
            return;
        }

        for (Node* neighbor : currentNode->neighbors) {
            if (find(visited.begin(), visited.end(), neighbor) == visited.end()) {
                q.push(neighbor);
                visited.push_back(neighbor);
            }
        }
    }

    cout << "未找到目标节点！" << endl;
}

int main() {
    // 创建图形节点
    Node* node1 = new Node{1};
    Node* node2 = new Node{2};
    Node* node3 = new Node{3};
    Node* node4 = new Node{4};
    Node* node5 = new Node{5};

    // 构建图形关系
    node1->neighbors.push_back(node2);
    node1->neighbors.push_back(node3);
    node2->neighbors.push_back(node4);
    node3->neighbors.push_back(node4);
    node4->neighbors.push_back(node5);

    // 在图形中进行广度优先搜索
    BFS(node1, 5);

    return 0;
}

这段代码首先定义了一个节点结构 `Node`，其中包含一个值和一个邻居节点的向量。然后，定义了一个 `BFS` 函数来执行广度优先搜索。在 `BFS` 函数中，使用队列来存储待访问的节点，并使用一个 `visited` 向量来记录已访问过的节点。然后，从起始节点开始，逐层遍历图形中的节点，直到找到目标节点或遍历完整个图形。

在 `main` 函数中，创建了一些节点，并构建了它们之间的关系。然后，调用 `BFS` 函数来执行广度优先搜索，并传入起始节点和目标值。