Cycle in Undirected Graph Graph Algorithmを視聴したので、Disjoint set algorithmによるcycle detect実装してみます。
Disjoint set algorithmでは、以下3つの操作を使うことでcycle detectを行います。
- MakeSet
- 各nodeだけの集合を作る(初期化)
- Union
- 2つの集合を結合する
- FindSet
- edgeを入力に、そのedgeの両端のnodeが含まれる集合を返す
Algorithm
アルゴリズムは以下となります。
- MakeSetにより、各nodeの集合を作る
- edgeを順番に選ぶ
- FindSetにより、2.で選んだedgeの両端のnodeが含まれる集合を見つける
- 3.で見つけた2つの集合が同じか、異なるかを判定する
- 同じ: cycleあり
- 異なる かつ 全edgeを探索終了: cycleなし
Cycle in Undirected Graph Graph Algorithmの動画では、図を交えた説明がされているので、詳しくは動画を御覧ください。
実装
本体だけ抜き出すと実装は以下のようになります。
func DisjointSetAlgorithm(g *graph) bool { d, err := g.NewDisjointSet() if err != nil { panic(err) } for _, e := range g.GetEdges() { F, T := d.FindSet(e) if F.Equal(T) { return true } d = d.Union(F, T) } return false }
FindSet
やUnion
の実装はこちら