当前位置：首页 > news >正文

拓扑排序在实际开发中的应用

news 2025/8/21 19:23:23

1. 拓扑排序说明

简单解释：针对于有向无环图（DAG），给出一个可行的节点排序，使节点之间的依赖关系不冲突。

复杂解释：自行搜索相关资料。

本次应用中的解释：给出一个可行的计算顺序，使得每个字段计算时，所需的变量已经完成了计算。

2. 业务场景

在开发的报表数据管理系统中，系统的业务流程如下：

① 先从目标数据库中抓取数据值，例如目标系统为物流系统，抓取其中物流订单的相关数据，送货地区、货物体积、数量、型号等数据。

② 对数据进行一定的运算逻辑，如计算总费用= 运费+卸货费

问题难点：

系统在计算的过程中，存在多级计算，如下图中的单价、运费、卸货费、总费用都需要进行计算，如何确定每个字段的计算顺序，保证总费用在计算时，运费已经完成计算了。即系统需要将运费的计算先排在总费用的计算前面。这个时候就可以应用到拓扑排序。

如果系统不去进行这么一个排序的话，用户在添加公式的时候，需要考虑字段之间的顺序是否符合先后顺序，如果出现了计算总费用时，运费这个字段还没有计算完成的情况，系统会出现报错，用户需要对错误进行排查，导致用户使用体验非常差。

在这里插入图片描述

3. 实际应用代码

kahn算法说明：

维护一个入度为0的队列
先找到所有入度为0的点，并从图中移除，加入到入度为0的队列中，即setOfZeroIndegree
循环处理setOfZeroIndegree队列中的所有点，将点向外指出的边进行删除，A->B，A的入度为0 ，B的入度为1，删除掉A点和B点的边后，B点的入度为0，这个时候B点也可以加入setOfZeroIndegree队列中
挡setOfZeroIndegree队列为空时，判断图中是否还有边没有删除干净，如果没有删除干净，则当前图为有环图，无法得到可行解。如果删除干净了，表示给出的图是有可行解的。

拓扑排序工具类

/*** @author kstar* @date 2024/10/16* @description* 操作方法见main方法，有详细的操作流程*/import java.util.*;public class GraphUtils {// 定义点的数据结构public static class Node {public Object val;public int pathIn = 0; // 入链路数量public Node(Object val) {this.val = val;}}/*** 拓扑图类*/public static class Graph {// 图中节点的集合public Set<Node> vertexSet = new HashSet<Node>();// 相邻的节点，纪录边public Map<Node, Set<Node>> adjaNode = new HashMap<Node, Set<Node>>();// 将节点加入图中public boolean addNode(Node start, Node end) {// 判断节点集合中是否有这两个节点，没有的话就加入到节点集合if (!vertexSet.contains(start)) {vertexSet.add(start);}if (!vertexSet.contains(end)) {vertexSet.add(end);}// 如果图中已经存在该边，则不添加if (adjaNode.containsKey(start)&& adjaNode.get(start).contains(end)) {return false;}// 判断当前节点是否有边的map，有的话可以直接加入，没有的话新建一个setif (adjaNode.containsKey(start)) {adjaNode.get(start).add(end);} else {Set<Node> temp = new HashSet<Node>();temp.add(end);adjaNode.put(start, temp);}// 被指向的节点入度+1end.pathIn++;return true;}}/**Kahn算法*  0. 维护一个入度为0的队列*  1. 先找到所有入度为0的点，并从图中移除，加入到入度为0的集合中*  2. 循环处理setOfZeroIndegree集合中的所有点，*/public static class KahnTopo {private List<Node> result; // 用来存储结果集,结果数据集就是最终的排序结果private Queue<Node> setOfZeroIndegree; // 用来存储入度为0的顶点private Graph graph;//构造函数，初始化public KahnTopo(Graph di) {this.graph = di;this.result = new ArrayList<Node>();this.setOfZeroIndegree = new LinkedList<Node>();// 对入度为0的集合进行初始化for(Node iterator : this.graph.vertexSet){if(iterator.pathIn == 0){this.setOfZeroIndegree.add(iterator);}}}//拓扑排序处理过程public void process() {while (!setOfZeroIndegree.isEmpty()) {Node v = setOfZeroIndegree.poll();// 将当前顶点添加到结果集中result.add(v);if (this.graph.adjaNode.get(v)==null){this.graph.vertexSet.remove(v);continue;}if(this.graph.adjaNode.keySet().isEmpty()){return;}// 遍历由v引出的所有边for (Node w : this.graph.adjaNode.get(v) ) {// 将该边从图中移除，通过减少边的数量来表示w.pathIn--;if (0 == w.pathIn) // 如果入度为0，那么加入入度为0的集合{setOfZeroIndegree.add(w);}}this.graph.vertexSet.remove(v);this.graph.adjaNode.remove(v);}// 如果此时图中还存在边，那么说明图中含有环路if (!this.graph.vertexSet.isEmpty()) {List<String> errNode = new ArrayList<>();for (Node node : this.graph.vertexSet) {errNode.add(node.val.toString());}throw new IllegalArgumentException("当前参数存在循环依赖，请检查:"+errNode);}}//结果集public Iterable<Node> getResult() {return result;}}//测试方法public static void main(String[] args) {// 添加点Node A = new Node("A");Node B = new Node("B");Node C = new Node("C");Node D = new Node("D");Node E = new Node("E");Node F = new Node("F");// 添加边Graph graph = new Graph();graph.addNode(A, B);graph.addNode(B, C);graph.addNode(B, D);graph.addNode(D, C);graph.addNode(E, C);graph.addNode(C, F);KahnTopo topo = new KahnTopo(graph);topo.process();for(Node temp : topo.getResult()){System.out.print(temp.val.toString() + "-->");}}
}

实际应用代码

// 在实际业务场景中的应用，仅做说明演示，直接复制过去无法使用，要用的话用上面的代码的main方法即可测试
// 样例方法中，需要对CollectSchemeDetail这个类中进行排序，
// 排序时根据类中的getCollectResultCode构建图，将计算时需要的字段解析出来构建图
public void calculateOrder(String collectSchemeCode){List<CollectSchemeDetail> collectSchemeDetails = listByCode(collectSchemeCode);Map<String, GraphUtils.Node> nodeMap = new HashMap<>();// 循环遍历对象数组中的值，取出其中的点和图的关系for (CollectSchemeDetail schemeDetail : collectSchemeDetails) {GraphUtils.Node node = new GraphUtils.Node(schemeDetail.getCollectResultCode());nodeMap.put(schemeDetail.getCollectResultCode(),node);}GraphUtils.Graph graph = new GraphUtils.Graph();for (CollectSchemeDetail schemeDetail : collectSchemeDetails) {if (schemeDetail.getCollectType().equals(CollectSchemeDetail.CollectTypeEnum.EQUATION)) {if (schemeDetail.getExpression()==null||!schemeDetail.getExpression().contains("$")){throw new GlobalException("公式：["+schemeDetail.getCollectResultName()+"]中没有设置表达式，请先设置表达式后再添加");}// 公式解析，expression为公式，如A+B-C，// JEPUtils.getVariables的方法可以将公式中的有效字段解析出来List<String> variableList = JEPUtils.getVariables(schemeDetail.getExpression());for (String variable : variableList) {graph.addNode(nodeMap.get(variable), nodeMap.get(schemeDetail.getCollectResultCode()));}}}// 执行拓扑排序算法GraphUtils.KahnTopo topo = new GraphUtils.KahnTopo(graph);topo.process();Map<String,List<CollectSchemeDetail>> resultCodeSchemeDetailMap = collectSchemeDetails.stream().collect(Collectors.groupingBy(CollectSchemeDetail::getCollectResultCode));int i = 1;List<CollectSchemeDetail> needUpdateList = new ArrayList<>();// 循环拓扑排序的结果，对数据的计算顺序进行更新for(GraphUtils.Node temp : topo.getResult()){for (CollectSchemeDetail collectSchemeDetail : resultCodeSchemeDetailMap.get(temp.val.toString())) {collectSchemeDetail.setCalculateOrder(i);}needUpdateList.addAll(resultCodeSchemeDetailMap.get(temp.val.toString()));i++;}updateBatchById(needUpdateList);}