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

问题描述

让 A 成为图的邻接矩阵 G =（V，E）。如果节点 i 和 j A（i，j）= 1 $ c>与边相连， A（i，j）= 0 否则。

我的目标是了解 G 是否是非循环的。周期的定义如下：

• i 和 j 连接： A（i，j）= 1


• j 和 k 连接： A（j，k）= 1 li>
  
• k 和 i 连接： A（k ，我）= 1

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

• 从边缘开始（i，j）


• 选择从 j 输出的边的集合 O ，即<$ c中的所有1


• 导航 O code>以DFS方式


• 如果从此导航生成的路径之一通向节点 i ，则a周期被检测到
  
  
  

  很明显，这个解决方案非常慢，因为我必须评估矩阵中的所有路径。如果 A 非常大，则所需的开销非常大。我想知道是否有导航邻接矩阵的方法，以便在不使用DFS等昂贵算法的情况下查找周期。

  
  
  

  我想在MATLAB。

  
  
  

  在此先感谢，

  
  
  Eleanore。

  解决方案

  基于对 Danil 的观察，您需要计算 A ^ n ，这样做的效率稍高一些是
  
  

    n =尺寸（A，1）; 
   An = A; 
   for ii = 2：n 
   An = An * A;如果trace（An）〜= 0 
   fprintf（1，'got cycles\\\
  '），％不会重新计算从
  开始的A ^ n; 
  结束
  结束
    

  
  

  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.

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

  • 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:

  • 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

  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.

  I would like to implement my solution in MATLAB.

  Thanks in advance,

  Eleanore.

  解决方案

  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\n');
       end
  end
  

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