图的宽度优先遍历算法

图的宽度优先遍历（Breadth First Search，BFS）算法是一种用于遍历图的算法。该算法从指定的起始节点开始，逐层访问其它节点，直到遍历完整个图为止。

下面是一种常见的实现方式：

1. 创建一个队列，并把起始节点放入队列中。

2. 将起始节点标记为已访问。

3. 从队列中取出下一个节点，访问该节点，并将其所有未曾访问过的邻居节点放入队列中。

4. 将这些邻居节点标记为已访问。

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

以下是C++语言实现的图的宽度优先遍历算法的示例代码

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 邻接表表示法的结构体定义
struct Graph {
    int V; // 图的节点数
    vector<vector<int>> adj; // 存储邻接表的二维数组
};

// 初始化一个包含V个节点的图
Graph initGraph(int V) {
    Graph g;
    g.V = V;
    g.adj.resize(V);
    return g;
}

// 将边(v, w)添加到图g中
void addEdge(Graph& g, int v, int w) {
    g.adj[v].push_back(w);
}

// 图的宽度优先遍历算法
void bfs(Graph g, int start) {
    vector<bool> visited(g.V, false); // 用来记录每个节点是否被访问过
    queue<int> q; // 存储将要访问的节点

    visited[start] = true; // 标记起始节点为已访问
    q.push(start); // 将起始节点放入队列中

    while (!q.empty()) {
        int v = q.front(); // 取出队列中的第一个节点
        q.pop();

        cout << v << " "; // 访问节点

        // 遍历该节点的所有未曾访问过的邻居节点，并将它们放入队列中
        for (auto w : g.adj[v]) {
            if (!visited[w]) {
                visited[w] = true;
                q.push(w);
            }
        }
    }
}

int main() {
    Graph g = initGraph(5); // 创建一个包含5个节点的图
    addEdge(g, 0, 1);
    addEdge(g, 0, 2);
    addEdge(g, 1, 2);
    addEdge(g, 2, 0);
    addEdge(g, 2, 3);
    addEdge(g, 3, 3);

    cout << "BFS遍历结果：";
    bfs(g, 2);

    return 0;
}

在上述代码中，我们定义了一个Graph结构体来存储邻接表表示法的图，并定义了initGraph和addEdge函数来初始化和添加边到图中。在主函数中，我们创建了一个包含5个节点的图，并调用bfs函数对图进行宽度优先遍历。

在bfs函数中，我们首先创建了一个长度为V的visited数组来记录每个节点是否被访问过，以及一个queue队列来存储将要访问的节点。然后，我们标记起始节点为已访问，并将其放入队列中。接着，我们在一个循环中取出队列中的第一个节点，访问该节点，并遍历该节点的所有未曾访问过的邻居节点，并将它们放入队列中，以便后续访问。循环直到队列为空，即遍历完成。

如果我们使用上面的示例代码进行测试，将输出以下结果：

BFS遍历结果：2 0 3 1

这是因为我们以2为起始节点进行宽度优先遍历，因此我们首先访问节点2，并将其邻居节点0和3放入队列中。接下来，我们取出队列中的第一个节点0，并访问它，并将它的邻居节点1放入队列中。然后，我们取出队列中的第一个节点3，并访问它。最后，我们取出队列中的第一个节点1，并访问它，遍历结束。

需要注意的是，图的宽度优先遍历算法需要使用队列来存储将要访问的节点，并按照队列中的顺序依次访问它们的邻居节点。这样才能确保遍历的顺序是逐层递进的，从而保证遍历的结果是符合预期的。

下面我们通过示意图的方式，模拟一下宽度优先遍历算法的执行过程。

假设我们有如下所示的无向图：

    0 ---- 1
   / \\
  2 -- 3

其中，0、1、2、3表示节点，横线表示边，表示这些节点之间存在连接关系。我们将以节点2为起始节点进行宽度优先遍历。

首先，我们将节点2标记为已访问，并将它放入队列中：

Visited: 2
Queue: 2

接着，我们从队列中取出节点2，并访问它。然后，我们将节点0和3放入队列中：

Visited: 2 0 3
Queue: 0 3

我们继续从队列中取出节点0，并访问它。然后，我们将节点1放入队列中：

Visited: 2 0 3 1
Queue: 3 1

现在，我们从队列中取出节点3，并访问它。由于节点3没有未访问的邻居节点，所以不需要将任何节点放入队列中：

Visited: 2 0 3 1
Queue: 1

最后，我们从队列中取出节点1，并访问它。由于节点1也没有未访问的邻居节点，所以遍历结束：

Visited: 2 0 3 1
Queue:

因此，宽度优先遍历的结果为：2 0 3 1。可以看到，我们首先访问了起始节点2，然后按照2的邻居节点的顺序访问了节点0和节点3，接着按照0和3的邻居节点的顺序访问了节点1。这正是宽度优先遍历算法的执行顺序。