MATLAB:如何在有向图中找到任何循环中的节点？

Question

假设有向图 A 的邻接矩阵由下式给出

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

那么任意循环中的节点都是

1 (1->2->1)
2 (2->1->2)
4 (4->4)

有没有一种有效的方法来获取任何循环中的节点列表？

我知道求和 A,A^2,A^3,A^4... 并搜索非零对角线工作，但我正在处理高维矩阵，这需要很长时间。

谢谢。

Answer 1

您可以使用 dfsearch使用 edgetodiscovered 选项查找所有循环的开始和结束节点。然后使用循环查找shortest path从结束节点到起始节点:

G = digraph(A);
e = dfsearch(G, 1, 'edgetodiscovered', 'Restart', true);
n = size(e,1);
result = cell(1,n);
for k = 1:n
    result{k} = shortestpath(G, e(k,2), e(k,1), 'Method', 'unweighted');
end

为了避免循环，您可以创建一个虚拟节点并将从该节点到循环的所有结束节点的边添加。然后使用 shortestpathtree找到从虚拟节点到循环起始节点的最短路径。请注意，结果中的每条路径都以应从路径中删除的虚拟节点开始。

G = digraph(A);
e = dfsearch(G, 1, 'edgetodiscovered', 'Restart', true);
n = size(e,1);
dummy = numnodes(G) + 1;
G = addedge(G, repmat(dummy, n, 1) , e(:,2));
result = shortestpathtree(G, dummy , e(:,1), 'OutputForm', 'cell', 'Method', 'unweighted');