我有一个n部分(无向)图，以邻接矩阵的形式给出，例如这里的一个:
A B C D
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
谢谢!
P.S.我已经看过用于计算传递闭包的算法，但是这些算法通常只能判断两个节点之间是否存在路径，而不能直接判断该路径上的节点。
最佳答案
您可以做的一件事是计算矩阵A的n次方。结果将告诉您从任一顶点到另一顶点的长度为n的路径数。
现在，如果您有兴趣了解路径上的所有顶点，那么我不认为使用纯矩阵运算是可行的方法。考虑到您有一个n部分图，我将按如下所示设置数据结构:(请记住，空间值对于除小值之外的所有值都将是昂贵的。)
每一列在我们的图形中每个节点都有一个条目。如果从我们指定的起始顶点或起始集开始的第n次迭代中此节点可到达，则第n列将包含in，否则为零。每个列条目还将包含指向n-1列中的顶点的后向指针列表，该指针指向第n列中的该顶点。 (这类似于维特比算法，不同之处在于，我们必须为每个条目维护一个后向指针列表，而不仅仅是维护一个。)执行此操作的复杂度为(m ^ 2)* n，其中m是顶点中顶点的数量。图，n是所需路径的长度。
我对您的顶部矩阵有些困惑:对于一个未经校正的图，我希望邻接矩阵是对称的。
关于math - 矩阵运算可枚举n部分图的所有路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/587636/