グラフの単純な閉路（サイクル）の距離を列挙する｜Python

Aru

グラフのサイクル（閉路）を検出する方法として強連結成分（SCC）などのアルゴリズがあり、AtCoder Libraryなどでライブラリ化されているので検出にはそれを使えば良いです。ここでは、開始点を１つ固定した場合の閉路を列挙する方法を解説します。

Contents

サイクル（閉路）の検出

サイクル（閉路）の検出

サイクル（閉路とは）とは

ここでは、有向グラフ（グラフに向きがある場合）のサイクルについて考えます。サイクルとは、グラフにおいて同じノードに戻ってくるような経路 のことを指します。より厳密には、同じ辺を2回以上通らずに、開始点と終了点が同じになるパス （経路）のことです。

例えば１→２、２→３、３→１という３つの経路が存在する場合、１→２→３→１と辿れば同じノードに戻ってくるのでサイクルということになります。

サイクルの検出

サイクルが存在するかどうかはDFS（深さ優先探索）を行うことで可能です。なお、サイクル検出は強連結成分分解（SCC）を使うことで高速に行うことができますが、「ある頂点を含むサイクルの列挙」を行うことはできません。

この記事では特定の頂点からスタートするサイクルを列挙を行う方法について解説します。

サイクルの距離を検出する

サイクルが存在するかどうかは、DFS（深さ優先探索）を行うことで可能です。すべての頂点からDFSをすると演算量が大きいですが、１つの頂点からなら演算量は小さくなります。

競技プログラミングなどでは、サイクル列挙を行うことは少ないかもしれませんが、たまに使うことがあります。

ある点（ここではノード１）を始点とするサイクルを検出するのはDFSをPythonプログラムは以下のようになります。

各変数の意味

node: グラフの隣接リスト（各ノードの到達先とコスト）
rst: 各頂点までの経路長集合。最終的にrst[0]がサイクル距離を格納
use: 再帰探索中の訪問済みノードを管理するフラグ配列
L: 許容される最大経路長（プログラムでは実質無制限ですが、制限することも可能）

このプログラムではグラフの形状をテキストファイルから読み込んだ後、dfs(0,0)を呼び出すことで探索を行います。結果はrst[0]に格納されているのでそれを表示します。

import sys
sys.setrecursionlimit(10**6) # 再帰の深さを増やしておく

n, m = map(int,input().split())

node = [[] for _ in range(n)]
for i in range(m) :
    u, v, c = map(int,input().split())
    u -= 1
    v -= 1
    node[u].append((v, c))


rst = [set() for _ in range(n)]
use = [False for _ in range(n)] 

L = 10**9

def dfs(cur, l) :
    if l > L :
        return 
    use[cur] = True
    for e in node[cur] :
        if e[0] == 0 :
            rst[0].add(l+e[1])
        if use[e[0]] :
            continue
        if l+e[1] in rst[e[0]] :
            continue
        rst[e[0]].add(l+e[1])
        dfs(e[0], l+e[1])
    use[cur] = False
                   
dfs(0, 0)

print(*rst[0])

入力の例

入力は有向グラフになります（1 2 1の入力は 1→2へコスト１の経路があることを示す。双方向でないことに注意）

入力をグラフとして書くと以下のようになります。

結果

サイクルは、 1→2→3→1, 1→2→3→4→1, 1→2→3→4→5→1（逆順もあり）の合計3種類になります。

3 4 5

このように深さ優先探索を行うことでサイクルの経路長を列挙することができます

まとめ

有向グラフに含まれるサイクルを列挙する場合、強連結成分分解（SCC）を使うことが多いと思いますが、SCCでは一番大きなサイクルでグループ化されてしまいます。列挙するには、深さ優先探索を行うのが簡単です（演算量は要注意です）。この記事では、DFSによるサイクル列挙のコードをPythonで書いてみました。参考になれば幸いです。

#python #グラフ