图论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}}
}

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);}

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 ++;      //统计联通分量的数量}
}

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的前一个不是wreturn true;}return false;
}

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;}}

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;}

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的上一个顶点是vdis[w] = dis[v] + 1;}}
}