图算法 – 只需“五步” ,获取两节点间的所有路径(非递归方式)_奈落_前端开发者

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

获取两点之间是所有路径

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

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

求两点间所有路径的遍历算法算法 – 调度场算法(Shunting Yard Algorithm)

1、算法过程

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

节点 3节点 6

allpathallpath

allpath

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

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

主栈辅栈

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

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

    Step 1: 建栈

    Step 1

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

    v3节点3v3[v1, v7]

    首次建栈首次建栈

    首次建栈

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

    建栈(build stack)

    Step 2: 继续建栈

    Step 2

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

    [v1, v7]

    查看栈顶查看栈顶

    查看栈顶

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

    v1[v7]

    压栈压栈

    压栈

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

    v1[v3, v0]由于 v3 节点已经在主栈里,需要从这个列表中剔除v3[v0]辅栈

    继续建栈继续建栈

    继续建栈

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

    建栈(build stack)

    Step 3: 削栈

    Step 3

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

    Step 2v7[]

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

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

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

    []v6

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

    此路不通

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

    v7[]

    削栈削栈

    削栈

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

    主栈辅栈削栈(cutdown stack)

    Step 4:获取第一条路径

    Step 4

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

    Step 2Step 3

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

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

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

    v6

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

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

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

    v3v6

    获取一条从 v3 到 v6 的路径获取一条从 v3 到 v6 的路径

    获取一条从 v3 到 v6 的路径

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

    ['v3', 'v1', 'v0', 'v2', 'v5', 'v6']v3 -> v1 -> v0 -> v2 -> v5 -> v6

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

    v3v6

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

    Step 5: 获取所有路径

    Step 5

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

    Step 2Step 4

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

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

  • 只要主栈栈顶是目标节点,我们输出路径,同时削栈
  • 目标节点

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

    主栈

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

    建栈(build stack)削栈(cutdown stack)v3v6

    2、代码实现

    2.1、伪代码

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

    BEGIN

      初始化主栈
      初始化辅栈

      首次建栈

      WHILE 主栈不为空 THEN

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

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

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

      END WHILE

    END

    BEGIN

      初始化主栈
      初始化辅栈

      首次建栈

      WHILE 主栈不为空 THEN

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

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

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

      END WHILE

    END
    BEGIN

      初始化主栈
      初始化辅栈

      首次建栈

      WHILE 主栈不为空 THEN

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

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

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

      END WHILE

    END

    WHILE 主栈不为空 THEN

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

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

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

      END WHILE

    END
    THEN

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

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

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

      END WHILE

    END

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

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

      END WHILE

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

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

      END WHILE

    END

    ELSE
          削栈
          CONTINUE
        END IF

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

      END WHILE

    END

    CONTINUE
        END IF

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

      END WHILE

    END

    END IF

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

      END WHILE

    END
    IF

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

      END WHILE

    END

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

      END WHILE

    END
    THEN
          获取一条路径,保存起来
          削栈
        END IF

      END WHILE

    END

    END IF

      END WHILE

    END
    IF

      END WHILE

    END

    END WHILE

    END
    WHILE

    END

    END

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

    该算法也适合有向图

    2.2、实现效果

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

    ss-graphss-graph

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

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

    运行实际代码,验证算法运行实际代码,验证算法

    运行实际代码,验证算法

    3、总结

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

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

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

  • 当不知道算法如何实现的时候,比较适合归纳总结的学习方法,即先逐步从简单场景开始演示,等摸索到其中规律之后再着手去实现。
  • 图相关的算法还有很多,有很多经典算法,后续有空会将一些经典的算法实现并整理出来,互有裨益。

    参考文章

  • Find if there is a path between two vertices in a directed graph:geeksforgeeks 相关面试题,递归实现
  • Find if there is a path between two vertices in a directed graph

  • Print all paths from a given source to a destination:递归实现,查找所有路径
  • Print all paths from a given source to a destination

  • 求两点间所有路径的遍历算法:较为通俗易懂;,一个保存路径的栈、一个保存已标记结点的数
  • 求两点间所有路径的遍历算法

    以下是我的公众号,会时常更新 JS(node.js) 知识和资讯,欢迎扫码关注交流。

    个人微信公众号个人微信公众号

    个人微信公众号

    » 本文来自:前端开发者 » 《图算法 – 只需“五步” ,获取两节点间的所有路径(非递归方式)_奈落_前端开发者》
    » 本文链接地址:https://www.rokub.com/73289.html
    » 您也可以订阅本站:https://www.rokub.com
    赞(0)
    64K

    评论 抢沙发

    评论前必须登录!