Union-Find 알고리즘 (Union-Find Algorithm)

Union-Find 알고리즘 (Union-Find Algorithm)

1. 개념

대표적인 그래프 알고리즘

합집합 찾기 알고리즘

서로소 집합 알고리즘

여러 개의 노드가 존재할 때 두개의 노드를 선택해서 이 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘

같은 그래프에 있다는 것은 부모 노드가 같고, 서로 연결되있음을 의미한다.

2. 알고리즘

3가지 개념이 합쳐져 Union - Find 알고리즘을 만들 수 있다.

1) 부모를 찾기 -> getParent

2) 노드를 같은 그래프에 합치기 ->unionParent

3) 부모 노드 찾기 ->findParent

3.코드

1) getParent

def getParent(cost, a): if cost[a] == a: return a return cost[a] = getParent(cost, cost[a])

a의 부모 노드만 보고 한번에 파악할 수 없기 때문에 재귀함수를 이용한다.

2) unionParent

def unionParent(cost, a,b): a = getParent(cost,a) b = getParent(cost,b) if a < b: cost[b] = a else: cost[a] = b

a 노드와 b노드를 같은 그래프에 합치려면 각각의 부모노드를 구한 후 더 작은 부모 노드를 각자의 부모 노드로 설정한다.

3) findParent

def findParent(cost, a, b): a = getParent(cost, a) b = getParent(cost, b) if a == b: return 1 else return 0

a노드와 b노드가 같은 그래프에 속해있는지 확인하는 함수입니다. a노드와 b노드가 같은 그래프에 있다는 건 부모노드가 같다는 걸 의미합니다.

from http://vhrlgkwlak.tistory.com/66 by ccl(A) rewrite - 2021-09-06 00:26:29