algorithm - pseudo code for finding closed paths in a graph

Question

I have an adjaceny matrix for a graph which tracks the edges between the nodes by having a 1 in the corresponding adjMat[i,j] = 1; Through this adjaceny matrix i wish to find out all the closed paths of length 4 which exists in the graph. Can anyone please provide me with a pseudo code. thank u

Answer 1

This sounds like homework, so I won't give the whole thing away. But here's a hint: since you are interested in finding cycles of length 4, take the 4th power of the adjacency matrix and scan along the diagonal. If any entry M[i,i] is nonzero, there is a cycle containing vertex i.

Answer 2

也许它不是计算它的最佳方法（它是O(n^4)），但一种非常直接的方法是扫描所有顶点

a, b, c, d such that b > a, c > b, d > c

您可以检查然后检查以下每个周期：

1. ([a,b] && [b,c] && [c,d] && [d,a])
 2. ([a,b] && [b,d] && [d,c] && [c,a])
 3. ([a,d] && [d,b] && [b,c] && [c,a])

 1：2：3：
 A---B A---BAB
 | | \ / |\ /|
 | | X | X |
 | | / \ |/ \|
 D---C D---CCD

您基本上是在检查每个有序的顶点集 (a,b,c,d) 以了解它们可以形成循环的 3 种方式。

所以伪代码将是：

for a = 0 to <lastVertex>
 for b = a + 1 to <lastVertex>
  for c = b + 1 to <lastVertex>
   for d = c + 1 to <lastVertex>

    if(IsCycle(a,b,c,d)) AddToList([a,b,c,d])
    if(IsCycle(a,b,d,c)) AddToList([a,b,d,c])
    if(IsCycle(a,c,b,d)) AddToList([a,c,b,d])

   next d
  next c
 next b    
next a

Answer 3

Apply a depth-limited depth-first-search to every node and record nodes where the DFS finds the starting node. For the search, see pseudo-code here: http://en.wikipedia.org/wiki/Depth-limited_search. You just need to add something like

if(node' == node && node'.depth==4) memorize(node)

to the beginning of the loop.