广度优先生成树邻接表

### 使用邻接表实现广度优先生成树

#### 广度优先生成树的概念
广度优先生成树是从图中的某个顶点出发，在访问此顶点之后，依次访问与此顶点相邻且未曾被访问过的全部顶点；再按照这些顶点被访问的先后次序依次访问与它们相邻并且尚未访问过的全部顶点，直到所有和初始节点连通的节点都被访问过为止。如果此时还有未访问到的节点，则另选一个未曾被访问过的起始点重复上述过程，直至所有的节点都已被访问。

#### 邻接表表示法简介
邻接表是一种用于存储稀疏矩阵的有效方法，对于图来说，它由数组加链表构成。每个顶点对应于数组的一个元素，该元素指向一条单向链表，而这条链表包含了所有与这个顶点相连的其他顶点的信息[^1]。

#### 实现思路
为了构建广度优先生成树(BFS Tree)，可以采用队列来辅助遍历操作。具体做法如下：

- 初始化：创建一个空队列Q，并将起点加入其中；
- 记录已访问状态：设置布尔型数组`visited[]`记录哪些结点已经被处理过了；
- 开始循环：当队列不为空时执行以下动作：
- 取出队首元素u作为当前正在探索的位置；
- 对于每一个从未到达过的邻居v（即满足!visited[v]），做两件事：
* 将其标记为已访问并入队等待后续考察；
* 如果需要的话还可以在此处保存父子关系以便最终形成一棵完整的BFS tree。

最后得到的结果就是一颗以指定根为基础展开出来的无环子图——也就是所谓的“广度优先生成树”。

下面是具体的C++代码示例:

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

using namespace std;

class Graph {
private:
    int V; // Number of vertices
    list<int> *adj; // Pointer to an array containing adjacency lists
    
public:
    Graph(int V); // Constructor
    void addEdge(int v, int w);
    void BFS(int s);
};

Graph::Graph(int V) : V(V), adj(new list<int>[V]) {}

void Graph::addEdge(int v, int w){
    adj[v].push_back(w);
}

// Prints BFS traversal from a given source vertex `s`.
void Graph::BFS(int s){
    bool *visited = new bool[V];
    for (int i = 0; i < V; ++i)
        visited[i] = false;
        
    queue<int> q;
    visited[s] = true;
    q.push(s);

    while (!q.empty()){
        s = q.front();
        cout << s << " ";
        q.pop();

        for(auto it = adj[s].begin();it != adj[s].end();++it){
            if(!visited[*it]){
                visited[*it]=true;
                q.push(*it);
            }
        }
    }

    delete [] visited;
}

这段程序定义了一个简单的无权有向图类及其成员函数`BFS()`来进行广度优先搜索。通过调用`addEdge()`,可以在实例化对象后动态添加边。注意这里只打印了路径上的各个顶点编号，实际应用中可能还需要额外维护父指针等信息用来重建整棵树结构。