前回のDisjoint-set algorithmに引き続き、Cycle in Undirected Graph Graph AlgorithmのDFSによるcycle detect実装してみます。
前回は、自作のgraphパッケージを使いましたが、グラフの持ち方(データ構造)も検討しながらまとめたいと思います。
DFSによるcycle detectのアルゴリズム
まずDFSによるcycle detectを行うアルゴリズムの概要についてです。 DFSは、Depth-First Searchの略で、その名の通り深さ優先探索によってcycle detectを行います。 アルゴリズムは以下になります。
- 入力となる始点(頂点)
sに対して、現在訪れている頂点cをsとする - 頂点
cが訪問済みか確認する（訪問済みならcycleありを返して終了。未訪問なら後続のステップへ） - 頂点
cを訪問済みにする - 頂点
cに接続する頂点を順に訪れる
以下、2.から繰り返し
※cはcurrentの意で命名
すべての頂点の探索が終了すればcycleなしとして探索終了です。
例：cycleあり
以下の例でイメージを掴んでみましょう。
まず始点sを頂点0とします。各頂点からの接続されている頂点への移動は、一つ前の頂点以外である必要があります。ここではわかりやすいように、一つ前の頂点以外で最も値が小さい頂点に移動するとしましょう。
移動を表にまとめると以下のとおりです。
| 頂点c | 訪問済みの頂点 |
|---|---|
| 0 | 0 |
| 1 | 0,1 |
| 3 | 0,1,3 |
| 0 | 0,1,3 |
頂点3から頂点0に移動した時点でステップ2.の確認で頂点0(太字)が訪問済みであるため、cycleあり となります
例：cycleなし
先程の例から辺1-3を削除したものを考えてみます。
先程と同様に始点sを頂点0とし、移動を表にまとめると以下のとおりです。
| 頂点c | 訪問済みの頂点 |
|---|---|
| 0 | 0 |
| 1 | 0,1 |
| 2 | 0,1,2 |
| 3 | 0,1,2,3 |
すべての頂点を探索しても訪問済みの頂点がなかったため、cycleなし となります
設計
データ構造をどうするか
グラフのデータ構造といえば、隣接リストと隣接行列ですが、上記の例で考えたように次に訪れる頂点さえわかればよいので隣接リストを採用します。 上記の例では以下の表のようにグラフを保持します。
例：cycleあり
| 頂点 | 隣接する頂点 |
|---|---|
| 0 | 1,2,3 |
| 1 | 0,3 |
| 2 | 0 |
| 3 | 0,1 |
例：cycleなし
| 頂点 | 隣接する頂点 |
|---|---|
| 0 | 1,2,3 |
| 1 | 0 |
| 2 | 0 |
| 3 | 0 |
sliceかmapか
Goには、リストを扱うパッケージcontainer/listがありますが、Golangのcontainer/listでスタックとキューによるとsliceのほうが速いようです（自分でベンチマークは取っていないですが）。 sliceとmapのどちらで隣接リストを持つか決めるために、Golangのmapとsliceはどちらが速いのか - 逆さまにしたでベンチマークを測定した結果、要素の探索を行わないのであれば、sliceが有利でした。 また、グラフ探索アルゴリズムとその応用にも以下のように書かれていますが、隣接行列ではなく、隣接リストを採用する場合、対象とするグラフのEdgeが少ないことを期待します。
疎グラフに対して、高速・省メモリ
Golangのmapとsliceはどちらが速いのか - 逆さまにしたのベンチマークでは、要素数による違いを実感することはできませんでしたが、GoのパフォーマンスTipsメモに以下のように書かれており、上述の通り、グラフのEdge数(=要素数)は、少ないことを期待し、sliceを採用することにします。
100要素超えくらいからmapのアクセス速度一定の恩恵が発揮される。
頂点の数は予め与えられることとして、以下のように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 }
辺の追加
GraphにAddEdgeを生やします。
// AddEdge adds a edge connects vertex u to v and v to u. func (g *Graph) AddEdge(u, v int) { g.edges[v] = append(g.edges[v], u) g.edges[u] = append(g.edges[u], v) }
今回は省略しますが、できれば以下をエラーチェックしたほうがよいでしょう。
uとvが同一頂点でないこと- 初期化の頂点に含まれていないこと
DFSによるcycle detectの実装
DFSの実装には、スタックを用いた実装と再帰を用いた実装がありますが、再帰のほうがコードがシンプルになることが多いので、再帰で実装することにします。 アルゴリズム自体は冒頭に書いた通りですが、実装のポイントを以下です。
- 訪問済みの頂点を
visitedとし、mapで持つ
→ Golangのmapとsliceはどちらが速いのか - 逆さまにしたでベンチマークを取った通り、探索まで含めるとsliceだと遅くなってしまいます。今回は、訪れた頂点が 既に訪問済みか を確認したいのでmapにします。set型がないGoでは、mapを用いてset型の代わりのデータ構造を実装することがありますが、この時、strct{}がGo上ではサイズ0となることからmap[int]strct{}として実装するのがよいです。
- 一つ前の頂点には戻らない
→ 直前にいた頂点に戻るようなDFSの実装にしてしまうと、visitedがtrueを返すので、2頂点目を訪れた時点で(falseを返すべきなのに)trueを返して終了です。直前の頂点をp(parentを意識した命名)として実装します。
上記2点を踏まえた実装は以下です。
func dfs(p, c int, edges [][]int, visited map[int]struct{}) bool { _, ok := visited[c] if ok { return true } visited[c] = struct{}{} for _, v := range edges[c] { if v == p { continue } return dfs(c, v, edges, visited) } return false }
dfsをGraph型の変数からメソッドとして呼び出せるように以下のように実装します。
func (g *Graph) ExistsCycle() bool { return dfs(-1, 0, g.edges, map[int]struct{}{}) }
ここで、pは直前に訪れた頂点がないためdfs()中のv == pがfalseになるようにp = -1としています。さらに探索を開始する頂点(冒頭のアルゴリズムにあるs)は、どこでもいいので、s = 0から始めています。
テスト
上記の例で正しく動作することを試してみます。
例：cycleあり
| 頂点 | 隣接する頂点 |
|---|---|
| 0 | 1,2,3 |
| 1 | 0,3 |
| 2 | 0 |
| 3 | 0,1 |
g := undirected.NewGraph(4) g.AddEdge(0, 1) g.AddEdge(0, 2) g.AddEdge(0, 3) g.AddEdge(1, 3) fmt.Println(g.ExistsCycle()) // true
例：cycleなし
| 頂点 | 隣接する頂点 |
|---|---|
| 0 | 1,2,3 |
| 1 | 0 |
| 2 | 0 |
| 3 | 0 |
g := undirected.NewGraph(4) g.AddEdge(0, 1) g.AddEdge(0, 2) g.AddEdge(0, 3) fmt.Println(g.ExistsCycle()) // false