本文记录如何通过拓扑排序，实现循环依赖判断
前言
一般提到循环依赖，首先想到的就是Spring框架提供的Bean的循环依赖检测，相关文档可参考：
本文方案脱离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. 对象实体
1@Builder 2@NoArgsConstructor 3@AllArgsConstructor 4@Getter 5@Setter 6@ToString 7public class RelationVo implements Serializable { 8 9 /** 10 * 唯一标识 11 */ 12 private String uniqueKey; 13 14 /** 15 * 关联唯一标识集合 16 */ 17 private List combinedUniqueKeys; 18 19} 20 21
2. 对象集合转换为有向邻接矩阵图
1 /** 2 * 将List集合转换为邻接矩阵图的二维数组形式 3 * 4 * @param sourceList 5 * @return 6 */ 7 public static int[][] listToAdjacencyMatrixDiagram(List sourceList) { 8 9 List distinctRelationVoList = new ArrayList(sourceList); 10 List keyCollect = distinctRelationVoList.stream().map(RelationVo::getUniqueKey).collect(Collectors.toList()); 11 12 for (RelationVo vo : sourceList) { 13 vo.getCombinedUniqueKeys().forEach(child -> { 14 if (!keyCollect.contains(child)) { 15 // 若叶子节点不在集合中,补充List集合中单独叶子节点,目的是完成提供邻接矩阵图计算的入参 16 keyCollect.add(child); 17 RelationVo build = RelationVo.builder().uniqueKey(child).build(); 18 distinctRelationVoList.add(build); 19 } 20 }); 21 } 22 23 // 顶点数:对象中出现的全部元素总数 24 int vertexNum = keyCollect.size(); 25 /* 26 * 初始化邻接矩阵图的边的二维数组,1表示有边 0表示无边 权重均为1 27 * 其中数组下标为边的两个顶点,数组值为对象边的权值(权值=是否有边*权重) 28 */ 29 int[][] edges = new int[vertexNum][vertexNum]; 30 31 // 计算邻接矩阵图 32 for (int i = 0; i < vertexNum; i++) { 33 RelationVo colVo = distinctRelationVoList.get(i); 34 List colUniqueKeys = colVo.getCombinedUniqueKeys(); 35 for (int j = 0; j < vertexNum; j++) { 36 RelationVo rowVo = distinctRelationVoList.get(j); 37 String rowVertex = rowVo.getUniqueKey(); 38 if (CollUtil.isNotEmpty(colUniqueKeys)) { 39 if (colUniqueKeys.contains(rowVertex)) { 40 edges[i][j] = 1; 41 } else { 42 edges[i][j] = 0; 43 } 44 } 45 } 46 } 47 return edges; 48 } 49 50
3. 计算邻接矩阵图顶点的入度
1 /** 2 * 返回给出图每个顶点的入度值 3 * 4 * @param adjMatrix 给出图的邻接矩阵值 5 * @return 6 */ 7 public static int[] getSource(int[][] adjMatrix) { 8 int len = adjMatrix[0].length; 9 int[] source = new int[len]; 10 for (int i = 0; i < len; i++) { 11 // 若邻接矩阵中第i列含有m个1，则在该列的节点就包含m个入度，即source[i] = m 12 int count = 0; 13 for (int j = 0; j < len; j++) { 14 if (adjMatrix[j][i] == 1) { 15 count++; 16 } 17 } 18 source[i] = count; 19 } 20 return source; 21 } 22 23
4. 对邻接矩阵图进行拓扑排序
1 /** 2 * 拓扑排序,返回给出图的拓扑排序序列 3 * 拓扑排序基本思想： 4 * 方法1：基于减治法：寻找图中入度为0的顶点作为即将遍历的顶点，遍历完后，将此顶点从图中删除 5 * 若结果集长度等于图的顶点数,说明无环;若小于图的顶点数,说明存在环 6 * 7 * @param adjMatrix 给出图的邻接矩阵值 8 * @param source 给出图的每个顶点的入度值 9 * @return 10 */ 11 public static List topologySort(int[][] adjMatrix, int[] source) { 12 // 给出图的顶点个数 13 int len = source.length; 14 // 定义最终返回路径字符数组 15 List result = new ArrayList(len); 16 17 // 获取入度为0的顶点下标 18 int vertexFound = findInDegreeZero(source); 19 20 while (vertexFound != -1) { 21 result.add(vertexFound); 22 // 代表第i个顶点已被遍历 23 source[vertexFound] = -1; 24 for (int j = 0; j < adjMatrix[0].length; j++) { 25 if (adjMatrix[vertexFound][j] == 1) { 26 // 第j个顶点的入度减1 27 source[j] -= 1; 28 } 29 } 30 vertexFound = findInDegreeZero(source); 31 32 } 33 //输出拓扑排序的结果 34 return result; 35 36 } 37 38 /** 39 * 找到入度为0的点,如果存在入度为0的点，则返回这个点；如果不存在，则返回-1 40 * 41 * @param source 给出图的每个顶点的入度值 42 * @return 43 */ 44 public static int findInDegreeZero(int[] source) { 45 for (int i = 0; i < source.length; i++) { 46 if (source[i] == 0) { 47 return i; 48 } 49 } 50 return -1; 51 } 52 53
5. 检查集合是否存在循环依赖
1 /** 2 * 检查集合是否存在循环依赖 3 * 4 * @param itemList 5 */ 6 public static void checkCircularDependency(List itemList) throws Exception { 7 if (CollUtil.isEmpty(itemList)) { 8 return; 9 } 10 // 计算邻接矩阵图的二维数组 11 int[][] edges = listToAdjacencyMatrixDiagram(itemList); 12 // 计算邻接矩阵图每个顶点的入度值 13 int[] source = getSource(edges); 14 // 拓扑排序得到拓扑序列 15 List topologySort = topologySort(edges, source); 16 if (source.length == topologySort.size()) { 17 // 无循环依赖 18 return; 19 } else { 20 // 序列集合与顶点集合大小不一致,存在循环依赖 21 throw new Exception("当前险种关系信息存在循环依赖,请检查"); 22 } 23 } 24 25
单测用例
1. 测试物料-无循环依赖
1示例JSON Array结构(可完成拓扑排序): 2[{ 3 "uniqueKey":"A", 4 "combinedUniqueKeys":[ 5 "C", 6 "D", 7 "E" 8 ] 9}, 10{ 11 "uniqueKey":"B", 12 "combinedUniqueKeys":[ 13 "D", 14 "E" 15 ] 16}, 17{ 18 "uniqueKey":"D", 19 "combinedUniqueKeys":[ 20 "C" 21 ] 22} 23] 24 25 26
2. 测试物料-存在循环依赖
1示例JSON Array结构(不可完成拓扑排序): 2[{ 3 "uniqueKey":"A", 4 "combinedUniqueKeys":[ 5 "C", 6 "D", 7 "E" 8 ] 9}, 10{ 11 "uniqueKey":"B", 12 "combinedUniqueKeys":[ 13 "D", 14 "E" 15 ] 16}, 17{ 18 "uniqueKey":"D", 19 "combinedUniqueKeys":[ 20 "C" 21 ] 22}, 23{ 24 "uniqueKey":"C", 25 "combinedUniqueKeys":[ 26 "B" 27 ] 28} 29] 30
3. 单测示例
1@Slf4j 2public class CircularDependencyTest { 3 /** 4 * 针对集合信息判断该集合是否存在循环依赖 5 */ 6 @Test 7 void testCircularDependencyList() throws Exception { 8 String paramInfo = "[{\"uniqueKey\":\"A\",\"combinedUniqueKeys\":[\"C\",\"D\",\"E\"]},{\"uniqueKey\":\"B\",\"combinedUniqueKeys\":[\"D\",\"E\"]},{\"uniqueKey\":\"D\",\"combinedUniqueKeys\":[\"C\"]}]"; 9 // 序列化 10 List list = JSONArray.parseArray(paramInfo, RelationVo.class); 11 TopologicalSortingUtil.checkCircularDependency(list); 12 } 13} 14 15
作者：京东保险 侯亚东
来源：京东云开发者社区 转载请注明来源