检测邻接矩阵中的循环 [英] Detecting cycles in an adjacency matrix

问题描述

令A 为图G = (V,E) 的邻接矩阵.A(i,j) = 1 如果节点 i 和 j 与一条边相连，A(i,j)= 0 否则.

Let A be the adjacency matrix for the graph G = (V,E). A(i,j) = 1 if the nodes i and j are connected with an edge, A(i,j) = 0 otherwise.

我的目标是了解 G 是否是非循环的.循环定义如下:

My objective is the one of understanding whether G is acyclic or not. A cycle is defined in the following way:

• i 和 j 相连:A(i,j) = 1
• j 和 k 相连:A(j,k) = 1
• k 和 i 相连:A(k,i) = 1

• i and j are connected: A(i,j) = 1
• j and k are connected: A(j,k) = 1
• k and i are connected: A(k,i) = 1

我已经实现了一个导航矩阵的解决方案，如下所示:

I have implemented a solution which navigates the matrix as follows:

• 从边开始(i,j)
• 选择从j出的边的集合O，即j-th行的所有1>A
• 以 DFS 方式导航 O
• 如果此导航生成的路径之一通向节点 i，则检测到一个循环

• Start from an edge (i,j)
• Select the set O of edges which are outgoing from j, i.e., all the 1s in the j-th row of A
• Navigate O in a DFS fashion
• If one of the paths generated from this navigation leads to the node i, then a cycle is detected

显然这个解决方案很慢，因为我必须评估矩阵中的所有路径.如果A很大，那么所需的开销也很大.我想知道是否有一种导航邻接矩阵的方法，以便在不使用昂贵的算法(例如 DFS)的情况下找到循环.

Obviously this solution is very slow, since I have to evaluate all the paths in the matrix. If A is very big, the required overhead is very huge. I was wondering whether there is a way of navigating the adjacency matrix so as to find cycles without using an expensive algorithm such as DFS.

我想在 MATLAB 中实现我的解决方案.

I would like to implement my solution in MATLAB.

提前致谢，

埃莉诺.

推荐答案

根据Danil的观察，你需要计算A^n，一种稍微更有效的方法是

Based on the observation of Danil, you need to compute A^n, a slightly more efficient way of doing so is

n = size(A,1);
An = A; 
for ii = 2:n
     An = An * A; % do not re-compute A^n from skratch
     if trace(An) ~= 0
        fprintf(1, 'got cycles
');
     end
end

这篇关于检测邻接矩阵中的循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！