介绍
广度优先搜索（BFS）是一种常用的图形遍历算法，它在按层次顺序遍历图形时特别有用。在BFS中，我们从某个节点开始，首先访问其相邻节点，然后是二级邻居，然后是三级邻居，以此类推。我们通常使用一个队列来帮助我们实现BFS。
在本文中，我们将展示如何使用C语言中的向量和队列实现BFS。我们将使用CLRS算法（《算法导论》）来实现。这将是一个从头到尾的指南，因此我们将从基础知识开始，并一步步构建我们的代码。
实现BFS的数据结构
在我们开始实现BFS之前，我们需要一些数据结构来表示图形。我们将使用以下三个数据结构：
//表示节点的结构
struct node {
int data; //数据
bool visited; //表示节点是否被访问过
vector neighbors; //节点的邻居
};
//表示边的结构
struct edge {
node* from; //边的起点
node* to; //边的终点
};
//用于表示图的结构
struct graph {
vector nodes; //节点列表
vector edges; //边列表
//添加节点到图中
void add_node(int data) {
node* n = new node;
n->data = data;
n->visited = false;
nodes.push_back(n);
}
//添加边到图中
void add_edge(node* from, node* to) {
edge* e = new edge;
e->from = from;
e->to = to;
from->neighbors.push_back(to);
edges.push_back(e);
}
};
以上代码中，我们定义了三个结构来表示节点、边和图。节点结构包含了节点的数据、节点是否被访问过以及节点的邻居。边结构包含起点和终点。图结构包含节点列表和边列表。
实现BFS算法
现在我们已经有了一些数据结构来表示图形，我们可以开始实现BFS算法。我们将从一个简单的非递归版本开始，然后向递归版本转换。
非递归版本的BFS算法
下面是CLRS算法（第3版）中非递归版本的BFS算法实现。它使用一个队列来保存节点的邻居。我们使用标志visited来记录节点是否已被访问，这将帮助我们防止在处理图中的循环时无限循环：
void bfs(graph* g, node* start) {
queue q; //定义队列
//将起始节点标记为已访问并将其添加到队列中
start->visited = true;
q.push(start);
//遍历队列
while (!q.empty()) {
//从队列中获取下一个节点并打印其值
node* current = q.front();
cout << current->data << endl;
//遍历当前节点的每一个邻居
vector::iterator i;
for (i = current->neighbors.begin(); i != current->neighbors.end(); i++) {
node* n = *i;
//如果邻居没有被访问，则将其标记为已访问并将其添加到队列中
if (!n->visited) {
n->visited = true;
q.push(n);
}
}
//从队列中删除已处理的节点
q.pop();
}
}
以上代码实现了一个非递归版本的BFS算法。它使用队列来遍历每个节点的邻居，并将节点的未访问邻居添加到队列中。此过程一直持续到队列为空。
递归版本的BFS算法
下面是递归版本的BFS算法实现，它使用递归来遍历每个节点的邻居。与non递归版本的算法类似，我们使用visited标志来防止无限循环：
void bfs_recursion(graph* g, node* start, queue& q) {
//退出条件
if (start == NULL) {
return;
}
//标记节点已访问并将其添加到队列中
start->visited = true;
q.push(start);
cout << start->data << endl;
//遍历当前节点的每一个邻居
vector::iterator i;
for (i = start->neighbors.begin(); i != start->neighbors.end(); i++) {
node* n = *i;
//如果邻居没有被访问，则递归地调用BFS算法
if (!n->visited) {
bfs_recursion(g, n, q);
}
}
}
以上代码实现了递归版本的BFS算法。与非递归版本类似，它使用visited标志来防止无限循环，然后使用递归来遍历每个节点的邻居。
使用BFS算法解决问题
现在我们已经实现了BFS算法，我们可以使用它来解决图论问题。在这里，我们将演示一个基于BFS的例子，其中我们将确定图中节点之间的最短路径。
最短路径问题的BFS算法实现
下面是CLRS算法（第3版）中BFS算法解决最短路径问题的实现。它使用BFS算法来确定节点之间的最短路径。BFS算法基于图中的层次结构，因此它是一种天然的最短路径算法：
void bfs_shortest_path(graph* g, node* start) {
queue q; //定义队列
//将起始节点标记为已访问并将其添加到队列中
start->visited = true;
q.push(start);
int level = 0;
//遍历队列
while (!q.empty()) {
int size = q.size();
cout << "Level " << level << ": ";
while (size--) {
//从队列中获取下一个节点并打印其值
node* current = q.front();
cout << current->data << " ";
//遍历当前节点的每一个邻居
vector::iterator i;
for (i = current->neighbors.begin(); i != current->neighbors.end(); i++) {
node* n = *i;
//如果邻居没有被访问，则将其标记为已访问并将其添加到队列中
if (!n->visited) {
n->visited = true;
q.push(n);
}
}
//从队列中删除已处理的节点
q.pop();
}
level++;
cout << endl;
}
}
以上代码实现了基于BFS算法的最短路径问题解决。它使用队列来遍历每个节点的邻居，并将节点的未访问邻居添加到队列中。打印节点的值并增加层计数器。
使用BFS算法解决最短路径问题的示例
下面是一个示例，演示如何使用BFS算法解决最短路径问题。在这里，我们将使用以下图形：
graph g;
g.add_node(1);
g.add_node(2);
g.add_node(3);
g.add_node(4);
g.add_node(5);
g.add_node(6);
g.add_edge(g.nodes[0], g.nodes[1]);
g.add_edge(g.nodes[0], g.nodes[3]);
g.add_edge(g.nodes[1], g.nodes[2]);
g.add_edge(g.nodes[3], g.nodes[4]);
g.add_edge(g.nodes[4], g.nodes[5]);
这是一个简单的有向图，我们将使用BFS算法来找到节点1和节点6之间的最短路径：
//找到节点1和节点6之间的最短路径
node* start = g.nodes[0];
node* end = g.nodes[5];
vector path;
path.push_back(start);
queue q;
q.push(start);
while (!q.empty()) {
//从队列中获取下一个节点
node* current = q.front();
q.pop();
//遍历当前节点的每一个邻居
vector::iterator i;
for (i = current->neighbors.begin(); i != current->neighbors.end(); i++) {
node* n = *i;
//如果邻居没有被访问，则将其标记为已访问并将其添加到队列中
if (!n->visited) {
n->visited = true;
q.push(n);
//将节点添加到路径中
path.push_back(n);
//如果找到终点，则返回路径
if (n == end) {
cout << "Path: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->data << " ";
}
cout << endl;
return;
}
}
}
}
这段代码使用BFS算法来找到从节点1到节点6的最短路径。它使用一个path向量来记录路径，每当找到一个新节点时就将其添加到path向量中。一旦找到终点，它将打印路径并返回。
结束语
在本文中，我们已经看到了如何使用向量和队列实现BFS算法。我们从基础算法开始，然后一步步地构建我们的代码，直到最后我们实现了一个从一个节点到另一个节点的最短路径。这是开始学习图形算法的很好的起点，并且为深入了解其他算法（如Dijkstra和Prim）打下了基础。