广度优先搜索

广度优先搜索算法 Breadth First Search

在一个无权图中（或图中所有边的权值均为 $1$）的情况下，我们会使用广度优先搜索算法来实现。广度优先搜索算法的代码也很简洁：

struct node{
    int pos;
    int steps;
}; queue<node> que;
struct Edge{
    int to;
    int weight;
}; vector<Edge> G[105];
// 记录一个点是否被访问过，防止出现循环。
int vis[105];

void bfs(int start){
    que.push(start)  // 将起点加入队列。
    while(!que.empty()){
        node t = que.front();
        que.pop();
        // 如果走到目标答案，就输出答案并终止循环。
        if (t.pos == terminal){
            cout << t.steps << endl;
            return ;
        }
        // 遍历从 t 开始所有的边。
        for (Edge next : G[t]){
            // 如果被访问过了，就略过。
            if (vis[next.to]) continue;
            vis[next.to] = 1;
            // 将新的节点加入到队列之中。
            que.push((node){next.to, t.steps + next.weight});
        }
    }
    return ;
}

我们已经知道，在一般的地图问题中广度优先搜索的效率非常高。那我们是否可以加以改进广度优先算法，让它适配带权图呢？答案是可以的，经过改编后的算法就是大名鼎鼎的 Dijkstra 算法。