您好!
欢迎来到京东云开发者社区
登录
首页
博文
课程
大赛
工具
用户中心
开源
首页
博文
课程
大赛
工具
开源
更多
用户中心
开发者社区
>
博文
>
拓扑排序实现循环依赖判断
分享
打开微信扫码分享
点击前往QQ分享
点击前往微博分享
点击复制链接
拓扑排序实现循环依赖判断
st****
2023-12-04
IP归属:北京
164浏览
本文记录如何通过拓扑排序,实现循环依赖判断 <!--more--> --- ### 前言 一般提到循环依赖,首先想到的就是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<String> combinedUniqueKeys; } ``` #### 2. 对象集合转换为有向邻接矩阵图 ``` /** * 将List集合转换为邻接矩阵图的二维数组形式 * * @param sourceList * @return */ public static int[][] listToAdjacencyMatrixDiagram(List<RelationVo> sourceList) { List<RelationVo> distinctRelationVoList = new ArrayList(sourceList); List<String> 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<String> 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<Integer> topologySort(int[][] adjMatrix, int[] source) { // 给出图的顶点个数 int len = source.length; // 定义最终返回路径字符数组 List<Integer> 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<RelationVo> 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<RelationVo> list = JSONArray.parseArray(paramInfo, RelationVo.class); TopologicalSortingUtil.checkCircularDependency(list); } } ```
上一篇:浅谈SQL优化小技巧
下一篇:Pipeline模式应用
st****
文章数
2
阅读量
152
作者其他文章
01
Pipeline模式应用
本文记录Pipeline设计模式在业务流程编排中的应用前言Pipeline模式意为管道模式,又称为流水线模式。旨在通过预先设定好的一系列阶段来处理输入的数据,每个阶段的输出即是下一阶段的输入。本案例通过定义PipelineProduct(管道产品),PipelineJob(管道任务),PipelineNode(管道节点),完成一整条流水线的组装,并将“原材料”加工为“商品”。其中管道产品负责承载各
01
拓扑排序实现循环依赖判断
本文记录如何通过拓扑排序,实现循环依赖判断前言一般提到循环依赖,首先想到的就是Spring框架提供的Bean的循环依赖检测,相关文档可参考:https://blog.csdn.net/cristianoxm/article/details/113246104本文方案脱离Spring Bean的管理,通过算法实现的方式,完成对象循环依赖的判断,涉及的知识点包括:邻接矩阵图、拓扑排序、循环依赖。本文会
st****
文章数
2
阅读量
152
作者其他文章
01
Pipeline模式应用
添加企业微信
获取1V1专业服务
扫码关注
京东云开发者公众号