BFS及其应用

作者: Ice_spring | 来源:发表于2020-04-01 22:51 被阅读0次

BFS及其应用
图的桥和割点
简答（网络摘抄）
大一上acm总结
python-数据结构队列和广度优先搜索（BFS）
无向图中DFS和BFS的应用
宽度优先搜索
合成树脂及应用丛书酚醛树脂及其应用黄发荣等编著
走迷宫(BFS例题)
【生信课程】06-高通量测序-山东大学-生物信息学

内容概要：

BFS类的实现
BFS求解连通分量
BFS求解无向图点对之间的一条最短路径
BFS判定无环图和二分图
BFS与DFS的联系

树与图的广度优先遍历对比

树的层次遍历其实就是一种广度优先遍历。图的广度优先遍历和树的广度优先遍历非常类似，区别只在于图要对节点是否被遍历做记录。

广度优先遍历类

BFS只是和DFS的遍历逻辑不通，有了DFS的基础，不难给出BFS的相关类。
广度优先遍历到某个顶点后，要遍历与它相邻的所有顶点。这个过程使用队列实现。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class GraphBFS {
    private Graph G;
    private boolean[] visited;
    private ArrayList<Integer> order = new ArrayList<>();

    public GraphBFS(Graph G){
        this.G = G;
        visited = new boolean[G.V()];
        for(int v = 0; v < G.V(); v ++)
            if(!visited[v])
                bfs(v);
    }

    private void bfs(int s){
        // 从 s 开始进行BFS
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        visited[s] = true;
        while(!queue.isEmpty()) {
            int v = queue.remove(); // 取队头
            order.add(v);

            for (int w : G.adj(v))
                if (!visited[w]) {
                    queue.add(w);
                    visited[w] = true;
                }
        }
    }
    public Iterable<Integer> order(){
        return order;
    }
    public static void main(String[] args){
        Graph g = new Graph("g.txt");
        GraphBFS graphBFS = new GraphBFS(g);
        System.out.println("BFS :" + graphBFS.order());
    }
}

广度优先遍历一样可以解决求图的连通分量个数、环检测、二分图检测等。

BFS解决单源路径问题

BFS的性质
遍历时由顶点到顶点一定是跨越边数最少的路径。
求解路径问题
两个顶点在同一连通分量表示有路径，从一点出发，记录经过的顶点，直到到达另一顶点这就是一条路径。具体做法就是记录每个顶点是从哪里来的，由于会有访问标记，所以这个值是唯一的，最后从终点到源点反推即得到路径。
由BFS的性质，这个路径一定是跨过的边数最少的路径，如果是无权图，就是最短路径。

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class ShortestPath {
    private Graph G;
    private int s;
    private boolean[] visited;
    private int[] pre;
    private int[] dis;

    public ShortestPath(Graph G, int s){
        this.G = G;
        this.s = s;
        visited = new boolean[G.V()];
        dis = new int[G.V()];
        pre = new int[G.V()];

        for(int i = 0; i < G.V(); i ++) {
            pre[i] = -1;
            dis[i] = -1;
        }

        bfs(s);
    }

    private void bfs(int s){
        // 从 s 开始进行BFS
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        visited[s] = true;
        pre[s] = s;
        dis[s] = 0;

        while(!queue.isEmpty()) {
            int v = queue.remove(); // 取队头

            for (int w : G.adj(v))
                if (!visited[w]) {
                    queue.add(w);
                    visited[w] = true;
                    pre[w] = v;
                    dis[w] = dis[v] + 1;// 距离加一
                }
        }
    }

    public boolean isConnectedTo(int t){
        G.validateVertex(t);
        return visited[t];// 意味着 s 与 t 在同一连通分量;
    }

    public Iterable<Integer> path(int t){
        // s -> t 的路径

        ArrayList<Integer> res = new ArrayList<>();
        if(!isConnectedTo(t)) return res;
        int cur = t;
        while(cur != s){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);
        Collections.reverse(res);
        return res;
    }
    public int dis(int t){
        // s -> t 的距离，不关注路径，只关注最短距离
        G.validateVertex(t);
        return dis[t];

    }
    public static void main(String[] args){
        Graph g = new Graph("g.txt");
        ShortestPath sp = new ShortestPath(g,0);
        System.out.println("0 -> 3: " + sp.dis(3));
    }
}

由上也不难得到所有点对之间的最短路径。

BFS求解连通分量

与DFS解决连通分量问题思路一样，将visited数组定义为整型数组，初值为-1表示没有访问过这个顶点，而非负值就代表顶点所属的连通分量。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class ConnectedComponents {
    private Graph G;
    private int[] visited;
    private int cccount = 0;

    public ConnectedComponents(Graph G){
        this.G = G;
        visited = new int[G.V()];
        for(int i = 0; i < visited.length; i ++)
            visited[i] = -1;

        for(int v = 0; v < G.V(); v ++)
            if(visited[v] == -1) {
                bfs(v, cccount);
                cccount ++;
            }
    }
    private void bfs(int s, int ccid){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        visited[s] = ccid;

        while(!queue.isEmpty()){
            int v = queue.remove();

            for(int w: G.adj(v))
                if(visited[w] == -1){
                    queue.add(w);
                    visited[w] = ccid;
                }
        }
    }

    public int count(){ // 返回连通分量个数
        return cccount;
    }

    public boolean isConnected(int v, int w){
        return visited[v] == visited[w];
    }

    public ArrayList<Integer>[] components(){
        // 返回各个连通分量
        ArrayList<Integer>[] res = new ArrayList[cccount];
        for(int i = 0; i < cccount; i ++)
            res[i] = new ArrayList<>();
        for(int v = 0; v < G.V(); v ++)
            res[visited[v]].add(v);
        return res;
    }
    public static void main(String args[]){
        Graph g = new Graph("g.txt");
        ConnectedComponents cc = new ConnectedComponents(g);
        ArrayList<Integer>[] comp = cc.components();
        for(int ccid = 0; ccid < comp.length; ccid ++) {
            System.out.print(ccid + ": ");
            for (int w : comp[ccid])
                System.out.print(w + " ");
            System.out.println();
        }
    }
}

BFS求解环检测

与DFS解决该问题思路一样，如果一个被访问的顶点再次被访问到，且这个顶点不是它前一个节点，则说明图中存在环。

import java.util.LinkedList;
import java.util.Queue;

public class CycleDetection {
    private Graph G;
    private boolean[] visited;
    private int[] pre;
    private boolean hasCycle = false;

    public CycleDetection(Graph G){
        this.G = G;
        visited = new boolean[G.V()];
        pre = new int[G.V()];
        for(int v = 0; v < G.V(); v ++)
            pre[v] = -1;

        for(int v = 0; v < G.V(); v ++)
            if(!visited[v])
                if(bfs(v)){ // 如果通过BFS检测出环
                    hasCycle = true;
                    break;
                }
    }
    private boolean bfs(int s){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        visited[s] = true;
        pre[s] = s;
        while(!queue.isEmpty()){
            int v = queue.remove();
            for(int w: G.adj(v)){
                if(!visited[w]){
                    queue.add(w);
                    visited[w] = true;
                    pre[w] = v;
                }
                // 这里是逻辑的关键
                // 如果 w 已经被访问过了，我们还必须判断，w 不是 v 的上一个节点
                // 如果 w 不是 v 的上一个节点，说明我们找到了一个环
                else if(pre[v] != w)
                    return true;
            }
        }
        return false;
    }
    public boolean hasCycle(){
        return hasCycle;
    }
    public static void main(String[] args) {

        Graph g = new Graph("g.txt");
        CycleDetection cycleDetection = new CycleDetection(g);
        System.out.println(cycleDetection.hasCycle());
    }
}

BFS判定二分图

通过染色操作完成，用两种颜色对图进行染色，如果可以每两个相邻顶点都不同色，则这个图是二分图。

import java.util.LinkedList;
import java.util.Queue;

public class BiPartitionDetection {
    private Graph G;
    private boolean[] visited;
    private int[] colors; //  两种颜色,实际 colors 可以兼有 visited 的功能
    private boolean isBipartite = true;

    public BiPartitionDetection(Graph G){
        this.G = G;
        visited = new boolean[G.V()];
        colors = new int[G.V()];

        for(int v = 0; v < G.V(); v ++)
            colors[v] = -1;

        for(int v = 0; v < G.V(); v ++)
            if(!visited[v])
                if(!bfs(v)){
                    isBipartite = false;
                    break;
                }
    }

    private boolean bfs(int s){
        // 从s 点开始看整张图是否是二分图
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        visited[s] = true;
        colors[s] = 0;
        while (!queue.isEmpty()){
            int v = queue.remove();
            for(int w: G.adj(v)) {
                if (!visited[w]) {
                    queue.add(w);
                    visited[w] = true;
                    colors[w] = 1 - colors[v];
                }
                else if(colors[v] == colors[w]){
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {

        Graph g = new Graph("g.txt");
        BiPartitionDetection bipartitionDetection = new BiPartitionDetection(g);
        System.out.println(bipartitionDetection.isBipartite);
    }
}

BFS与DFS之间的联系

观察BFS和DFS的非递归代码：
BFS

visited[0...V-1] = false;
for(int v = 0; v < G.V(); v ++)
    if(!visited[v])
        bfs(v);

void bfs(int s){
    Queue<Integer> queue = new LinkedList<>();
    queue.add(s);
    visited[s] = true;
    while(!queue.isEmpty()) {
        int v = queue.remove(); 
        order.add(v);
        for (int w : G.adj(v))
            if (!visited[w]) {
                queue.add(w);
                visited[w] = true;
            }
    }
}

DFS

visited[0...V-1] = false;
for(int v = 0; v < G.V(); v ++)
    if(!visited[v])
        bfs(v);

void dfs(int s){
    Stack<Integer> stack = new Stack<>();
    stack.add(s);
    visited[s] = true;
    while(!stack.isEmpty()) {
        int v = stack.remove(); 
        order.add(v);
        for (int w : G.adj(v))
            if (!visited[w]) {
                stack.add(w);
                visited[w] = true;
            }
    }
}

它们的非递归代码的区别只在于数据结构使用的不同，一个用栈一个用队列，而其它的逻辑完全一样。也就只是在容器中循环取元素的顺序不同而已。

BFS及其应用
内容概要： BFS类的实现 BFS求解连通分量 BFS求解无向图点对之间的一条最短路径 BFS判定无环图和二分图 ...
图的桥和割点
内容概要：图中的桥图的DFS遍历树和BFS遍历树及其与寻桥算法的关系图的割点 DFS和BFS的对比小结桥(...
简答（网络摘抄）
1.DFS 和BFS 的区别及其使⽤用场景？ http://blog.csdn.net/lulipeng_cpp/...
大一上acm总结
先说说都学了些什么吧。1 . 三个算法专题，高精度，dfs，bfs，高精度基础应用没什么问题，dfs，bfs，题做...
python-数据结构队列和广度优先搜索（BFS）
1.队列和广度优先搜索（BFS）原题来自LeetCode 广度优先搜索（BFS）的一个常见应用是找出从根结点到目...
无向图中DFS和BFS的应用
DFS和BFS的应用-寻找路径寻找路径就是记录下DFS和BFS访问过的路径节点然后可以通过这些节点推出路径。可以...
宽度优先搜索
Java BFS应用场景图的遍历 Traversal in Graph 层级遍历 Level Order Trav...
合成树脂及应用丛书酚醛树脂及其应用黄发荣等编著
合成树脂及应用丛书酚醛树脂及其应用黄发荣等编著书籍名称：合成树脂及应用丛书酚醛树脂及其应用编著人员：...
走迷宫(BFS例题)
BFS例题---走迷宫 BFS对应数据结构queue BFS算法时间复杂度O(n^2) BFS算法不走走过的点的...
【生信课程】06-高通量测序-山东大学-生物信息学
高通量测序技术及其应用高通量测序技术及其应用高通量测序技术在精准医疗的应用鉴定新疾病的基因image.png...