Java如何计算图中两个顶点间的所有路径？

本文共计2022个文字，预计阅读时间需要9分钟。

目录+前言+抽象数据模型+代码实现数据模型+计算两个顶点之间路径算法+总结+前言+最近公司的项目上有这样一个需求，还有一个分享价值的，这边做个记录。需求大致如下，下面是一个流程图。

目录

• 前言
• 抽象数据模型
• 代码实现数据模型
• 计算两个顶点之间路径算法
• 总结

前言

最近公司的项目上有个需求，还挺有分享价值的，这边做个记录。需求大致如下，下面的一个流程图，点击条件线上选择的内容，必须是前面配置过的节点，如果不是，需要在保存的时候做强校验提示。

需求其实很明确，抽象出来就是获取图中两个顶点之间所有可达路径的顶点集合，大家可以思考下，该如何实现？这里面涉及到了数据结构中图相关知识，而数据结构算法也是本事最大的弱项，还是废了我一番工夫。

抽象数据模型

实际上，看到这个需求就很容易想到我们的有向图，那么在java中该用怎么样的数据结构表示有向图呢？在恶补了一番图相关的知识以后，最终确定用"邻接表"的方式实现。邻接表是图的一种最主要存储结构,用来描述图上的每一个点。