• 中文
    • English
  • 注册
  • 查看作者
  • 计算图中两个顶点的所有路径,你会吗

    前言

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

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

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

    抽象数据模型

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

    我们假设下面的一个有向图:

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

    那么可以抽象出下面的数据结构:

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

    不知道大家发现规律了吗,每个顶点关联了它关联的其他顶点,比如A通过边关联了B,C,D, 可以理解为A有3条边,他们的目标顶点是B,C,D,那如何用java表示呢?

    代码实现数据模型

    1. 顶点类Vertex

    • 成员变量 表示顶点关联的所有的边

    1. 顶点关联的边类Edge

    • 成员变量 用来存储边的目标顶点id

    1. 创建有向图DirectedDiagraph

    • 成员变量 存储图中的顶点信息

    • 方法用来添加顶点数据

    • 方法用来添加边数据

    计算两个顶点之间路径算法

    回到前言的需求,目前图的数据模型已经创建好了,现在需要实现计算两个顶点之间可达路径的所有顶点集合,直接上代码。

    由于用到的参数比较多,这边封装了一个算法的类

    • 方法就是算法的核心入口

    • 成员变量 中存放了所有可达的路径列表。

    • 方法打印所有的路径。

    • 返回所有可达的顶点集合。

    代码注释比较清晰的,就不再介绍了,主要是利用了深度搜索的方式+ 栈保存临时路径。

    然后在 类中添加一个方法 ,查找所有的路径,如下图:

    最后,我们写个单元测试验证下吧。

    创建的例子也是我们前面图片中的例子,我们看下运行结果是否符合预期。

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

    总结

    本次需求利用了图这个数据结构得到结果,突然感觉数据结构和算法真的很重要,感觉现在的做法也不是最优解,性能应该也不是最佳,但是考虑到流程节点数据不会很多,应该能满足业务需求。不知道大家有没有更好的做法呢?

  • 0
  • 0
  • 0
  • 71
  • 请登录之后再进行评论

    登录
  • 任务
  • 实时动态
  • 发布
  • 单栏布局 侧栏位置: