网站展示型推广,如何建设公司网站 需要注意什么,凡科送审平台登录入口,阿里云域名注册邮箱本文记录如何通过拓扑排序#xff0c;实现循环依赖判断
前言
一般提到循环依赖#xff0c;首先想到的就是Spring框架提供的Bean的循环依赖检测#xff0c;相关文档可参考#xff1a; https://blog.csdn.net/cristianoxm/article/details/113246104 本文方案脱离Spring Be…本文记录如何通过拓扑排序实现循环依赖判断
前言
一般提到循环依赖首先想到的就是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创建需要BB创建需要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] mint 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个顶点的入度减1source[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 {/*** 针对集合信息判断该集合是否存在循环依赖*/Testvoid 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);}
} 作者京东保险 侯亚东 来源京东云开发者社区 转载请注明来源
