无向图的处理算法（四）连通分量

asce1885 发布于2019-08-14 12:10 / 3475人阅读

这篇讲的是连通分量，连通分量是深度优先搜索算法的一个应用。
每进行了一次dfs，就会找到一条连通分量。
定义如下的API

public class CC
    CC(Graph g)      预处理构造函数
    boolean connected(int v,in w)  v和w连通吗
    int count()     改图中的连通分量个数
    int id(int v)   顶点v所在的连通分量编号

具体实现如下：

package Graph;

public class CC {
    /*
     * 计算一个图中的连通分量，从起始点开始进行dfs算法，同时用一个以顶点作为索引的数组id[]来保存该点所在的连通分量的起始点，也就是id
     * 这样，判断两个点是否处于同一个连通分量，只要判断id是否相同
     */
    private boolean[] marked;
    private int[] id;
    private int count;

    public CC(Graph G){
        marked = new boolean[G.V()];
        id = new int[G.V()];
        for(int s = 0;s < G.V();s++){
            if(!marked[s]){
                dfs(G,s);
                count++;
            }
        }
    }
    private void dfs(Graph G,int v){
        marked[v] = true;
        id[v] = count;          //该连通分量的起始节点
        for(int w:G.adj(v)){
            if(!marked[w])
                dfs(G,w);
        }
    }

    public boolean connected(int v,int w){
        return id[v] == id[w];
    }
    public int id(int v){
        return id[v];
    }
    public int count(){
        return count;
    }
}

同样还能解决双色问题，即“能够用两种不同颜色将顶点着色，使得相邻的顶点颜色不同吗？等价于这个图是一个二分图吗？

/*
 * 使用dfs算法，来判断一个图中的顶点是否可以用两种颜色染色，使得相邻的顶点颜色不同
 * 也就是，判断该图是否是一个二分图：
 * 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
 * 
 */
public class TwoColor {
    private boolean[] marked;
    private boolean[] color;
    private boolean isTwoColorable = true;

    public TwoColor(Graph G){
        marked = new boolean[G.V()];
        color = new boolean[G.V()];
        for(int s = 0;s < G.V();s++){
            if(!marked[s])
                dfs(G,s);
        }
    }

    private void dfs(Graph G,int v){
        marked[v] = true;
        for(int w: G.adj(v)){
            if(!marked[w]){
                color[w] =!color[v];
            }
            else if (color[w] == color[v])
                isTwoColorable = false;
        }
    }
    public boolean isTwoColorable(){
        return isTwoColorable;
    }
}

GPU云服务器云服务器最大连通区域算法java 最大连通子图算法 webrtc agc算法四字符串处理算法匹配算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64338.html

算法第四版4.1-无向图详解

摘要：树是一副无环连通图。互不相连的树组成的集合称为森林。表示无向图的数据类型图的基本操作的两个构造，得到顶点数和边数，增加一条边。该方法不符合第一个条件，上百万个顶点的图是很常见的空间不满足。四种重要的图模型：无向图（简单连接）有向图（连接有方向性）加权图（连接带有权值）加权有向图（连接既有方向性又带有权值）无向图定义：由一组顶点和一组能够将两个顶点相连的边组成。特殊：...

scola666 2019-08-14 17:53 评论0 收藏0
算法（第4版） Chapter 4.1 无向图

摘要：边仅由两个顶点连接，并且没有方向的图称为无向图。用分隔符当前为空格，也可以是分号等分隔。深度优先算法最简搜索起点构造函数找到与起点连通的其他顶点。路径构造函数接收一个顶点，计算到与连通的每个顶点之间的路径。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter...

kamushin233 2019-08-14 17:14 评论0 收藏0
算法（第4版） Chapter 4.2 强联通性 Tarjan算法补充

摘要：在实际的测试中，算法的运行效率也比算法高左右。此外，该算法与求无向图的双连通分量割点桥的算法也有着很深的联系。学习该算法，也有助于深入理解求双连通分量的算法，两者可以类比组合理解。固属于同一连通分支。参考资料http://blog.csdn.net/acmmmm/a...https://www.byvoid.com/blog/s...http://blog.csdn.net/noth...

maybe_009 2019-08-14 17:13 评论0 收藏0
算法之不定期更新（三）（2018-04-24）

摘要：实现这个想法之后就发现，时间复杂度真的太高了。本期算法小分享就到这里咯刚做完探索里的初级，还有好多已经说烂了的题就不分享了。如果有什么意见或者想法欢迎在评论区和我交流题目 input: n // 代表无向图的顶点数 // 从1开始 m // 无向图的边数 arr1 // 各边的情况，形如[[1, 2], [3, 4],...]（代表顶点0和顶点2相连，顶点3和顶点4相连） ...

darryrzhong 2019-08-22 16:40 评论0 收藏0