在邻接矩阵中形成循环的节点（Matlab）

Question

我有一个有向边的邻接矩阵。计算 A^3，将帮助我检测矩阵中是否存在长度为 3（三角形）的循环。但是，我想知道哪些节点形成了三角形。我怎样才能在 Matlab 中实现这个？

谢谢

Answer 1

矩阵乘法的问题在于它将所有行相加。当您将矩阵 P 的第一行乘以矩阵 Q 的第一列时，它会进行逐元素乘法，然后生成结果向量的总和，从而丢弃有关该矩阵的所有数据中间节点。好吧，我们想要那个向量，所以让我们阻止它把它们相加。

假设我们有邻接矩阵 A:

A =

   0   1   0   0   0
   0   0   1   0   0
   1   0   0   1   0
   0   0   0   0   0
   0   0   0   1   0

并且我们想找出是否有从节点 x 到节点 z 通过节点 y 的任何路径（还不是循环）。 x 行告诉我们哪些节点的边从 x 到 y，列 z 告诉我们哪些节点的边从 y 到 z .如果我们对行 x 和列 z 进行逐元素 AND，我们应该得到一个包含所有节点 y 的向量，这些节点都连接到 [=19] =] 和 z.

例如，如果我们对这个邻接矩阵 AND 行 1 和列 3：

A =

   0   1   0   0   0
   x   x   1   x   x
   x   x   0   x   x
   x   x   0   x   x
   x   x   0   x   x 

>> A(1,:) & A(:,3).'   %// remember to transpose the column first...
ans =

   0   1   0   0   0

我们看到它们由节点 2 连接。太棒了，现在我们知道对于这种情况我们有一条路径 1->2->3。不过一般来说，从 1 到 3 可能有多个路径，因此我们将使用整个向量。

现在我们要做的就是确保存在从节点 3 返回节点 1 的路径。好吧，那是我们邻接矩阵中的行 3、列 1。如果我们 AND A(3,1) 与我们的矢量，如果有从 3 到 1 的边，我们应该返回相同的矢量，如果没有则返回零（因此，无循环）。

>> (A(1,:) & A(:,3).') & A(3,1)
ans =

   0   1   0   0   0

对此进行概括，从 x 到 z 的每条路径的向量是

C(x,:,z) = (A(x,:) & A(:,z).') & A(z,x);

不幸的是，我一直无法找到一种方法来对其进行矢量化处理，因此目前双 for 循环就足够了：

for x = 1:size(A,1)
   for z = 1:size(A,2)
      C(x,:,z) = (A(x,:) & A(:,z).') & A(z,x);
   end
end

如果存在从 x 到 y 再到 z（和返回）的循环，则结果矩阵将具有 C(x,y,z) = 1，否则为 0 .注意每个循环会被列出3次：

C(x,y,z) == C(y,z,x) == C(z,x,y)

在邻接矩阵中形成循环的节点（Matlab）

Nodes that form a loop in adjacency matrix (Matlab)

matlab

matrix

matrix-multiplication

adjacency-matrix