图上的广度优先遍历-邻接矩阵存图

广度优先遍历是一种用于图的遍历的算法。在邻接矩阵存储图中，广度优先遍历通过逐层访问图中的顶点，先访问与起始顶点直接相邻的顶点，然后再访问与这些顶点直接相邻的顶点，以此类推，直到遍历完所有可达的顶点。具体实现广度优先遍历的算法如下：

1. 创建一个大小为顶点数的布尔类型的数组visited，用于标记顶点是否已被访问。
2. 创建一个队列queue，用于存储待访问的顶点。
3. 将起始顶点i标记为已访问，并将其入队。
4. 当队列不为空时，执行以下步骤：
- 出队一个顶点v，并输出该顶点。
- 遍历与顶点v直接相邻的顶点w，若顶点w未被访问，则将其标记为已访问，并将其入队。
5. 重复步骤4直到队列为空。

以上就是邻接矩阵存图上的广度优先遍历算法的具体步骤。

相关问题

图遍历-邻接矩阵存储

图遍历是一种在图中访问所有顶点的过程，通常有深度优先搜索（DFS）和广度优先搜索（BFS）两种方法。邻接矩阵是图的一种常见数据结构，用于表示图中任意两个顶点之间是否存在边。在这个矩阵中，行代表起点，列表代表终点，每个元素的值通常是0（无边）或1（有边）。

具体到邻接矩阵存储，图的邻接矩阵是一个二维数组，其中：
- 对角线元素通常为0，因为不存在一个顶点与自身直接相连；
- 非对角线元素如果为1，则表示对应顶点之间存在一条边；
- 如果元素为0，则表示没有连接。

图遍历使用邻接矩阵时的操作如下：
1. **深度优先搜索 (DFS)**:
- 从给定起点开始，检查其相邻节点，标记并进入未访问节点。
- 对于每个相邻节点，递归地执行DFS直到遍历完整张矩阵。
- **广度优先搜索 (BFS)**:
- 用队列实现，先将起点放入队列，然后逐个取出节点，将其相邻节点（矩阵中的非对角线）加入队列，直到队列为空。

广度优先遍历（邻接矩阵BFS）c++实现

以下是邻接矩阵BFS的C++实现：

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

const int MAXN = 100; // 最大顶点数
int G[MAXN][MAXN]; // 邻接矩阵
bool vis[MAXN]; // 标记数组

void BFS(int s, int n) { // s为起点，n为顶点数
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";
        for (int v = 0; v < n; v++) {
            if (G[u][v] && !vis[v]) {
                q.push(v);
                vis[v] = true;
            }
        }
    }
}

int main() {
    int n, m; // n为顶点数，m为边数
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u][v] = G[v][u] = 1; // 无向图
    }
    BFS(0, n);
    return 0;
}