图论算法（二）广度优先搜索

这是一种连通图的常用遍历策略，通常用于求起点到各点的最短路径，以及求两点之间的最优路径等问题。首先我们先来看看广度优先搜索的具体方法吧：

对于一个连通图，我们假设一开始所有顶点均未被访问，广度优先搜索的主要操作如下：

1 选择图中任意一个顶点 v 作为起点进行访问，并将顶点 v 标为已访问。
2 遍历并访问与顶点 v 相邻且未被访问的所有顶点 c1c1, c2c2, …, ckck；接着遍历并访问与顶点 c1c1, c2c2, …, ckck 相邻且未被访问的顶点——也就是依次访问所有相邻顶点的相邻顶点；以此类推，直到所有顶点均被访问。

对于算法的具体实现，结合队列先进先出的特性，我们可以借助队列这一数据结构来实现广度优先搜索：

1 任意选择一个顶点 v 作为起点，加入队列；
2 访问队首元素 v 并标记，将其从队列中删除；
3 遍历与顶点 v 相邻且未被访问的所有顶点 c1c1, c2c2, …, ckck，并依次加入到队列中；
4 重复第二步和第三步操作，直到队列为空。

void bfs(int start_vertex) {
     queue<int> bfs_queue;
     bfs_queue.push(start_vertex);
     while (!bfs_queue.empty()) {
         int vertex = bfs_queue.front();
         cout << vertex << endl;
         bfs_queue.pop();
         for (int adj_vertex: edges[vertex]) {
             if (!visited[adj_vertex]) {
                 visited[adj_vertex] = true;
                 bfs_queue.push(adj_vertex);
             }
         }
     }
}