广度优先搜索

发布时间:2024年01月06日

广度优先搜索(BFS)是一种图遍历算法,

用于在给定的图中寻找从起始节点到目标节点的最短路径。

在C++语言中实现BFS算法可以采用队列数据结构。

下面是一个关于C++广度优先搜索的示例代码:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<vector<int>> graph; // 图的邻接矩阵
vector<bool> visited; // 记录节点是否被访问过

void bfs(int start) {
    queue<int> q;
    q.push(start); // 将起始节点加入队列
    visited[start] = true; // 标记起始节点已访问

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        // 遍历当前节点的邻居节点
        for (int neighbor = 0; neighbor < graph[node].size(); neighbor++) {
            if (graph[node][neighbor] == 1 && !visited[neighbor]) {
                q.push(neighbor); // 将邻居节点加入队列
                visited[neighbor] = true; // 标记邻居节点已访问
            }
        }

        // 输出当前节点
        cout << node << " ";
    }
}

int main() {
    int numNodes, numEdges;
    cout << "Enter the number of nodes and edges: ";
    cin >> numNodes >> numEdges;

    // 初始化图的邻接矩阵和访问数组
    graph.resize(numNodes, vector<int>(numNodes, 0));
    visited.resize(numNodes, false);

    cout << "Enter the edges: " << endl;
    for (int i = 0; i < numEdges; i++) {
        int from, to;
        cin >> from >> to;

        // 添加边到邻接矩阵
        graph[from][to] = 1;
        graph[to][from] = 1;
    }

    int startNode;
    cout << "Enter the start node: ";
    cin >> startNode;

    cout << "BFS traversal: ";
    bfs(startNode);

    return 0;
}

以上代码实现了一个简单的广度优先搜索算法,

在控制台中读取图的节点和边,

然后输入起始节点,

最后输出广度优先搜索的结果。

该代码使用邻接矩阵来表示图,

使用队列来实现广度优先搜索算法。

文章来源:https://blog.csdn.net/C___b___b___/article/details/135424125
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。