c++ - 无向图中的 4 个循环

Question

我有一个无向图，它作为邻域矩阵给出。我需要找到 4 个周期的计数：包含 4 个边的周期。如果您对算法有任何想法，请帮助我。

Answer 1

简单（非最佳）方法伪代码：

output = []
skip_nodes = []
for node in input_graph:
    if node in skip_nodes:
        continue
    for path in deep_search(start=node, max_depth=4):
        if len(path) == 4 and path[1] == path[4]:
            output.append(path)
            skip_nodes.append(path[2], path[3], path[4])
return output

Answer 2

将矩阵自身乘以 4 次，据我所知，非 0 对角线项将参与 4 边循环（此处可能有错误的标准，但您可以进一步挖掘）

http://www.math.vt.edu/people/brown/doc/cycles_dm9875.pdf