[アルゴリズム]Union-Findアルゴリズム
2948 ワード
Union Findアルゴリズム
union-find(アセンブリを探す)アルゴリズムはdisjoint set(才集合)とも呼ばれる.
コンセプト
Union
2つの要素の集合を1つの集合に結合する演算.
Find
2つの要素が同じグラフィックに属するかどうかを決定する演算.
インプリメンテーション
1.初期化
各ノードの親ノードをノード番号に初期化
parent = []
for i in range(n+1):
parent.append(i)2.親ノードの検索
親ノードを再帰的に検索します.=>親ノードと現在の自身のノードを返すと、そのノードが親ノードであることを示します.したがって、直接戻ります.そうしないと、要素の値を使用して親ノードの値が再帰的に検索されます.
def get_find(parent, x):
if parent[x] != x:
return get_find(parent, parent[x])
return x
3.連結演算
親が一緒にいるときは、普通はもっと小さい値に行きます.
def union_parent(parent,a,b):
a = get_find(parent,a)
b = get_find(parent,b)
if a < b :
parent[b] = a
else :
parent[a] = b4.find演算
2つのノードが同じグラフィックに属しているかどうかを確認します.
def find_parent(parent,a,b):
a = get_find(parent,a)
b = get_find(parent,b)
if a == b:
return 1
else:
return 0改良されたfind演算
上の図に示すように、5番目のノードの親ノードを探すには、5->4->1のプロセスがかかります.非常に長いツリー構造でleafノードの親ノードを検索すると、非常に効果的ではありません.
上記のように変更すると、ルートノードをより迅速に決定できます.
def get_find(parent, x):
if parent[x] != x:
return get_find(parent, parent[x])
return parent[x]ループ判別法
Union findアルゴリズムを使用して、グラフィックの周期を判別できます.
1-1本のノードが異なる場合は=>Union操作
1～2個のルートノードが同じ場合、=>ループ
すべての幹線に対して1回の
for i in range(e):
a, b = map(int, input().split())
if find_parent(parent, a, b):
cycle = True
break
else:
union_parent(parent, a, b)備考ブログ1
備考ブログ2
備考ブログ3
Reference
この問題について([アルゴリズム]Union-Findアルゴリズム), 我々は、より多くの情報をここで見つけました https://velog.io/@yujin1760/알고리즘Union-Find-알고리즘テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol