Kruskal 알고리즘(MST) / Union-Find

크루스칼 알고리즘(Kruskal)

탐욕적인 방법(Greedy Method)를 사용한다. 네트워크의 모든 정점을 최소 비용으로 연결하는 것이 목표이다. 

• 최소 비용의 간선으로 구성한다.
• 사이클을 포함하지 않는다.

흔히 말해 "최소 신장 트리(MST)를 찾는 알고리즘"이라고 한다.  여기서 신장 트리란 무엇일까.

 

신장트리(Spanning Tree) 

신장트리

예를 들어 G1이라는 연결 그래프가 있다고 할 때, 4개의 정점으로 이루어져 있다. 네 개의 정점을 잇는 것이 목표이지만, 사이클을 형성하면 안 된다. 

 

다시 크루스칼 알고리즘으로 넘어가서, 그러면 크루스칼 알고리즘은 최소 신장 트리를 찾는다고 했는데 대체 뭘까. 바로 신장 트리의 조건을 지키면서도, 최소한의 비용으로 신장 트리를 만드는 것을 목적으로 하는 것이다.

 

알고리즘의 동작 과정

1. 간선 데이터를 오름차순으로 정렬한다.
2. 간선을 하나씩 확인한다. 이때, 현재의 간선이 사이클을 만드는지 확인한다.
   • 만약 사이클이 발생한다면, 최소 신장 트리에 포함하지 않는다.
   • 만약 사이클이 발생하지 않는다면, 최소 신장 트리에 포함한다.
3. 모든 간선에 대해서 계속 반복한다.

크루스칼 알고리즘은 계속 강조되고 있는 부분이지만, 사이클이 발생하지 않는지에 대해 정말 민감하게 반응한다. 그러므로 반드시 지켜줘야 한다! 그러면 사이클이 발생하는지는 어떻게 판별할까? 이건 Union-Find 알고리즘을 통해 찾아낼 수 있다.

 

Union Find 알고리즘

사이클이 발생하는지를 확인하기 위해 kruskal에서 많이 사용하는 알고리즘이다. 두 노드가 같은 그래프에 속해있을 때, 이를 연결하면 사이클이 발생한다.

 

그래프 안에서 연결된 수들끼리 집합을 구성한다. 그리고 그 집합 안에서 가장 작은 값을 가진 노드를 대표자로 정한다. 그래서 대표자를 통해 집합을 구분할 수 있도록 한다. 예를 들어 대표자가 2명이라면 그래프도 2개, 대표자가 3명이라면 그래프도 3개인 것이다.

 

Union

만약 집합이 만들어지지 않은 노드들만 있을 경우에는 더 작은 쪽으로 노드들을 합쳐준다. 그 집합 안으로 들어가면, 각각의 노드들은 대표자를 가리킨다. 

 

Find

두 개의 부모 노드를 비교한 후에, 현재 같은 집합에 속하는지 확인하는 알고리즘이다. 대표자를 보고, 내 집합의 대표자를 찾아가는 과정이라고 생각하면 쉽다.

 

함수 구성

• getParent #부모 노드를 찾는 함수
• unionParent #두 부모 노드를 합치는 함수
• findParent #같은 부모를 가지는지 확인하는 함수

 

코드

#부모를 자기 자신으로 초기화
parent =[i for i in range(n+1)]

#parent[x] = x의 부모
#x의 부모가 자기 자신이 아니라면, findP를 호출하여 x의 부모를 찾는다.
#재귀적으로 부모를 탐색
def getParent(x):
    if parent[x] != x:
        return findParent(parent, parent[x])

#두 원소가 속한 집합의 대표 원소를 찾아서 합치는 함수
def unionParent(a,b):
    a=getParent(a)
    b =getParent(b)
    if a<b:
        parent[b] =a
    else:
        parent[a]=b

#원소가 같은 집합에 속하는지 찾는 함수, True or False 반환
def sameParent(a,b):
    return getParent(a) == getParent(b)
    
#사이클이 발생하는지 판별하는 함수
def hasCycle(edges):
	for edge in edges:
    #간선에서 두 노드를 a,b에 할당한다
    	a,b = edge
        #a,b가 같은 집합에 속한다면 사이클이 형성된다.
        if sameParent(a,b)
        	return True #종료!
        #사이클이 발견되지 않았으니, union 호출 후 a,b가 속한 집합을 합친다.
        unionParent(a,b)
    #사이클이 발견 안 되면 False반환
    return False