問題タブ [disjoint-sets]

アルゴリズム:

グラフ:

(1)------(2)

隣接リスト:

[1] -> [2]

[2] -> [1]

素集合:

{{1}、{2}}

反復 1 :

エッジ e = (1, 2)

ユニオン(1, 2)

素集合 = {{1, 2}}

反復 2 :

エッジ e = (2, 1)

2 と 1 の両方が同じセットに属しているため、アルゴリズムはサイクルを検出します。グラフにサイクルが含まれていないことは明らかです。

このアルゴリズムは、有向グラフに対して問題なく機能します。この分析を手伝ってください。

サイクルとフォレストを持つ有向グラフの効率的なUnion-Find (別名Disjoint Set ) データ構造を探しています。このようなグラフが与えられた場合、次のクエリに答えたいと思います。G

1. vからノードに到達できますuか?
2. 到達できないノードuはどれですか?

単一の「ソース」ノードの場合、 DFS検索をu実行して、そこから到達できるかどうかを確認できます。1 回の DFS 検索の上限コストは、最悪の場合 です。ここで、とは、それぞれグラフ内の頂点とエッジの数です。ただし、私はそのような「ソース」ノードを多数持っており、すべての「ソース」ノードから個別に DFS を実行するよりも優れたアプローチがあるかどうか疑問に思っています (最悪の場合、上限コストはです)。vm + nmnmm * (m + n)

これらの質問の両方は、有向グラフの Union-Find データ構造によって効率的に回答できるようです。驚いたことに、かなりのオンライン検索を行っても解決策が見つかりませんでした。問題を間違った方向に考えていますか？

この答えを見つけましたが、理解できませんでした。