乐趣区

关于java:图算法系列之深度优先搜索二

jiezi

吐血整顿程序员必读书单：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

实现的思路：

  1. 标记曾经搜寻过的每个顶点
  2. 当遇到了一个曾经被标记过的顶点，示意曾经图中存在环；
  3. 因为图是无向图，如果 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

最初（点关注，不迷路）

文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。

最初，写作不易，请不要白嫖我哟 ，心愿敌人们能够 点赞评论关注 三连，因为这些就是我分享的全副能源起源🙏

退出移动版