以邻接矩阵形式存储的图的广度优先遍历

广度优先遍历（BFS）是一种遍历图的算法，它从图中某个顶点开始遍历，依次访问该顶点的所有邻接点，然后再依次访问邻接点的邻接点，直到遍历完整个图。BFS 通常借助队列来实现。

以邻接矩阵形式存储的图的广度优先遍历算法步骤如下：

1.定义一个队列，把起始顶点压入队列。

2.把起始顶点标记为已访问。

3.从队列中弹出一个顶点，访问该顶点的所有未访问的邻接点，并把它们标记为已访问，然后把这些邻接点压入队列。

4.重复步骤3，直到队列为空。

下面是一个示例代码实现：

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

const int MAX_SIZE = 100;
int graph[MAX_SIZE][MAX_SIZE]; // 邻接矩阵存储图
bool visited[MAX_SIZE]; // 标记顶点是否已访问

void BFS(int start, int n)
{
    queue<int> q;
    q.push(start); // 把起始顶点压入队列
    visited[start] = true; // 标记起始顶点已访问

    while (!q.empty())
    {
        int curr = q.front(); // 取出队头顶点
        q.pop();

        cout << curr << " "; // 访问当前顶点

        // 遍历当前顶点的所有邻接点
        for (int i = 0; i < n; i++)
        {
            if (graph[curr][i] == 1 && !visited[i])
            {
                q.push(i); // 把邻接点压入队列
                visited[i] = true; // 标记邻接点已访问
            }
        }
    }
}

int main()
{
    int n; // 顶点个数
    cin >> n;

    // 输入邻接矩阵
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> graph[i][j];
        }
    }

    // 广度优先遍历
    for (int i = 0; i < n; i++)
    {
        if (!visited[i])
        {
            BFS(i, n);
        }
    }

    return 0;
}