矩阵运算以枚举通过n-partite图的所有路径

Question

我有一个n-partite(无向)图,作为邻接矩阵给出,例如这个:

  a b c d
a 0 1 1 0
b 0 0 0 1
c 0 0 0 1
d 0 0 0 0

我想知道是否有一组矩阵运算可以应用于此矩阵,这将产生一个矩阵,用于"列出"此图中所有路径(长度为n,即通过所有分区).对于上面的示例,存在路径a-> b-> d和a-> c-> d.因此,我想得到以下矩阵:

a b c d
1 1 0 1
1 0 1 1

第一个路径包含节点a,b,d,第二个路径包含节点a,c,d.如有必要,结果矩阵可能会有一些全0行,如下所示:

a b c d
1 1 0 1
0 0 0 0
1 0 1 1
0 0 0 0

谢谢!

PS我已经研究了用于计算传递闭包的算法,但这些算法通常只能说明两个节点之间是否存在路径,而不是直接指向该路径上的哪些节点.

Answer 1

您可以做的一件事是计算矩阵 A 的 n 次方。结果将告诉您从任何一个顶点到任何其他顶点有多少条长度为 n 的路径。

现在，如果您有兴趣了解路径上的所有顶点，我认为使用纯矩阵运算并不是正确的方法。请记住，您有一个 n 部分图，我将设置如下数据结构：（请记住，对于除小值之外的所有值而言，空间成本都会很昂贵。）

每列都会有图表中每个节点的一个条目。如果该节点在第 n 次迭代中从我们指定的起始顶点或起始集可到达，则第 n 列将包含 1，否则为零。每个列条目还将包含指向第 n-1 列中的顶点的后向指针列表，这些顶点指向第 n 列中的该顶点。（这类似于维特比算法，只不过我们必须为每个条目维护一个反向指针列表，而不仅仅是一个。）这样做的复杂度是 (m^2)*n，其中 m 是图，n 是所需路径的长度。

我对你的顶部矩阵有点困惑：对于无向图，我希望邻接矩阵是对称的。