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

0 以外の対角要素が 4 エッジ サイクルに参加することを覚えている限り、マトリックス自体を 4 回乗算します (ここでは基準が間違っている可能性がありますが、さらに掘り下げることができます)。

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