拓扑排序实现循环依赖判断 | 京东云技术团队

京东云开发者
• 阅读 239

本文记录如何通过拓扑排序,实现循环依赖判断

前言

一般提到循环依赖,首先想到的就是Spring框架提供的Bean的循环依赖检测,相关文档可参考:

https://blog.csdn.net/cristianoxm/article/details/113246104

本文方案脱离Spring Bean的管理,通过算法实现的方式,完成对象循环依赖的判断,涉及的知识点包括:邻接矩阵图、拓扑排序、循环依赖。本文会着重讲解技术实现,具体算法原理不再复述

概念释义

1. 什么是邻接矩阵?

这里要总结的邻接矩阵是关于图的邻接矩阵;图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图;一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息;

图分为有向图和无向图,其对应的邻接矩阵也不相同,无向图的邻接矩阵是一个对称矩阵,就是一个对称的二位数组,a[i][j] = a[j][i]; 邻接矩阵可以清楚的知道图的任意两个顶点是否有边;方便计算任意顶点的度(包括有向图的出度和入度);可以直观的看出任意顶点的邻接点;

本案例中,有向邻接矩阵图为进行拓扑排序的必要条件之一,其次为有向邻接矩阵图每个顶点的入度

2. 邻接矩阵的存储结构?

vexs[MAXVEX]这是顶点表;

arc[MAXVEX][MAXVEX]这是邻接矩阵图,也是存储每条边信息的二维数组。数组的索引是边的两个顶点,数组的数据是边的权值;

numVertexes, numEdges分别为图的顶点数和边数。

3. 有向邻接矩阵图顶点的入度?

在有向图中,箭头是具有方向的,从一个顶点指向另一个顶点,这样一来,每个顶点被指向的箭头个数,就是它的入度。从这个顶点指出去的箭头个数,就是它的出度

邻接矩阵的行号即代表箭头的出发结点,列号是箭头的指向结点,所以矩阵中同一行为1的表示有从第i个结点指向第j个结点这样一条边,而在同列为1就代表第j个结点被第i个结点指向,因此要求顶点的入度或出度,只需要判断同列为1的个数或同行为1的个数

4. 什么是拓扑排序?

拓扑排序的要素:
1.有向无环图;
2.序列里的每一个点只能出现一次;
3.任何一对 u 和 v ,u 总在 v 之前(这里的两个字母分别表示的是一条线段的两个端点,u 表示起点,v 表示终点);

根据拓扑排序的要素,可通过其有向无环来判断对象依赖是否存在循环。若对象组成的图可完成拓扑排序,则该对象图不存在环,即对象间不存在循环依赖。

拓扑排序除了通过有向邻接矩阵图实现外,还可以通过深度优先搜索(DFS)来实现。本案例中仅讲解前者。

5. 什么是循环依赖?

简单解释如下,若存在两个对象,若A创建需要B,B创建需要A,这两个对象间互相依赖,就构成了最简单的循环依赖关系。

编程示例

1. 对象实体

@Builder
@NoArgsConstructor
@AllArgsConstructor
@Getter
@Setter
@ToString
public class RelationVo implements Serializable {

    /**
     * 唯一标识
     */
    private String uniqueKey;

    /**
     * 关联唯一标识集合
     */
    private List combinedUniqueKeys;

}

2. 对象集合转换为有向邻接矩阵图

    /**
     * 将List集合转换为邻接矩阵图的二维数组形式
     *
     * @param sourceList
     * @return
     */
    public static int[][] listToAdjacencyMatrixDiagram(List sourceList) {

        List distinctRelationVoList = new ArrayList(sourceList);
        List keyCollect = distinctRelationVoList.stream().map(RelationVo::getUniqueKey).collect(Collectors.toList());

        for (RelationVo vo : sourceList) {
            vo.getCombinedUniqueKeys().forEach(child -> {
                if (!keyCollect.contains(child)) {
                    // 若叶子节点不在集合中,补充List集合中单独叶子节点,目的是完成提供邻接矩阵图计算的入参
                    keyCollect.add(child);
                    RelationVo build = RelationVo.builder().uniqueKey(child).build();
                    distinctRelationVoList.add(build);
                }
            });
        }

        // 顶点数:对象中出现的全部元素总数
        int vertexNum = keyCollect.size();
        /*
         * 初始化邻接矩阵图的边的二维数组,1表示有边 0表示无边 权重均为1
         * 其中数组下标为边的两个顶点,数组值为对象边的权值(权值=是否有边*权重)
         */
        int[][] edges = new int[vertexNum][vertexNum];

        // 计算邻接矩阵图
        for (int i = 0; i < vertexNum; i++) {
            RelationVo colVo = distinctRelationVoList.get(i);
            List colUniqueKeys = colVo.getCombinedUniqueKeys();
            for (int j = 0; j < vertexNum; j++) {
                RelationVo rowVo = distinctRelationVoList.get(j);
                String rowVertex = rowVo.getUniqueKey();
                if (CollUtil.isNotEmpty(colUniqueKeys)) {
                    if (colUniqueKeys.contains(rowVertex)) {
                        edges[i][j] = 1;
                    } else {
                        edges[i][j] = 0;
                    }
                }
            }
        }
        return edges;
    }

3. 计算邻接矩阵图顶点的入度

     /**
     * 返回给出图每个顶点的入度值
     *
     * @param adjMatrix 给出图的邻接矩阵值
     * @return
     */
    public static int[] getSource(int[][] adjMatrix) {
        int len = adjMatrix[0].length;
        int[] source = new int[len];
        for (int i = 0; i < len; i++) {
            // 若邻接矩阵中第i列含有m个1,则在该列的节点就包含m个入度,即source[i] = m
            int count = 0;
            for (int j = 0; j < len; j++) {
                if (adjMatrix[j][i] == 1) {
                    count++;
                }
            }
            source[i] = count;
        }
        return source;
    }

4. 对邻接矩阵图进行拓扑排序

    /**
     * 拓扑排序,返回给出图的拓扑排序序列
     * 拓扑排序基本思想:
     * 方法1:基于减治法:寻找图中入度为0的顶点作为即将遍历的顶点,遍历完后,将此顶点从图中删除
     * 若结果集长度等于图的顶点数,说明无环;若小于图的顶点数,说明存在环
     *
     * @param adjMatrix 给出图的邻接矩阵值
     * @param source    给出图的每个顶点的入度值
     * @return
     */
    public static List topologySort(int[][] adjMatrix, int[] source) {
        // 给出图的顶点个数
        int len = source.length;
        // 定义最终返回路径字符数组
        List result = new ArrayList(len);

        // 获取入度为0的顶点下标
        int vertexFound = findInDegreeZero(source);

        while (vertexFound != -1) {
            result.add(vertexFound);
            // 代表第i个顶点已被遍历
            source[vertexFound] = -1;
            for (int j = 0; j < adjMatrix[0].length; j++) {
                if (adjMatrix[vertexFound][j] == 1) {
                    // 第j个顶点的入度减1
                    source[j] -= 1;
                }
            }
            vertexFound = findInDegreeZero(source);

        }
        //输出拓扑排序的结果
        return result;

    }

    /**
     * 找到入度为0的点,如果存在入度为0的点,则返回这个点;如果不存在,则返回-1
     *
     * @param source 给出图的每个顶点的入度值
     * @return
     */
    public static int findInDegreeZero(int[] source) {
        for (int i = 0; i < source.length; i++) {
            if (source[i] == 0) {
                return i;
            }
        }
        return -1;
    }

5. 检查集合是否存在循环依赖

    /**
     * 检查集合是否存在循环依赖
     *
     * @param itemList
     */
    public static void checkCircularDependency(List itemList) throws Exception {
        if (CollUtil.isEmpty(itemList)) {
            return;
        }
        // 计算邻接矩阵图的二维数组
        int[][] edges = listToAdjacencyMatrixDiagram(itemList);
        // 计算邻接矩阵图每个顶点的入度值
        int[] source = getSource(edges);
        // 拓扑排序得到拓扑序列
        List topologySort = topologySort(edges, source);
        if (source.length == topologySort.size()) {
            // 无循环依赖
            return;
        } else {
            // 序列集合与顶点集合大小不一致,存在循环依赖
            throw new Exception("当前险种关系信息存在循环依赖,请检查");
        }
    }

单测用例

1. 测试物料-无循环依赖

示例JSON Array结构(可完成拓扑排序):
[{
    "uniqueKey":"A",
    "combinedUniqueKeys":[
        "C",
        "D",
        "E"
    ]
},
{
    "uniqueKey":"B",
    "combinedUniqueKeys":[
        "D",
        "E"
    ]
},
{
    "uniqueKey":"D",
    "combinedUniqueKeys":[
        "C"
    ]
}
]


2. 测试物料-存在循环依赖

示例JSON Array结构(不可完成拓扑排序):
[{
    "uniqueKey":"A",
    "combinedUniqueKeys":[
        "C",
        "D",
        "E"
    ]
},
{
    "uniqueKey":"B",
    "combinedUniqueKeys":[
        "D",
        "E"
    ]
},
{
    "uniqueKey":"D",
    "combinedUniqueKeys":[
        "C"
    ]
},
{
    "uniqueKey":"C",
    "combinedUniqueKeys":[
        "B"
    ]
}
]

3. 单测示例

@Slf4j
public class CircularDependencyTest {
    /**
     * 针对集合信息判断该集合是否存在循环依赖
     */
    @Test
    void testCircularDependencyList() throws Exception {
        String paramInfo = "[{\"uniqueKey\":\"A\",\"combinedUniqueKeys\":[\"C\",\"D\",\"E\"]},{\"uniqueKey\":\"B\",\"combinedUniqueKeys\":[\"D\",\"E\"]},{\"uniqueKey\":\"D\",\"combinedUniqueKeys\":[\"C\"]}]";
        // 序列化
        List list = JSONArray.parseArray(paramInfo, RelationVo.class);
        TopologicalSortingUtil.checkCircularDependency(list);
    }
}

作者:京东保险 侯亚东

来源:京东云开发者社区 转载请注明来源

点赞
收藏
评论区
推荐文章
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
CuterCorley CuterCorley
3年前
C语言基础习题50例(八)36-40
习题36求100之内的素数。实现思路:使用函数实现,并循环遍历依次判断。代码如下:cinclude<stdio.hinclude<math.hintmain(){intisPrime(intn);inti,count0;for(i2;i<101;i){if(isPrime(i)){
0源码基础学习Spring源码系列(二)——Spring如何解决循环依赖
本篇文章适用于0基础学习spring源码,文章重点解析spring如何解决循环依赖,并从解决循环依赖过程、三级缓存在循环依赖中的作用、解决代理对象的问题、二级缓存、初始化几个维度出发,解析spring源码。
Easter79 Easter79
2年前
Spring是如何解决循环依赖的
​在某一次面试中,对方问了一个问题:Spring的Bean如果互相依赖,会发生什么?由于我那段时间正好遇到了一个Spring循环依赖报错的问题,就回答会报错。然后听对方口气,感觉自己答错了。于是事后了解了一下,才发现其实Spring自身解决了循环依赖的问题。​Spring的启动后,会读取配置文件,资源文件读取校验,创建BeanFacto
Easter79 Easter79
2年前
Spring循环依赖问题的解决
循环依赖问题一个bean的创建分为如下步骤:!(https://static.oschina.net/uploads/img/202102/24030007_IrhH.png)当创建一个简单对象的时候,过程如下:先从单例池中获取bean,发现无a创建a的实例为a赋值把a放到单例池
Stella981 Stella981
2年前
Spring core 源码分析
    上节提到了在AbstractApplicationContext调用refresh方法里,初始化所有BeanDefinitions后,遍历所有BeanDefinitionNames后,循环调用BeanFactory的getBean(name)方法,实例化所有容器Bean对象(非lasyinit)。GetBean做了什么?循环引用如何处理
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Easter79 Easter79
2年前
Spring如何解决循环依赖的问题
        在关于Spring的面试中,我们经常会被问到一个问题,就是Spring是如何解决循环依赖的问题的。这个问题算是关于Spring的一个高频面试题,因为如果不刻意研读,相信即使读过源码,面试者也不一定能够一下子思考出个中奥秘。本文主要针对这个问题,从源码的角度对其实现原理进行讲解。1\.过程演示        关于Spring
从源码层面深度剖析Spring循环依赖 | 京东云技术团队
本文从源码层面介绍了Spring如何创建bean、如何解决循环依赖,同时也介绍了不能解决哪些循环依赖,同时在文章的最后解决循环依赖报错的几个方法