前言最近公司项目有个需求，挺有价值的分享一下。让我在这里记录一下。要求大致如下。在下面的流程图中，点击条件线上选中的内容。必须是之前配置的节点。如果没有，需要在保存时做强验证提示。这个要求其实很明确。抽象就是得到图中两个顶点之间所有可达路径的顶点集合。你能想想怎么实现吗？这涉及到数据结构中图相关的知识，数据结构算法也是我能力的最大弱点，还是浪费了我的时间。抽象数据模型其实看到这个需求很容易想到我们的有向图，那么在java中应该用什么样的数据结构来表示有向图呢？在补充了一些图相关的知识后，最终还是决定使用“邻接表”的方式来实现。邻接表是图最重要的存储结构，用来描述图上的每个点。我们假设如下有向图：那么可以抽象出如下数据结构：不知大家有没有发现这个规律，每个顶点都与它所关联的其他顶点关联，比如A关联B、C、D通过edges，可以理解为A有3条边，它们的目标顶点分别是B、C、D，那么java中怎么表达呢？代码实现数据模型1.VertexclassVertex/***vertex*/@Data@AllArgsConstructor@Accessors(chain=true)@NoArgsConstructorclassVertex{/***vertexid*/privateStringid;/***顶点名称*/privateStringname;/***顶点发出的边信息*/privateListedges=newArrayList<>();}成员变量edges表示与该顶点关联的所有边。2.顶点关联的边类Edge/***Edge*/@Data@AllArgsConstructor@Accessors(chain=true)@NoArgsConstructorclassEdge{/***边的目标id*/privateStringtargetVertexId;/***边缘ID*/privateStringid;/***边的名称*/privateStringname;}成员变量targetVertexId用于存储边的目标顶点id3.创建有向图DirectedDiagraph/***有向图**@authoralvin*@date2022/10/26*@since1.0**/@Data@Slf4j(topic="a.DirectedDiagraph")publicclassDirectedDiagraph{/***有向图的顶点信息*/privateMapvertexMap=newHashMap<>();/***边数*/privateintedgeNum;/***添加顶点信息**@paramvertexId顶点id*@paramvertexName顶点名称*/publicvoidaddVertex(StringvertexId,StringvertexName){if(StrUtil.isEmpty(vertexId)){thrownewRuntimeException("Thevertexid不能为空");}顶点节点=newVertex().setId(vertexId).setName(vertexName);//添加到有向图vertextMap.put(vertexId,node);}/***添加边信息**@paramfromVertexId边起始节点*@paramtargetVertexId边目标节点*@paramedgeId边id*@paramedgeName边名*/publicvoidaddEdge(StringfromVertexId,StringtargetVertexId,StringedgeId,StringedgeName){if(StrUtil.isEmpty(fromVertexId)||StrUtil.isEmpty(targetVertexId)){thrownewRuntimeException("边的起始顶点或目标顶点不能为空");}边edge=newEdge().setTargetVertexId(targetVertexId).setId(edgeId).setName(edgeName);//获取顶点fromVertex=vertextMap.get(fromVertexId);//添加到边fromVertex.getEdges().add(edge);//边数+1edgeNum++;}/***添加边信息*@paramfromVertexId边的起始节点*@paramtargetVertexId边的目标节点*/publicvoidaddEdge(StringfromVertexId,StringtargetVertexId){this.addEdge(fromVertexId,targetVertexId,null，无效的）;}/***获取图中的边数量*/publicintgetEdgeNum(){returnedgeNum;}}成员变量vertextMap存储图中的顶点信息addVertex()方法用于添加顶点数据addEdge()方法用于添加边数据计算两个顶点之间的路径算法根据前言的要求，当前数据图的模型已经创建。现在需要实现计算两个顶点之间可达路径的所有顶点集。直接上传代码。由于使用的参数比较多，这里封装一个算法。类CalcTwoVertexPathlgorithmcalcPaths()方法是算法的核心入口成员变量allPathList，存储所有可达路径列表。printAllPaths()方法打印所有路径。getAllVertexs()返回所有可达顶点的集合。/***计算两个顶点之间路径的算法*/@Slf4j(topic="a.CalcTwoVertexPathlgorithm")classCalcTwoVertexPathlgorithm{/***起始顶点*/privateStringfromVertexId;/***查询的目标顶点*/privateStringtoVertextId;/***当前图*/privateDirectedDiagraphdirectedDiagraph;/***所有路径*/privatefinalList>allPathList=newArrayList<>();publicCalcTwoVertexPathlgorithm(DirectedDiagraphdirectedDiagraph,StringfromVertexId,StringtoVertextId){this.fromVertexId=fromVertexId;this.toVertextId=toVertextId;this.directedDiagraph=directedDiagraph;}/***打印所有路径*/publicvoidprintAllPaths(){log.info("{}和{}之间的路径:",fromVertexId,toVertextId);allPathList.forEach(item->{log.info("{}",item);});}/***获取两点之间所有可能的顶点数据*@return*/publicSetgetAllVertexs(){returnallPathList.stream().flatMap(Collection::stream).collect(Collectors.toSet());}publicvoidcalcPaths(){//先清理上次调用留下的数根据allPathList.clear();DirectedDiagraph.VertexfromNode=directedDiagraph.getVertextMap().get(fromVertexId);DirectedDiagraph.VertextoNode=directedDiagraph.getVertextMap().get(toVertextId);//找不到边if(fromNode==null||toNode==null){thrownewRuntimeException("Thevertexiddoesnotexist");}//如果实际节点等于目标节点，也认为是一条边if(fromNode==toNode){Listpaths=newArrayList<>();paths.add(fromVertexId);allPathList.add（路径）；返回;}//递归调用coreRecGetAllPaths(fromNode,toNode,newArrayDeque<>());}privatevoidcoreRecGetAllPaths(DirectedDiagraph.VertexfromVertex,DirectedDiagraph.VertextoVertex,DequenowPaths){//检查是否存在循环，跳过if(nowPaths.contains(fromVertex.getId())){System.out.println("有一个循环");//弹出nowPaths.pop();返回;}//当前路径加上实际节点nowPaths.push(fromVertex.getId());//深度搜索边缘（DirectedDiagraph.Edgeedge:fromVertex.getEdges()){//如果边的目标顶点与路径的最终节点一致，则表示查找成功if(StrUtil.equals(edge.getTargetVertexId(),toVertex.getId())){//向当前路径添加数据nowPaths.push(toVertex.getId());//复制一份数据到allPathListListfindPaths=newArrayList<>();findPaths.addAll(nowPaths);CollUtil.reverse(findPaths);allPathList.add（查找路径）；//添加最后一个节点，返回一次nowPaths.pop();//跳过，查询下一条边继续；}//以边的目标顶点作为实际顶点，继续搜索DirectedDiagraph.VertexnextFromVertex=directedDiagraph.getVertextMap().get(edge.getTargetVertexId());if(nextFromVertex==null){thrownewRuntimeException("顶点id不存在");}//下次递归调用coreRecGetAllPaths(nextFromVertex,toVertex,nowPaths);}//完了，没找到，弹出数据nowPaths.pop();}代码注释的比较清楚，就不多介绍了，主要是使用深度搜索的方式+栈存储临时路径然后在DirectedDiagraph类中添加一个方法findAllPaths()来查找所有路径，如下图所示：@Data@Slf4j(topic="a.DirectedDiagraph")publicclassDirectedDiagraph{...../***获取两个顶点之间所有可能的数据**@paramfromVertexId起始顶点*@paramtargetVertexId目标顶点*@return*/publicSetfindAllPaths(StringfromVertexId,StringtargetVertexId){;//首先计算calcTwoVertexPathlgorithm.calcPaths();//打印找到的路径calcTwoVertexPathlgorithm.printAllPaths();//然后返回所有内容returncalcTwoVertexPathlgorithm.getAllVertexs();}....}最后，我们用单元测试来写Verifyit。@Testpublicvoidtest1(){DirectedDiagraphdirectedDiagraph=newDirectedDiagraph();directedDiagraph.addVertex("A","A");directedDiagraph.addVertex("B","B");directedDiagraph.addVertex("C","C");directedDiagraph.addVertex("D","D");directedDiagraph.addVertex("E","E");directedDiagraph.addEdge("A","B");directedDiagraph.addEdge("B","C");directedDiagraph.addEdge("C","D");directedDiagraph.addEdge("A","D");directedDiagraph.addEdge("B","D");directedDiagraph.addEdge("A","C");directedDiagraph.addEdge("D","E");SetallPaths=directedDiagraph.findAllPaths("A","D");log.info("allvertexIds:{}",allPaths);}创建的例子也是我们之前图片中的例子，看看运行结果是否符合预期。综上所述，本次请求使用图数据结构获取结果。突然觉得数据结构和算法真的很重要。感觉目前的做法不是最优方案，性能应该也不是最好的，但是考虑到流程节点数据不会很多，应该可以满足业务需求。不知道大家有没有更好的办法？
