用于在图中查找闭合路径的伪代码

Question

我有一个图的邻接矩阵，它通过在相应的 adjMat[i,j] = 1 中包含 1 来跟踪节点之间的边； 通过这个邻接矩阵，我希望找出图中存在的所有长度为 4 的闭合路径。 谁能给我提供一个伪代码。 感谢你

Answer 1

这听起来像是家庭作业，所以我不会透露全部内容。 但这里有一个提示：由于您对查找长度为 4 的循环感兴趣，因此取邻接矩阵的 4 次方并沿对角线扫描。 如果任何条目 M[i,i] 不为零，则存在包含顶点 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---B     A   B
 |   |       \ /      |\ /|
 |   |        X       | X |
 |   |       / \      |/ \|
 D---C      D---C     C   D

您基本上是在检查每个有序顶点集（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

对每个节点应用深度有限的深度优先搜索，并记录 DFS 找到起始节点的节点。
对于搜索，请参阅此处的伪代码： http://en.wikipedia.org/wiki/深度受限_搜索。 添加类似的内容即可。

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

您只需在循环的开头