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