邻接矩阵的广度优先搜索C++

邻接矩阵是一种常见的图的存储方式，广度优先搜索是一种常用的图遍历算法。在C++中，我们可以使用邻接矩阵来实现广度优先搜索，步骤如下：

1. 定义邻接矩阵和队列

   const int MAXN = 100; // 图的最大节点数
   int g[MAXN][MAXN]; // 邻接矩阵
   bool visited[MAXN]; // 标记节点是否已经被访问过
   queue<int> q; // 存放待遍历的节点

2. 初始化邻接矩阵和visited数组

   memset(g, 0, sizeof(g)); // 初始化为0
   memset(visited, false, sizeof(visited)); // 初始化为false

3. 添加边

   int u, v;
   // 从节点u到节点v有一条边
   g[u][v] = 1;

4. 广度优先搜索

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

       while (!q.empty()) {
           int cur = q.front(); // 取出队头元素
           q.pop();
           cout << cur << " "; // 访问当前节点

           for (int i = 0; i < MAXN; i++) {
               if (g[cur][i] && !visited[i]) { // 如果cur和i之间有边并且i没有被访问过
                   visited[i] = true; // 标记i已经被访问过
                   q.push(i); // 将i加入队列
               }
           }
       }
   }

完整代码示例：

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN = 100; // 图的最大节点数
int g[MAXN][MAXN]; // 邻接矩阵
bool visited[MAXN]; // 标记节点是否已经被访问过
queue<int> q; // 存放待遍历的节点

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

    while (!q.empty()) {
        int cur = q.front(); // 取出队头元素
        q.pop();
        cout << cur << " "; // 访问当前节点

        for (int i = 0; i < MAXN; i++) {
            if (g[cur][i] && !visited[i]) { // 如果cur和i之间有边并且i没有被访问过
                visited[i] = true; // 标记i已经被访问过
                q.push(i); // 将i加入队列
            }
        }
    }
}

int main() {
    memset(g, 0, sizeof(g)); // 初始化为0
    memset(visited, false, sizeof(visited)); // 初始化为false

    // 添加边
    g = 1;
    g = 1;
    g = 1;
    g = 1;
    g = 1;
    g = 1;

    bfs(0); // 从节点0开始遍历

    return 0;
}