广度优先搜索

Author Avatar
Brian Lee 9月 06, 2018
  • 在其它设备中阅读本文章

《Algorithm》(Sedgewick)笔记:广度优先搜索


原理

遍历图G 时,要找到从sv 的最短路径,从s 开始,在所有一条边就可以到达的顶点中寻找v ,如果找不到就继续在与s 距离两条边的所有顶点中查找v ,如此一直进行。当两次寻找相遇时,合二为一。直到查找到最短路径。


相关问题

单点最短路径

给定一幅图和一个起点s ,回答“从s 到给定目的顶点v 是否存在一条路径?如果有,找出其中最短的那条”


实现

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

先将起点加入队列,然后重复以下步骤直到队列为空:

  1. 取队列中的下一个顶点v 并标记它
  2. 将与v 相邻的所有未被标记过的顶点加入队列

搜索过程

示例图

搜索过程

  1. 首先将顶点0 标记并加入队列
  2. 从队列中删去顶点0 并将其邻居顶点215 标记、加入路径,并加入队列中
  3. 从队列中删除顶点2 并检查其相邻顶点,01 已被标记,将34 标记、加入路径并加入队列
  4. 从队列中删除顶点0 并检查其相邻顶点,发现已经全被标记,于是跳过
  5. 从队列中删除顶点5 并检查其相邻顶点,发现已经全被标记,于是跳过
  6. 从队列中删除顶点3 并检查其相邻顶点,发现已经全被标记,于是跳过
  7. 从队列中删除顶点4 并检查其相邻顶点,发现已经全被标记,于是跳过

代码

public class BFS {
    private boolean[] marked;   //到达该顶点的最短路径是否已知
    private int[] edgeTo;   //到达该顶点已知路径上最后一个顶点
    private int s;  //起点
    public BFS(Graph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        bfs(G, s);
    }
    private void bfs(Graph G, int s) {
        Queue<Integer> queue = new LinkedList<>();
        marked[s] = true;   //标记起点
        queue.offer(s);     //起点加入队列
        while (!queue.isEmpty()) {
            int v = queue.poll();   //从队列中删去下一顶点
            for (int w : G.adj(v)) {
                if (!marked[w]) {   //对每个未被标记的相邻结点
                    edgeTo[w] = v;  //保存最短路径的最后一条边
                    marked[w] = true;   //标记它,因为最短路径已知
                    queue.offer(w); //将它添加到队列中
                }
            }
        }
    }
    public boolean hasPathTo(int v) {
        return marked[v];
    }
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v))  return null;
        Stack<Integer> pathReverse = new Stack<>();
        for (int x = v; x != s; x = edgeTo[x])
            pathReverse.push(x);
        pathReverse.push(s);
        Queue<Integer> path = new LinkedList<>();
        while (!pathReverse.isEmpty())
            path.offer(pathReverse.pop());
        return path;
    }
}

DFS与BFS区别

  • 深度优先搜索搜索一幅图的方式是寻找离起点更远的顶点,只在碰到死胡同时才访问近处的顶点;广度优先搜索会首先覆盖起点附近的顶点,只在临近的所有顶点都被访问了之后才向前进。
  • 深度优先搜索不断深入图中并在栈中保存了所有分叉的顶点;广度优先搜索则像扇面一样扫描图,用一个队列保存访问过的最前端的顶点。
  • 深度优先遍历算法借助于 结构实现;广度优先遍历算法借助于队列 结构实现。

源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S4_Graphs/S4_1_Undirected_Graph/S4_1_5_Breadth_First_Search


本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
本文链接:http://brianleelxt.top/2018/09/06/BFS/