360免费建站李梦,深圳地产网站制作公司,顺风顺水的公司名字,做项目挣钱的网站文章目录1 API2 代码实现和分析测试后记1 API
深度优先搜索下一个直接应用就是找出一幅图中的连通分量,定义如下API。
public class CCCC(Graph g)预处理构造函数booleanconnected(int v, int w)v和w连通吗intcount()连通分量数intid(int v)v所在的连通分量标识符(0~count()-…
文章目录1 API2 代码实现和分析测试后记1 API
深度优先搜索下一个直接应用就是找出一幅图中的连通分量,定义如下API。
public class CCCC(Graph g)预处理构造函数booleanconnected(int v, int w)v和w连通吗intcount()连通分量数intid(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() {// 深度优先非递归实现借助栈StackIteratorInteger 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(StackIteratorInteger c, int v) {if (!marked[v]) {// 起点未标记标记计数加1// 起点默认没标记可以不加是否标记判断marked[v] true;id[v] count;size[count];IterableInteger iterable graph.adj(v);IteratorInteger it;if (iterable ! null (it iterable.iterator()) ! null){// 顶点对应的邻接表迭代器存入栈c.push(it);}}while (!c.isEmpty()) {IteratorInteger 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);}// 深度优先原则当前迭代器入栈新标记顶点的邻接表迭代器入栈下次循环优先访问IterableInteger iterable graph.adj(x);if (iterable ! null (it iterable.iterator()) ! null){c.push(it);}break;}}}}/*** 广度优先搜索连通分量*/private void bfs() {// 广度优先非递归实现借助队列QueueInteger q new Queue();// 搜索连通分量for (int v 0; v graph.V(); v) {// 遍历图中所有顶点以没有被标记过的顶点为起点搜索连通分量// 执行完一次bsf标记一个包含顶点v的连通分量if (!marked[v]) {bfs(q, v);// 连通分量标记1count;}}}private void bfs(QueueInteger 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() {MapInteger, ArrayListInteger 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];ArrayListInteger list map.get(k);list.add(i);map.put(k, list);}System.out.println(分量标记\t顶点数量\t顶点);for (int i 0; i count; i) {ArrayListInteger l map.get(i);System.out.println(i \t\t l.size() \t\t l);}}
}这里广度优先搜索和深度优先搜索都能完成连通分量的搜索和标记这里以广度优先搜索为例简单讲解下算法。
说明
算法第四版给出的是深度优先的递归版本实现我们这里给出了非递归的广度优先搜索和深度优先搜索实现。每次bfs(q, v)一定能保证完成包含顶点v的这个连通分量的搜索这样外层for遍历所有顶点在该连通分量的顶点被标记不在执行bfs不在该连通分量的顶点未被标记一定是属于其他连通分量。直至遍历结束。bsf(q,v)通过先标记起点v,在标记和顶点v距离1条边的顶点2条边的顶点依次类推直到标记所有连通的顶点。bfs(q, v)内顶点都属于同一连通分量id[]记录这些顶点对应的连通分量标记就相同每标记一个顶点相应的记录该连通分量size[]顶点数量1。
思考
这里为什么即可以用广度优先又可以用深度优先呢 命题C。深度优先搜索和广度优先搜索的预处理使用的时间和空间与VE成正比且可以在常数时间内处理关于图的连通性查询。 证明。有代码可以知道每个邻接表的元素都只会被检查一次共有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.
