0107连通分量-无向图-数据结构和算法(Java)

1 API

深度优先搜索下一个直接应用就是找出一幅图中的连通分量,定义如下API。

public class CC
	CC(Graph g)	预处理构造函数
boolean	connected(int v, int w)	v和w连通吗
int	count()	连通分量数
int	id(int v)	v所在的连通分量标识符(0~count()-1)

2 代码实现和分析

package com.gaogzhen.datastructure.graph.undirected;import com.gaogzhen.datastructure.stack.Stack;
import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.Queue;import java.util.*;/*** 无向图连通分量* @author: Administrator* @createTime: 2023/03/08 20:18*/
public class CC {/*** 顶点是否标记数组*/private boolean[] marked;/*** 顶点所在连通分量标志:0~count()-1*/private int[] id;/*** 每个连通分量顶点数量*/private int[] size;/*** 连通分量数量*/private int count;/*** 要处理的无向图*/private Graph graph;/*** 计算给定无向图的连通分量* @param graph 指定的无向图*/public CC(Graph graph) {this.graph = graph;int len = graph.V();// 初始化marked = new boolean[len];id = new int[len];size = new int[len];// 搜索连通分量bfs();}/*** 深度优先搜索连通分量*/private void dfs() {// 深度优先非递归实现，借助栈Stack<Iterator<Integer>> c = new Stack<>();// 搜索连通分量for (int v = 0; v < graph.V(); v++) {// 遍历图中所有顶点，以没有被标记过的顶点为起点，搜索连通分量// 执行完一次bsf，标记一个包含顶点v的连通分量if (!marked[v]) {dfs(c, v);// 连通分量标记+1count++;}}}/*** 深度优先搜索连通分量* @param v 起点*/private void dfs(Stack<Iterator<Integer>> c, int v) {if (!marked[v]) {// 起点未标记，标记计数加1// 起点默认没标记，可以不加是否标记判断marked[v] = true;id[v] = count;size[count]++;Iterable<Integer> iterable = graph.adj(v);Iterator<Integer> it;if (iterable != null && (it = iterable.iterator()) != null){// 顶点对应的邻接表迭代器存入栈c.push(it);}}while (!c.isEmpty()) {Iterator<Integer> it = c.pop();int x;while (it.hasNext()) {// 邻接表迭代器有元素，获取元素x = it.next();if (!marked[x]) {// 顶点未被标记，标记计数+1marked[x] = true;id[x] = count;size[count]++;if (it.hasNext()) {// 邻接表迭代器有元素重新入栈c.push(it);}// 深度优先原则，当前迭代器入栈，新标记顶点的邻接表迭代器入栈，下次循环优先访问Iterable<Integer> iterable = graph.adj(x);if (iterable != null && (it = iterable.iterator()) != null){c.push(it);}break;}}}}/*** 广度优先搜索连通分量*/private void bfs() {// 广度优先非递归实现，借助队列Queue<Integer> q = new Queue<>();// 搜索连通分量for (int v = 0; v < graph.V(); v++) {// 遍历图中所有顶点，以没有被标记过的顶点为起点，搜索连通分量// 执行完一次bsf，标记一个包含顶点v的连通分量if (!marked[v]) {bfs(q, v);// 连通分量标记+1count++;}}}private void bfs(Queue<Integer> q, int v) {marked[v] = true;id[v] = count;size[count]++;q.enqueue(v);while (!q.isEmpty()) {Integer x = q.dequeue();for (Integer w : graph.adj(x)) {if (!marked[w]) {marked[w] = true;id[w] = count;size[count]++;q.enqueue(w);}}}}/*** 给定顶点所在的连通分量标记* @param v 给定顶点* @return 顶点所在的连通分量标记* @throws IllegalArgumentException unless {@code 0<= v < V}*/public int id(int v) {validateVertex(v);return id[v];}/*** 顶点v和w是否连通（是否在同一个连通分量内）* @param v 顶点v* @param w 顶点w* @return  {@code true} 如果{@code v}和{@code w}在同一个连通分量内；否则{@code false}* @throws IllegalArgumentException unless {@code 0 <= v < V}* @throws IllegalArgumentException unless {@code 0 <= w < V}*/public boolean connected(int v, int w) {validateVertex(v);validateVertex(w);// 如果v和w在同一连通分量，那么连通分量标记相等；否则falsereturn id[v] == id[w];}/*** 返回无向图{@code graph}中连通分量数量* @return  返回无向图{@code graph}中连通分量数量*/public int count() {return count;}/*** 检查指定的顶点是否是有效顶点* @param v 给定顶点* @throws IllegalArgumentException unless {@code 0<= v < V}*/private void validateVertex(int v) {int V = marked.length;if (v < 0 || v >= V) {throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));}}public void display() {Map<Integer, ArrayList<Integer>> map = new HashMap<>(count);for (int i = 0; i < count; i++) {map.put(i, new ArrayList<>());}for (int i = 0; i < id.length; i++) {int k = id[i];ArrayList<Integer> list = map.get(k);list.add(i);map.put(k, list);}System.out.println("分量标记\t顶点数量\t顶点");for (int i = 0; i < count; i++) {ArrayList<Integer> l = map.get(i);System.out.println(i +"\t\t" + l.size() + "\t\t" + l);}}
}

这里广度优先搜索和深度优先搜索都能完成连通分量的搜索和标记，这里以广度优先搜索为例，简单讲解下算法。

说明：

1. 算法第四版给出的是深度优先的递归版本实现，我们这里给出了非递归的广度优先搜索和深度优先搜索实现。
2. 每次bfs(q, v)一定能保证完成包含顶点v的这个连通分量的搜索，这样外层for遍历所有顶点，在该连通分量的顶点（被标记）不在执行bfs；不在该连通分量的顶点（未被标记），一定是属于其他连通分量。直至遍历结束。
3. bsf(q,v)通过先标记起点v,在标记和顶点v距离1条边的顶点，2条边的顶点，依次类推，直到标记所有连通的顶点。
4. bfs(q, v)内顶点都属于同一连通分量，id[]记录这些顶点对应的连通分量标记就相同；每标记一个顶点，相应的记录该连通分量size[]顶点数量+1。

思考：

1. 这里为什么即可以用广度优先又可以用深度优先呢？

命题C。深度优先搜索和广度优先搜索的预处理使用的时间和空间与V+E成正比且可以在常数时间内处理关于图的连通性查询。

证明。有代码可以知道每个邻接表的元素都只会被检查一次，共有2E个元素（每条边2个）。

测试

测试代码：

public static void testCC() {String path = "H:\\gaogzhen\\java\\projects\\algorithm\\asserts\\tinyG.txt";In in = new In(path);Graph graph = new Graph(in);CC cc = new CC(graph);int v = 0, w = 5;System.out.println("顶点 " + v + " 和顶点 " + w + "是否连通：" + cc.connected(v, w));System.out.println("顶点 " + w + "连通分量标记：" + cc.id(w));System.out.println("连通分量数量：" + cc.count());cc.display();
}

测试结果：

顶点 0 和顶点 5是否连通：true
顶点 5连通分量标记：0
连通分量数量：3
分量标记	顶点数量	顶点
0		7		[0, 1, 2, 3, 4, 5, 6]
1		2		[7, 8]
2		4		[9, 10, 11, 12]

后记

如果小伙伴什么问题或者指教，欢迎交流。

❓QQ:806797785

⭐️源代码仓库地址：https://gitee.com/gaogzhen/algorithm

参考链接:

[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法：第4版[M].北京：人民邮电出版社，2012.10.p344-348.