用于枚举 n 分图所有路径的矩阵运算
我有一个 n 部分（无向）图，以邻接矩阵形式给出，例如这里的这个：
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我已经研究了计算传递闭包的算法，但这些通常只能告诉两个节点之间是否存在路径，而不直接告诉哪些节点在该路径上。
I have an n-partite (undirected) graph, given as an adjacency matrix, for instance this one here:
a b c d a 0 1 1 0 b 0 0 0 1 c 0 0 0 1 d 0 0 0 0
I would like to know if there is a set of matrix operations that I can apply to this matrix, which will result in a matrix that "lists" all paths (of length n, i.e. through all the partitions) in this graph. For the above example, there are paths a->b->d and a->c->d. Hence, I would like to get the following matrix as a result:
a b c d 1 1 0 1 1 0 1 1
The first path contains nodes a,b,d and the second one nodes a,c,d. If necessary, the result matrix may have some all-0 lines, as here:
a b c d 1 1 0 1 0 0 0 0 1 0 1 1 0 0 0 0
Thanks!
P.S. I have looked at algorithms for computing the transitive closure, but these usually only tell if there is a path between two nodes, and not directly which nodes are on that path.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可以做的一件事是计算矩阵 A 的 n 次方。结果将告诉您从任何一个顶点到任何其他顶点有多少条长度为 n 的路径。
现在，如果您有兴趣了解路径上的所有顶点，我认为使用纯矩阵运算并不是正确的方法。 请记住，您有一个 n 分图，我将设置一个数据结构，如下所示：（请记住，除了小值之外，所有空间成本都会很昂贵。）
每一列将有每个节点的一个条目在我们的图表中。 如果该节点在第 n 次迭代中从我们指定的起始顶点或起始集可到达，则第 n 列将包含 1，否则为零。 每个列条目还将包含指向第 n-1 列中的顶点的后向指针列表，这些顶点指向第 n 列中的该顶点。 （这类似于维特比算法，只不过我们必须为每个条目维护一个反向指针列表，而不仅仅是一个。）这样做的复杂度是 (m^2)*n，其中 m 是图，n 是所需路径的长度。
我对你的顶部矩阵有点困惑：对于无向图，我希望邻接矩阵是对称的。
One thing you can do is to compute the nth power of you matrix A. The result will tell you how many paths there of length n from any one vertex to any other.
Now if you're interested in knowing all of the vertices along the path, I don't think that using purely matrix operations is the way to go. Bearing in mind that you have an n-partite graph, I would set up a data structure as follows: (Bear in mind that space costs will be expensive for all but small values.)
Each column will have one entry of each of the nodes in our graph. The n-th column will contain 1 in if this node is reachable on the n-th iteration from our designated start vertex or start set, and zero otherwise. Each column entry will also contain a list of back pointers to the vertices in the n-1 column which led to this vertex in the nth column. (This is like the viterbi algorithm, except that we have to maintain a list of backpointers for each entry rather than just one.) The complexity of doing this is (m^2)*n, where m is the number of vertices in the graph, and n is the length of the desired path.
I'm a little bit confused by your top matrix: with an undidrected graph, I would expect the adjacency matrix to be symmetric.
不，没有纯矩阵方式来生成所有路径。 请使用纯组合算法。
“你可以做的一件事就是计算矩阵 A 的 n 次方。结果将告诉你从任何一个顶点到任何其他顶点有多少条长度为 n 的路径。”
矩阵的力量产生的是行走而不是路径。
No, There is no pure matrix way to generate all paths. Please use pure combinatorial algorithms.
'One thing you can do is to compute the nth power of you matrix A. The result will tell you how many paths there of length n from any one vertex to any other.'
The power of matriax generates walks not paths.