让A是该图的邻接矩阵G = (V,E) A(i,j) = 1如果节点i和j都具有边缘，连接A(i,j) = 0否则。
我的目的是了解是否一个G是无环的或不是。 一个周期被以如下方式定义：
i和j连接： A(i,j) = 1 j和k连接： A(j,k) = 1 k和i是连接： A(k,i) = 1 我已经实现其导航所述矩阵如下的解决方案：
(i,j) O边缘，它们被从传出j中，即，所有1S j的排第A O在DFS时尚 i ，则检测到循环 显然，这种解决方案很慢，因为我必须评估矩阵中的所有路径。 如果A是非常大的，所需要的开销是非常巨大的。 我想知道是否有导航邻接矩阵以便找到循环而没有使用昂贵的算法如DFS的一种方式。
我想实现我在MATLAB的解决方案。
提前致谢，
Eleanore。
根据观察DANIL ，你需要计算A^n ，这样做的稍微更有效的方式是这样
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\n');
end
end
回答这个，当我遇到这个问题就来了math.stackexchange问题。 对于未来的读者，我觉得我需要指出的（如其他已经）认为DANIL Asotsky的答案不正确，并提供一种替代方法。 该定理DANIL指的是第（i，j）的a ^ k的条目计数长度为k的阶层的数量从i到j在G.最关键的事情在这里的是，一走就是允许重复顶点。 所以，即使^ k的对角项为正，每走条目计数可能包含重复的顶点，所以就不能算作一个周期。
反：长度为4的路径将根据DANIL的回答包含一个4循环（更不用说，答案将意味着P = NP，因为这将解决汉密尔顿周期问题）。
不管怎么说，这里是另一种方法。 一个图是无环的，当且仅当它是一个森林，即，其具有C组分和准确NC边缘，其中n是顶点的数目。 幸运的是，有一种方法使用计算部件的数量拉普拉斯矩阵 L，其通过用条目的总和在第i行替换A的-A的第（i，i）的条目（即，顶点的程度得到用i）。 然后已知的G分量的数量为n-秩（L）（即，0多重为L的特征值）。
所以G具有周期当且仅当边的数目是至少N-（N-秩（L））+ 1。 在另一方面，通过握手引理，边的数量是完全迹（L）的一半。 所以：
G是无环的，当且仅当0.5 *微量（L）=秩（L）。 同样地，G具有周期当且仅当0.5 *微量（L）> =秩（L）+1。
如果A是定向或无向图G的邻接矩阵，则矩阵A^n （即，A的n个拷贝的矩阵乘积）具有以下性质：在第i行和第j列的条目给出的数量（针对或无向）散步长的n个顶点从i到顶点Ĵ。
例如，如果由于某种整数n矩阵A ^ n的含有至少一个非零对角项，比图具有大小为n的周期。
最简单的方法检查用于矩阵的非零对角线元素是计算矩阵trace(A) = sum(diag(A))在我们的矩阵式电力的情况下，元素将永远非负）。
Matlab的解决方案可以是以下几点：
for n=2:size(A,1)
if trace(A^n) ~= 0
fprintf('Graph contain cycle of size %d', n)
break;
end
end
这种方法使用DFS，但是是非常有效的，因为我们没有在随后的DFS的重复节点。
高层次的方法：
初始化所有节点的值设置为-1 。
从每个未知节点做了DFS，该节点的值设置为从开始自动递增值0 。
对于这些DFS的，更新每个节点的与值previous node's value + i/n^k其中该节点是i个先前节点和子k是探索的深度， 跳过已探索节点 （除了用于检查一个更大的值） 。
因此，对于一个示例n = 10 ：
0.1 0.11 0.111
j - k - p
0 / \ 0.12
i \ 0.2 l
m
1 1.1
q - o
...
您也可以使用i/branching factor+1为每个节点，以减少数字的显著数字，但是这需要额外的计算来确定。
所以上面我们从做了DFS i ，其中有2名儿童j和m 。 m无儿无女， j有2个孩子，......然后，我们完成了i ，并从下一个未开发的节点开始另一个DFS q 。
每当你遇到一个更大的价值，你知道发生了循环。
复杂：
您在检查每个节点最多一次，并在每一个节点，你做ñ检查，所以复杂度O(n^2)这是一样的在矩阵中的每个条目看一次（你不能做不过如此）。
注意：
我也只会注意， 邻接表可能比邻接矩阵更快，除非这是一个非常稠密图。
这就是问题我也有发现。 的解释，我想，如下所示：
当我们谈论周期，暗示我们的意思向圈。 你有邻接矩阵具有当你考虑到有向图有不同的含义; 这的确是长度为2的定向周期那么，$ A ^ N $的解决方案实际上是有向图。 对于无向图，我想一个解决将是只考虑矩阵（以0其余部分）的上三角的版本并重复上述步骤。 让我知道如果这是正确的答案。
如果图G是由它的邻接矩阵M则M'=表示的（I - M）将如果在它一个周期是单数。 我：M的同阶的单位矩阵
在基质上的方法更多一些想法...举的例子是用于断开的图的邻接矩阵（节点1和2被连接，并且节点3和4被连接，但也对连接到另一对）。 当你计算A ^ 2，答案（如说明）为单位矩阵。 然而，由于跟踪（A ^ 2）= 4，这表示有每个长度为2（这是正确的）的2个循环。 计算A ^ 3是不允许的，直到这些环被正确地识别并从基质除去。 这是一个复杂的过程，需要几个步骤，并且通过RL诺曼很好地详细描述的，“A矩阵法有向图，循环的位置” AIChE的Ĵ，11-3（1965），第450-452。 请注意：这是从作者，这种做法是否保证找到所有周期的，独特的循环，和/或基础周期不清楚。 我的经验表明，绝对不只能识别唯一周期。
