C++按广度优先非递归遍历图G。使用辅助队列Q 和访问标志数组visited

以下是C++实现按广度优先非递归遍历图G的代码，使用了辅助队列Q和访问标志数组visited：

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

const int MAXN = 100; // 最大顶点数
bool G[MAXN][MAXN]; // 图的邻接矩阵
bool visited[MAXN]; // 顶点访问标志

// 广度优先遍历
void BFS(int start, int n)
{
    queue<int> Q; // 辅助队列
    Q.push(start); // 将起点入队
    visited[start] = true; // 标记起点已访问

    while (!Q.empty()) // 队列不为空时循环
    {
        int u = Q.front(); // 取出队首顶点
        Q.pop(); // 将队首顶点出队
        cout << u << " "; // 输出顶点

        for (int v = 0; v < n; v++) // 遍历所有顶点
        {
            if (G[u][v] && !visited[v]) // 如果u和v有边且v未访问
            {
                Q.push(v); // 将v入队
                visited[v] = true; // 标记v已访问
            }
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m; // 输入顶点数和边数

    // 初始化邻接矩阵和访问标志数组
    memset(G, false, sizeof(G));
    memset(visited, false, sizeof(visited));

    // 输入边的信息并构建邻接矩阵
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        G[u][v] = true;
        G[v][u] = true;
    }

    // 从顶点0开始广度优先遍历
    BFS(0, n);

    cout << endl;
    return 0;
}

在该代码中，我们先输入图的顶点数和边数，然后读入边的信息并构建邻接矩阵。接着从起点0开始进行广度优先遍历，使用队列Q来存储待访问的顶点，visited数组来记录顶点是否已被访问过。在遍历过程中，我们取出队首顶点u，输出u，并遍历u所有的邻接顶点v。如果v未被访问过，则将v入队，并标记v已被访问过。最终，我们完成了整个图的广度优先遍历。