计算图中两个顶点的所有路径，你会吗？

最近公司的项目上有个需求，还挺有分享价值的，这边做个记录。需求大致如下，下面的一个流程图，点击条件线上选择的内容，必须是前面配置过的节点，如果不是，需要在保存的时候做强校验提示。,,需求其实很明确，抽象出来就是获取图中两个顶点之间所有可达路径的顶点集合，大家可以思考下，该如何实现？这里面涉及到了数据结构中图相关知识，而数据结构算法也是本事最大的弱项，还是废了我一番工夫。,实际上，看到这个需求就很容易想到我们的有向图，那么在java中该用怎么样的数据结构表示有向图呢？在恶补了一番图相关的知识以后，最终确定用”邻接表”的方式实现。邻接表是图的一种最主要存储结构,用来描述图上的每一个点。,我们假设下面的一个有向图：,,那么可以抽象出下面的数据结构：,,不知道大家发现规律了吗，每个顶点关联了它关联的其他顶点，比如A通过边关联了B,C,D, 可以理解为A有3条边，他们的目标顶点是B,C,D，那如何用java表示呢？,1.顶点类Vertex,成员变量edges表示顶点关联的所有的边。,2.顶点关联的边类Edge,成员变量targetVertexId用来存储边的目标顶点id,3.创建有向图DirectedDiagraph,回到前言的需求，目前图的数据模型已经创建好了，现在需要实现计算两个顶点之间可达路径的所有顶点集合，直接上代码。,由于用到的参数比较多，这边封装了一个算法的类CalcTwoVertexPathlgorithm,代码注释比较清晰的，就不再介绍了，主要是利用了深度搜索的方式+ 栈保存临时路径。,然后在DirectedDiagraph​类中添加一个方法findAllPaths()，查找所有的路径，如下图：,最后，我们写个单元测试验证下吧。,创建的例子也是我们前面图片中的例子，我们看下运行结果是否符合预期。,,本次需求利用了图这个数据结构得到结果，突然感觉数据结构和算法真的很重要，感觉现在的做法也不是最优解，性能应该也不是最佳，但是考虑到流程节点数据不会很多，应该能满足业务需求。不知道大家有没有更好的做法呢？