包含特定链接的有向非循环图中的路径总数

Question

我一直在尝试编写一个算法,该算法采用有向的节点集(我现在表示为稀疏的有向邻接矩阵),比如A,B,C和D,当被调用时,它给了我所有包含给定路径的可能路径(例如AB或AD).节点无法连接到自身,并且最终将所有节点定向为从A流向D.

到目前为止,我已经尝试编写递归python脚本,但成功有限 - 我的图论不强(实际上我没有背景).任何人都可以提供任何帮助,我应该去的方向将不胜感激.

作为免责声明 - 这不是家庭作业(我只是尝试处理大型数据集并为某些研究建立个人图书馆),我已经看了几个小时的"类似问题",但很大程度上没有用(除了前面提到的递归python脚本).

谢谢.

Answer 1

首先解决更简单的问题:给定DAG中的两个点A和B,您可以计算所有以A开头并以B结尾的路径吗？("路径"定义为边的列表,其中一个端节点等于下一个节点的起始节点.)

听起来很难.我们可以简化它吗？

很明显,最简单的情况是A和B实际上是同一个节点.在这种情况下,路径为零,因为图形是非循环的.

假设A和B不同.WOLOG假设A恰好有两个邻居C和D,它们都不是B.从A到B的路径数必须等于从C到B的路径数,再加上从D到B的路径数.

更一般地说:如果A有n个邻居,其中没有一个是B,那么找到从每个邻居到B的路径数并将它们相加.

如果A 确实有邻居B,那么不要忘记在路径A-> B的总数中加一.

现在我们将其分解为许多子问题,每个子问题都严格小于上一个问题.

你会认为一个简单的递归解决方案可以解决问题,但不幸的是它没有.考虑这个图:

                    A
                   / \
                  C   D
                   \ /
                    E
                   / \
                  F   G
                   \ /
                    H
                   / \
                  I   J
                   \ /
                    B

• 从A到B的路径等于从C到B的路径加上从D到B的路径.因此计算这些路径.
• 从C到B的路径等于从E到B的路径.
• 从D到B的路径等于从E到B的路径.

而且......我们只计算了从E到B两次的路径.这将依次计算从H到B的路径两次,总共四次.我绘制的算法最终可以计算2 ⁿ次相同的事情,其中n与图中节点的数量成正比!

你需要做的是制作一个记忆器,这样一旦答案计算一次,它就再也不会计算出来了.

因此,通过制作递归的,记忆的算法来解决更简单的问题,该算法计算两个给定节点之间的路径总数.

所以让我们试一试.从A到B有多少条路径？让我们来表示ab.我们计算:

ab = cb + db, but we don't know them...
  cb = eb, but we don't know it...
    eb = fb + gb, but we don't know them...
      fb = hb, but we don't know it...
        hb = ib + jb, but we don't know them...
          ib = 1
          jb = 1
        therefore hb = 2
      therefore fb = 2
    gb = hb, but we already know that is 2
    therefore eb = 4
  therefore cb = 4
  db = eb, but we already know that is 4
therefore ab is 8

我们已经完成了.

一旦找到两个节点之间的路径数,就可以直接计算包含给定边的所有路径.例如,从A到B的路径通过EG,等于从A到E的路径数乘以从G到B的路径数.

我们来试试吧.

ae = ce + de
  ce = 1
  de = 1
so ae = 2

gb = hb
  hb = ib + jb
    ib = 1
    jb = 1
  so hb = 2
so gb = 2

并且从A到B有ae*gb = 4路径通过EG.我们来看看我们的工作.路径是

AC-CE-EG-GH-HI-IB
AC-CE-EG-GH-HI-JB
AD-DE-EG-GH-HI-IB
AD-DE-EG-GH-HI-JB

是的,有四个.

合理？