【Golang】Disjoint-set algorithmによる無向グラフのcycle detectを実装する

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

アルゴリズムは以下となります。

  1. MakeSetにより、各nodeの集合を作る
  2. edgeを順番に選ぶ
  3. FindSetにより、2.で選んだedgeの両端のnodeが含まれる集合を見つける
  4. 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
}

FindSetUnionの実装はこちら

References