前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >图算法 - 只需“五步” ,获取两节点间的所有路径(非递归方式)

图算法 - 只需“五步” ,获取两节点间的所有路径(非递归方式)

作者头像
JSCON简时空
发布2020-03-02 09:56:48
3.2K0
发布2020-03-02 09:56:48
举报
文章被收录于专栏:JSCON简时空

温馨提示:因微信中外链都无法点击,请通过文末的 “阅读原文” 到技术博客中完整查阅版;

在实现 “图” 数据结构时,遇到 “获取两点之间是所有路径” 这个算法问题,网上的资料大多都是利用递归算法来实现(见文末的参考文章)。

我们知道在 JS 中用递归算法很容易会让调用栈溢出,为了能在生产环境中使用,必须要用非递归方式的去实现。

经过一番探索,实现的思路主要来自文章 《求两点间所有路径的遍历算法》 ,只是该文中并没有给出具体的实现细节,需要自己去实现;最终的实现结合类似 《算法 - 调度场算法(Shunting Yard Algorithm)》 中所提及的双栈来完成。

1、算法过程

以计算下图为例, 节点 3节点 6 所有路径所有可能的路径为 8 条:

获取图中两节点之间的所有路径

我们具体讲一下如何获取这 8 条路径的过程。

首先准备两个栈,分别称为 主栈辅栈

  • 主栈:每个元素是单个节点(Vertex),用于存放当前路径上的节点;
  • 辅栈:每个元素用于存放主栈对应元素的 相邻节点列表(Vertex Array);该栈是用来辅助 主栈 的,其长度和 主栈 一致;

Step 1: 建栈

v3节点3)放到主栈,同时将 v3 节点的邻接节点列表 [v1, v7] 放到辅栈中:

首次建栈

主栈和辅栈压入让栈长度增长,我个人称之为 建栈(build stack)

Step 2: 继续建栈

建栈后,我们查看辅栈,其栈顶是节点列表 [v1, v7]

查看栈顶

我们取出节点列表的第一个元素 v1,将其压入到主栈;同时将剩下的节点列表 [v7] 重新压回到辅栈:

压栈

同时查询 v1 的邻接节点列表是 [v3, v0]由于 v3 节点已经在主栈里,需要从这个列表中剔除(这一步很重要),将剔除后的节点列表 [v0] 压入 辅栈 中:

继续建栈

这一步也让主栈和辅栈长度增长了,所以也是 建栈(build stack) 过程

Step 3: 削栈

继续 Step 2 的建栈过程,直到我们的主栈栈顶 v7,此时辅栈的栈顶是空列表 []

当主栈是 v7 的时候,辅栈栈顶是空队列

由于辅栈的栈顶是空列表 [],所以没法继续建栈了 —— 这表明这条路径走到尽头了都还没找到目标节点 v6

走到 此路不通 的境地,我们就需要开始回退,看看来时的路上的其他岔路。

我们将主栈栈顶的 v7 弹出,同时也将辅栈的空列表 [] 弹出:

削栈

这一操作将导致 主栈辅栈 长度减少,该过程我个人称之为 削栈(cutdown stack)

Step 4:获取第一条路径

重复上述的 Step 2Step 3,采取策略:

  • 只要辅栈栈顶是非空列表,我们就建栈
  • 只要辅栈栈顶是空列表,我们就削栈

直到主栈的顶部节点是目标节点 v6

主栈栈顶元素是目标元素v6

进行到这里,我们停下来观察一番,发现主栈里的内容已经是一条完整的从 v3v6 的路径了:

获取一条从 v3 到 v6 的路径

我们输出当前栈为数组:['v3', 'v1', 'v0', 'v2', 'v5', 'v6'],该数组就表示 v3 -> v1 -> v0 -> v2 -> v5 -> v6 这条路径。

进行至此,我们终于获取了一条从 v3v6 的路径。

应该为自己的努力鼓个掌,已经看到胜利的曙光;接下来加个简单的循环就能获取所有的路径。

Step 5: 获取所有路径

重复 Step 2 - Step 4 步骤,采取策略如下:

  • 只要辅栈栈顶是非空列表,我们就建栈
  • 只要辅栈栈顶是空列表,我们就削栈
  • 只要主栈栈顶是目标节点,我们输出路径,同时削栈

重复以上过程,直到主栈为空为止。

随着 建栈(build stack)削栈(cutdown stack) 过程的进行,主栈和辅栈不断变化着,在这个变化的过程中我们就能不断地获取从 v3v6 的路径,最终就可以获取所有的路径。

2、代码实现

2.1、伪代码

依据上述过程的描述,很方面将文字转换成伪代码:

代码语言:javascript
复制
BEGIN

  初始化主栈
  初始化辅栈

  首次建栈

  WHILE 主栈不为空 THEN

    获取辅栈栈顶,为邻接节点列表

    IF 邻接节点列表不为空 THEN
      获取邻接节点列表首个元素
      将该元素压入主栈,剩下列表压入辅栈
      建栈
    ELSE
      削栈
      CONTINUE
    END IF

    IF 主栈栈顶元素 === 目标节点 THEN
      获取一条路径,保存起来
      削栈
    END IF

  END WHILE

END

以上是我们拿无向图来做范例,实际上该算法也适合有向图

2.2、实现效果

该双栈算法的 JS 实现已经写到代码库 ss-graph 中 ,我们直接拿它来做校验,实际运行效果如下:

可前往 https://runkit.com/boycgit/ss-graph 自行修改数据体验:

运行实际代码,验证算法

3、总结

最近在复习 “图” 这数据结构,在过程中逐步尝试书写代码去实现个中算法。能够体会得到知识点只有经过自己思考和总结后,才能为之后的融会贯通打下基础。

在本文的学习总结中,有两点体会印象较为深刻:

  1. 能用能递归解决的问题,一般都可以用 循环 + 栈(Stack) 的方式来解决。
  2. 当不知道算法如何实现的时候,比较适合归纳总结的学习方法,即先逐步从简单场景开始演示,等摸索到其中规律之后再想着去实现。

图相关的算法还有很多,有很多经典算法,后续有空会将一些经典的算法实现并整理出来,互有裨益。

REFERENCE

参考文档

  • Find if there is a path between two vertices in a directed graph:geeksforgeeks 相关面试题,递归实现
  • Print all paths from a given source to a destination:递归实现,查找所有路径
  • 求两点间所有路径的遍历算法:较为通俗易懂;,一个保存路径的栈、一个保存已标记结点的数
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-09-20,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 JSCON简时空 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1、算法过程
    • Step 1: 建栈
      • Step 2: 继续建栈
        • Step 3: 削栈
          • Step 4:获取第一条路径
            • Step 5: 获取所有路径
            • 2、代码实现
              • 2.1、伪代码
                • 2.2、实现效果
                • 3、总结
                领券
                问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档