图论05-【无权无向】-图的广度优先BFS遍历-路径问题/检测环/二分图/最短路径问题

1. 代码仓库

https://github.com/Chufeng-Jiang/Graph-Theory

2. 单源路径

2.1 思路

1. 构造visited数组和pre数组
   1.1 visited数组记录当前节点是否访问过
   也可以不使用visited数组，pre数组全部初始化为-1，联通的顶点对应的pre数组的值为前一个节点，pre数组中值为-1的都是不连通的顶点。
   1.2 pre数组记录当前节点的前一个节点
2. 使用pre数组对终点进行反推回源点，并记录
3. 将终点到原点的路径，反序输出

区别DFS和BFS两种解法中，递归部分参数问题。

DFS实际上是递归，把参数传进去就开始递归了。而BFS实际上是使用队列进行模拟，只需要传入源就可以，两个参数也可以但是没必要。

private void dfs(int v, int parent){ //参数一：当前顶点； 参数二：上一个顶点
private void bfs(int s){

2.2 主要代码

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

    for(int i = 0; i < pre.length; i ++)
        pre[i] = -1;

    bfs(s);
}

private void 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的上一个顶点是v
            }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

3. 所有点对路径

3.1 思路

对所有顶点进行遍历，创建每一个点的单源路径数组。

3.2 主要代码

    public AllPairsPath_UsingSingleSourcePath(Graph G){
        this.G = G;
        paths = new SingleSourcePath[G.V()];
        
        for(int v = 0; v < G.V(); v ++)
            paths[v] = new SingleSourcePath(G, v);
    }
1
2
3
4
5
6
7

4. 联通分量

跟DFS是一样的

public CC(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); //从0开始
            cccount ++;      //统计联通分量的数量
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5. 环检测

跟DFS也基本一样

5.1 思路

从某一点v出发，找到了点w，w被访问过，并且w不是v的前一个节点

5.2 主要代码

public CycleDetection(Graph G){

   this.G = G;
   visited = new boolean[G.V()];
   pre = new int[G.V()];

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

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

// 从顶点 v 开始，判断图中是否有环
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]){ //如果w没有访问过
               queue.add(w);
               visited[w] = true;
               pre[w] = v;
           }
           else if(pre[v] != w) //从s出发，如果w被访问过，并且顶点v的前一个不是w
               return true;
   }
   return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

6. 二分图检测

6.1 思路

二分图可以通过染色过程把顶点区分开，
[-1:顶点还没染色]
[0:一种颜色]
[1:另外一种颜色]

6.2 主要代码

6.2.1 遍历每个联通分量

1. dfs(v, 0) 返回true代表相连的两点颜色不一样，暂未出现矛盾；
2. dfs(v, 0) 返回false代表相连的两点颜色一样，不符合二分图的定义，因此进入if语句块，设置isBipartite = false;并且提前结束循环。

public BipartitionDetection(Graph G){

     this.G = G;
     visited = new boolean[G.V()];
     colors = new int[G.V()];

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

     for(int v = 0; v < G.V(); v ++)
         if(!visited[v])
             if(!bfs(v)){
                 isBipartite = false;
                 break;
             }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6.2.2 判断相邻两点的颜色是否一致

 private boolean bfs(int 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;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

7. 最短路径问题

7.1 思路

1. 引入dis数组;
2. 在从出发顶点进行BFS的时，pre数组记录当前节点的上一个节点，dis数组更新为当前节点到源点的距离=上一个节点到出发点的距离+1。

private int[] dis;
dis[w] = dis[v] + 1;

7.2 代码

public USSSPath(Chapt04_BFS_Path._0402_SingleSourcePath.Graph G, int s){
    this.G = G;
    this.s = s;

    visited = new boolean[G.V()];
    pre = new int[G.V()];
    dis = new int[G.V()];

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

    bfs(s);

    for (int i = 0; i < G.V(); i++) {
        System.out.print(dis[i] + " ");
    }
    System.out.println();
}

private void bfs(int s){ // 区分一下DFS两个参数，DFS实际上是递归，把参数传进去就开始递归了。而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; //w的上一个顶点是v
                dis[w] = dis[v] + 1;
            }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41