吐血整顿程序员必读书单：https://github.com/silently9527/ProgrammerBooks
微信公众号：贝塔学Java
在上篇中咱们学习了深度优先搜寻，晓得了如何通过深度优先搜寻在图中寻找门路；本篇咱们持续一起来学习深度优先搜索算法的其余利用场景
连通重量
从一幅图中找出所有的连通重量，这是也是深度优先搜寻的一个利用场景。什么是连通重量？这个定义在之前的文章中已有提到《如何检测社交网络中两个人是否是敌人关系（union-find算法）》
在这篇采纳的是union-find算法实现的连通性查看，本篇咱们将采纳深度优先搜寻的形式来找出图中的所有连通重量
连通重量的API定义
public class DepthFirstCC {
public DepthFirstCC(Graph graph);
public boolean connected(int v, int w); //查看两个顶点是否连通
public int count(); //统计连通重量的总数
public int id(int v); //顶点v所在连通重量的标识
}连通重量的API实现
与之前一样没扫描到一个顶点咱们就须要标记这个顶点，所以仍然须要定义一个marked[]数组
为了统计出图中总共有多少连通重量，所以须要定义一个变量count
为了判断两个顶点是否相连，咱们须要把相连的顶点对应的标识值记录成雷同值，当在调用connected办法的时候间接取出两个顶点的标识值比拟，如果雷同就是连通的，否则就是非连通；
这个的标识值咱们应用的是count的值，每个顶点都须要存一个标识值，所以还须要一个ids[]数组。
public class DepthFirstCC {
private boolean marked[];
private int count;
private int[] ids;
public DepthFirstCC(Graph graph) {
this.marked = new boolean[graph.V()];
this.ids = new int[graph.V()];
for (int v = 0; v < graph.V(); v++) {
if (!this.marked[v]) {
dfs(graph, v);
count++;
}
}
}
private void dfs(Graph graph, int v) {
this.marked[v] = true;
this.ids[v] = count;
for (int w : graph.adj(v)) {
if (!this.marked[w]) {
dfs(graph, w);
}
}
}
public boolean connected(int v, int w) {
return id(v) == id(w);
}
public int count() {
return count;
}
public int id(int v) {
return ids[v];
}
}单元测试
结构这样一个图，连通重量的总数应该是3
@Test
public void test() {
Graph graph = new Graph(10);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 5);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(4, 3);
graph.addEdge(5, 3);
graph.addEdge(6, 7);
graph.addEdge(8, 9);
DepthFirstCC cc = new DepthFirstCC(graph);
System.out.println(cc.connected(0,5));
System.out.println(cc.connected(1,2));
System.out.println(cc.count());
}
基于深度优先搜寻实现的连通性查看实践上说要比以前实现的union-find算法更快，因为查看连通性深度优先搜寻实现的版本可能保障在常量工夫内实现，而union-find算法不行；
然而union-find也有本人的劣势: 不须要把残缺的结构并示意一张图，更重要的是union-find算法是动静的增加节点。
查看无向图中是否有环
为了减小实现的复杂度，咱们假如图中不存在自环和平行边；
如果从顶点v登程存在环，示意从顶点v登程的连通重量中某个顶点的邻接顶点是v，那么在搜寻的过程中必定会再次遇到顶点v
实现的思路：
- 标记曾经搜寻过的每个顶点
- 当遇到了一个曾经被标记过的顶点，示意曾经图中存在环；
- 因为图是无向图，如果v-w相连，那么顶点v中的邻接表中有w，w邻接表中也会有v，然而他们没有形成环，所以须要排除掉该状况。
public class Cycle {
private boolean marked[];
private boolean hashCycle;
public Cycle(Graph graph) {
this.marked = new boolean[graph.V()];
for (int s = 0; s < graph.V(); s++) {
if (!this.marked[s]) {
dfs(graph, s, s);
}
}
}
private void dfs(Graph graph, int v, int pV) {
this.marked[v] = true;
for (int w : graph.adj(v)) {
if (!this.marked[w]) {
this.dfs(graph, w, v);
} else if (w != pV) {
this.hashCycle = true;
return;
}
}
}
public boolean hasCycle() {
return hashCycle;
}
}办法dfs的参数v示意须要待搜寻的顶点，pV示意的是达到v的顶点，所以如果v的邻接表中有个顶点已被标记过并且该顶点不等于达到v的顶点，那么示意图中有环
查看无向图是否是二分图
何为二分图? 图中每条边所连贯的顶点都属于不同的局部；如下图：
其中红色节点示意一个汇合，红色节点是另一个汇合，每条边连贯的两个顶点属于不同的汇合；
举个理论的例子就很好了解，电影与演员的关系，电影作为一个顶点，演员作为一个顶点，电影与电影间接是不会有边，演员与演员间接也不会有边，这就是一张二分图。
public class TwoColorGraph {
private boolean twoColor = true;
private boolean[] marked;
private boolean[] color;
public TwoColorGraph(Graph graph) {
this.marked = new boolean[graph.V()];
this.color = new boolean[graph.V()];
for (int v = 0; v < graph.V(); v++) {
if (!this.marked[v]) {
dfs(graph, v);
}
}
}
private void dfs(Graph graph, int v) {
this.marked[v] = true;
for (int w : graph.adj(v)) {
if (!this.marked[w]) {
this.color[w] = !this.color[v];
dfs(graph, w);
} else if (this.color[w] == this.color[v]) {
this.twoColor = false;
return;
}
}
}
public boolean isTwoColor() {
return twoColor;
}
}文中所有源码已放入到了github仓库:
https://github.com/silently9527/JavaCore
最初（点关注，不迷路）
文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。
最初，写作不易，请不要白嫖我哟，心愿敌人们能够点赞评论关注三连，因为这些就是我分享的全副能源起源🙏
发表回复