拓扑排序实现循环依赖判断 | 京东云技术团队
本文记录如何通过拓扑排序，实现循环依赖判断
前言
一般提到循环依赖，首先想到的就是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);
}
}
作者：京东保险 侯亚东
来源：京东云开发者社区 转载请注明来源
关注公众号
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有，本站原创内容转载请注明来源。
-
上一篇
机器学习 - 决策树：技术全解与案例实战
本文深入探讨了机器学习中的决策树算法，从基础概念到高级研究进展，再到实战案例应用，全面解析了决策树的理论及其在现实世界问题中的实际效能。通过技术细节和案例实践，揭示了决策树在提供可解释预测中的独特价值。 关注TechLead，分享AI全维度知识。作者拥有10+年互联网服务架构、AI产品研发经验、团队管理经验，同济本复旦硕，复旦机器人智能实验室成员，阿里云认证的资深架构师，项目管理专业人士，上亿营收AI产品研发负责人。 一、引言 决策树算法是机器学习领域的基石之一，其强大的数据分割能力让它在各种预测和分类问题中扮演着重要的角色。从它的名字便能窥见其工作原理的直观性：就像一棵树一样，从根到叶子的每一分叉都是一个决策节点，指引数据点最终归类到相应的叶节点，或者说是最终的决策结果。 在现实世界中，决策树的概念可以追溯到简单而普遍的决策过程。例如，医生在诊断病人时，会根据一系列的检查结果来逐步缩小疾病的范围，这个过程可以被视作一种决策树的实际应用。从症状到测试，每一个节点都是决策点，携带着是否进一步检查或是得出诊断的决策。 在机器学习的世界里，这种决策过程被数学化和算法化。我们不再是用肉眼观察，...
-
下一篇
Nacos 配置中心源码 | 京东物流技术团队
客户端 入口 在引入配置中心 maven 依赖的 jar 文件中找到 spring-cloud-starter-alibaba-nacos-config-2.2.5.RELEASE.jar!/META-INF/spring.factories，在该配置文件找到 NacosConfigBootstrapConfiguration 配置类，该类是 nacos 配置中心的入口类，类中注册了三个 bean。 NacosConfigProperties：属性配置类，对应配置文件中 spring.cloud.nacos.config 前缀的属性。 NacosConfigManager：管理 NacosConfigProperties 和 ConfigService。 NacosPropertySourceLocator：加载配置中心配置信息。 NacosConfigManager 在 NacosConfigManager 构造方法中，调用了 createConfigService 方法，该方法通过工厂类调用 ConfigService 实现类的构造方法创建 ConfigService ...
相关文章
文章评论
共有0条评论来说两句吧...
微信收款码
支付宝收款码