广度优先搜索 BFS

单点最短路径问题：从起点s到给定目的顶点v是否存在一条路径？如果有，找出其中最短的那条（所含边数最少）
解决这个问题的经典方法叫做 广度优先搜索（BFS）。DFS并不能解决这个问题，相比之下，BFS正是为了这个目标才出现的。

1、基本思想

广度优先搜索要找到从 s 到 v 的最短路径，从s开始，在所有由一条边就可以到达的顶点中寻找 v，如果找不到就继续在与 s 距离两条边的所有顶点中查找 v，如此一直进行。因此，BFS 是以距离递增的方式来搜索路径的。

BFS使用了一个 队列 来保存所有已被标记但其邻接表还未被检查的顶点。

思路：
初始先将 起点s 加入队列，然后重复以下步骤直到队列为空：
- 取队列中的第一个顶点 v 并标记它
- 将与 v 相邻的所有未被标记过的顶点加入队列

2、算法实现

注意：bfs() 不是递归的。不像 dfs() 中采用递归并隐式地使用栈，bfs() 中显式地使用了一个队列。

/*
 * 广度优先搜索，按照与起点的距离的顺序来遍历所有顶点
 */
public class BreadFirstPaths {
    private boolean[] marked;   //是否以被标记
    private int[] edgeTo;       //从起点到一个顶点的最短路径上的最后一个顶点
    private final int s;        //起点

    public BreadFirstPaths(Graph G,int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        bfs(G, s);
    }

    //广度优先搜索，同样会标记所有与s连通的顶点
    private void bfs(Graph G, int s){
        Queue<Integer> queue = new Queue<Integer>();
        marked[s] = true;   //标记起点
        queue.enqueue(s);   //将起点加入队列
        while (!queue.isEmpty()) {
            int v = queue.dequeue();      //从队列中删除下一个顶点
            for (int w : G.adj(v))
                if (!marked[w]) {      //对于每个未被标记的相邻顶点
                    edgeTo[w] = v;     //保存最短路径的最后一条边
                    marked[w] = true;  //标记它，因为最短路径已知
                    queue.enqueue(w);  //并将它添加到队列中
                }
        }
    }

    //是否存在从起点s到v的路径  （和DFS搜索中的实现相同）
    public boolean hasPathTo(int v){
        return marked[v];
    }

    //起点s到v的 最短路径，如果不存在则返回null （和DFS搜索中的实现相同）
    public Iterable<Integer> PathTo(int v){
        if (!hasPathTo(v))  return null;
        Stack<Integer> path = new Stack<Integer>();
        for (int x=v; x!=s; x=edgeTo[x])
            path.push(x);
        path.push(s);
        return path;
    }
}

3、符号图

在应用中，图一般使用的是字符串而非整数来表示顶点。可以编写合适的方法将输入流中的顶点名和图算法使用的顶点索引对应起来。

4、总结

本章总结：
- 图的术语
- 图的表示方法
- 图处理相关的类的设计模式。其实现算法通过在相关类的构造函数中对图进行预处理，构造所需的数据结构来支持用例对图性质的查询
- 深度优先搜索、广度优先搜索

下面总结了已经学习过的所有图算法的实现：