C++ 实现图的广度优先遍历 (BFS) - 代码示例和解释

下面是一个使用 C++ 实现图的广度优先遍历的示例代码：

#include <iostream>
#include <list>
#include <queue>

using namespace std;

class Graph {
private:
    int numVertices;
    list<int> *adjLists;
    bool *visited;

public:
    Graph(int vertices) {
        numVertices = vertices;
        adjLists = new list<int>[vertices];
        visited = new bool[vertices];
    }

    void addEdge(int src, int dest) {
        adjLists[src].push_back(dest);
        adjLists[dest].push_back(src);
    }

    void BFS(int startVertex) {
        for (int i = 0; i < numVertices; i++) {
            visited[i] = false;
        }

        queue<int> queue;
        visited[startVertex] = true;
        queue.push(startVertex);

        while (!queue.empty()) {
            int currVertex = queue.front();
            cout << currVertex << ' '; // 打印当前顶点
            queue.pop();

            list<int>::iterator it;
            for (it = adjLists[currVertex].begin(); it != adjLists[currVertex].end(); ++it) {
                int adjVertex = *it;
                if (!visited[adjVertex]) {
                    visited[adjVertex] = true;
                    queue.push(adjVertex);
                }
            }
        }
    }
};

int main() {
    Graph graph(6);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 4);
    graph.addEdge(3, 4);
    graph.addEdge(3, 5);
    graph.addEdge(4, 5);

    cout << 'BFS traversal starting from vertex 0: '; // 打印开始顶点
    graph.BFS(0);

    return 0;
}

这个示例中，我们首先实现了一个Graph类，该类包含了图的邻接链表表示和一些必要的方法。addEdge方法用于添加边，BFS方法用于执行广度优先遍历。

在BFS方法中，我们首先初始化visited数组为false，表示所有顶点都未被访问过。然后，我们使用一个队列来存储待访问的顶点。我们从起始顶点开始，将其标记为已访问，并将其加入队列中。然后，我们不断从队列中取出顶点，访问它，并将其未访问的邻居顶点加入队列中。这个过程会一直进行，直到队列为空。

在主函数中，我们创建一个具有6个顶点的图，并添加一些边。然后，我们调用BFS方法从顶点0开始进行广度优先遍历，并输出遍历结果。

运行上述代码，输出结果为：

BFS traversal starting from vertex 0: 0 1 2 3 4 5

这表示从顶点0开始的广度优先遍历顺序是0、1、2、3、4、5。