【Golang】DFS(深さ優先探索)による有向グラフのcycle detectを実装する

【Golang】DFS(深さ優先探索)による無向グラフのcycle detectを実装する - 逆さまにしたの続きで、今度は有向グラフのcycle detectです。 Detect Cycle in Directed Graph Algorithmを視聴したので、実装してみることにします。

有向グラフにおけるDFSによるcycle detectのアルゴリズム

有向グラフでは、同じDFSによるcycle detectでも、無向グラフのときと異なり、White Set、Grey Set、Black Setという3つの集合を利用します。特にGrey Setは、無向グラフにおけるVisited Setの役割を果たします。 これらの集合を使い、以下のアルゴリズムでDFSによるcycle detectを行います。

1. すべての頂点をWhite Setに追加する
2. White Setから頂点sを取り出す
3. 頂点sをGrey Setに加える
4. 頂点sの接続先である頂点cを順番に訪問する。未訪問の接続先がなくなった(葉のように元々接続先がない場合も含む)場合、頂点sをBlack Setに加え、一つ前に訪問した頂点を頂点sとして、4.を繰り返す
5. 頂点cがBlack Setに含まれていれば、4.における次の頂点へ
6. 頂点cがGrey Setに含まれていれば、cycleありとして探索終了
7. 5.,6.のいずれでもない(=頂点cがWhite Setに含まれる)場合は、3.から繰り返し
8. White Setが空になったら、cycleなしとして探索終了

※sはstartの意で命名(White Setから取り出す度に設定されるので厳密には始点ではないですが) ※cはcurrentの意で命名

例：cycleあり

2→4→5→2のcycleがある例です。

頂点0から上記のアルゴリズムを適用した場合のWhite Set、Grey Set、Black Setの変化を表にまとめると以下の通りです。

頂点	White Set	Grey Set	Black Set
-	0,1,2,3,4,5	-	-
0	1,2,3,4,5	0	-
1	2,3,4,5	0,1	-
3	2,4,5	0,1,3	-
1	2,4,5	0,1	3
4	2,5	0,1,4	3
5	2	0,1,4,5	3
2	-	0,1,2,4,5	3

最終行の時点で、頂点2がGrey Setに含まれるため、cycleありとなります。

例：cycleなし

上記の例から2→4の辺を除き、cycleをなくした例です。

こちらも先程と同様に、White Set、Grey Set、Black Setの変化を表にまとめます。途中までは一緒ですね。

頂点	White Set	Grey Set	Black Set
-	0,1,2,3,4,5	-	-
0	1,2,3,4,5	0	-
1	2,3,4,5	0,1	-
3	2,4,5	0,1,3	-
3	2,4,5	0,1	3
1	2,4,5	0,1	3
4	2,5	0,1,4	3
5	2	0,1,4,5	3
2	-	0,1,2,4,5	3
5	-	0,1,4,5	2,3
4	-	0,1,4	2,3,5
1	-	0,1	2,3,4,5
0	-	0	1,2,3,4,5
-	-	-	0,1,2,3,4,5

White Setを探索し終わったので、cycleなしとなります。

設計

隣接リスト

【Golang】DFS(深さ優先探索)による無向グラフのcycle detectを実装する - 逆さまにした同様に隣接リストで実装します。上記の例はそれぞれ以下のようにリストを持つことになります。

例：cycleあり

頂点	隣接リスト
0	1,2
1	3,4
2	4
3	-
4	5
5	2

例：cycleなし

頂点	隣接リスト
0	1,2
1	3,4
2	-
3	-
4	5
5	2

各Setをどうするか

White Set、Grey Set、Black Setをcolorという[]int型で実装することも考えましたが、有向グラフでは強連結でないグラフに対して扱いが難しくなりそうだったのでmapで実装します。 sliceとmapのdelete(+make)はどちらが速いのか - 逆さまにしたの結果が、無駄になってしまったのは残念ですが、Setと言っているのでmapのほうがわかりやすく実装できると考えて前に進むことにします。

実装

【Golang】DFS(深さ優先探索)による無向グラフのcycle detectを実装する - 逆さまにしたと同様に以下のようにGraphを定義します。

// Graph is a graph with n vertices and edges.
type Graph struct {
    n     int
    edges [][]int
}

コンストラクタも同様です。

// NewGraph creates a new graph with n vertices.
func NewGraph(n int) *Graph {
    g := &Graph{
        n:     n,
        edges: make([][]int, n),
    }
    return g
}

辺の追加

AddEdgeは、無向グラフと異なり、片方向にだけ辺を追加する点に注意です。

// AddEdge adds a edge connects vertex u to v and v to u.
func (g *Graph) AddEdge(u, v int) {
    g.edges[u] = append(g.edges[u], v)
}

DFSによるcycle detectの実装

基本的には、記事の先頭で述べたアルゴリズムを実装していくだけですが、White Setから頂点を選ぶ操作は以下のように実装しました。

c := -1
for c = range wSet {
  break
}

mapにはpopがないので、rangeでランダムに(mapに対するrangeは順序を保ちません)1つ取得し、breakしています。 これを踏まえた実装は以下です。

func dfs(c int, wSet, gSet, bSet map[int]struct{}, edges [][]int) bool {
    delete(wSet, c)
    gSet[c] = struct{}{}

    for _, n := range edges[c] {
        _, ok := bSet[n]
        if ok {
            continue
        }
        _, ok = gSet[n]
        if ok {
            return true
        }
        if dfs(n, wSet, gSet, bSet, edges) {
            return true
        }
    }

    delete(gSet, c)
    bSet[c] = struct{}{}
    return false
}

呼び出し側では、初期化も含めて行っています。

func (g *Graph) ExistsCycle() bool {
    wSet := make(map[int]struct{}, g.n)
    gSet := make(map[int]struct{}, g.n)
    bSet := make(map[int]struct{}, g.n)

    for i := 0; i < g.n; i++ {
        wSet[i] = struct{}{}
    }

    for len(wSet) != 0 {
        c := -1
        for c = range wSet {
            break
        }
        if dfs(c, wSet, gSet, bSet, g.edges) {
            return true
        }
    }
    return false
}

テスト

最後に上述の例で正しく動作することを試してみます。

例：cycleあり

頂点	隣接リスト
0	1,2
1	3,4
2	4
3	-
4	5
5	2

g := directed.NewGraph(6)
g.AddEdge(0, 1)
g.AddEdge(0, 2)
g.AddEdge(1, 3)
g.AddEdge(1, 4)
g.AddEdge(2, 4)
g.AddEdge(4, 5)
g.AddEdge(5, 2)

fmt.Println(g.ExistsCycle()) // true

例：cycleなし

頂点	隣接リスト
0	1,2
1	3,4
2	-
3	-
4	5
5	2

g := directed.NewGraph(6)
g.AddEdge(0, 1)
g.AddEdge(0, 2)
g.AddEdge(1, 3)
g.AddEdge(1, 4)
g.AddEdge(4, 5)
g.AddEdge(5, 2)

fmt.Println(g.ExistsCycle()) // false

References

• Detect Cycle in Directed Graph Algorithm
• Go言語 - enumを定義する
• 強連結成分分解の意味とアルゴリズム