Kruskal's Algorithm and Union-Find 크루스칼 알고리즘 파이썬 python

최소 비용 신장 트리를 만들기 위해 쓰이는 크루스칼 알고리즘.

일단 그래프에서 최소 비용인 엣지들을 오름차순으로 나열한다. 사이클을 만들지 않는 최소 비용인 엣지를 선택한다. 선택된 엣지가 노드의 총 개수 -1 이면 끝. 말은 쉽다. 그래도 말이 최소 비용 신장 트리지 복잡하게 트리를 만드는 과정은 없다. 배열로 끝낼 수 있다.

변의 개수 E, 꼭지점의 개수 N이라고 할 때 O(ElogV)의 시간 복잡도.

Union-Find를 알아야 한다. 두 노드가 같은 집합에 속하는 지를 판단하기 위해 쓰인다. Find로 각 노드가 어느 집합에 있는 지 확인, Union으로 각 집합을 합치기.

개선하기

Union:집합을 합칠 때, 두 집합 중 크기가 작은 것이 큰 집합에 붙는 것이 효율적이다.

Find:한 노드가 어느 집합에 속하는 지 판단하기 위해 부모를 거치며 루트를 찾는데, 이 때 2개씩 건너뛰면서 부모를 갱신하면 효율적이다.

모든 노드의 부모를 자기 자신이 되도록 한다. 1차원 배열을 쓰면 되는데 인덱스는 노드이고 값은 부모 노드이다.

parent=[0,1,2,3,4,5,6,7,8,9]

노드 4의 부모는 parent[4]이므로 4가 된다.

0	1	2	3	4	5	6	7	8	9
0	1	2	3	4	5	6	7	8	9

여기서 1과 2가 연결되면 parent배열은 다음과 같이 갱신된다.

0	1	2	3	4	5	6	7	8	9
0	1	1	3	4	5	6	7	8	9

2와 3이 연결되면? 1,2,3모두 같은 집합에 속하게 된다.

0	1	2	3	4	5	6	7	8	9
0	1	1	1	4	5	6	7	8	9

그렇다면 노드 3은 어떻게 1과 연결이 되는 건가?

find 함수로 2의 루트를 찾는다 -> 1.

find 함수로 3의 루트를 찾는다 -> 3.

루트가 다르다는 의미는 노드 2, 3이 다른 집합에 속한다는 의미이므로 union함수로 집합을 합칠 수 있다.

여기서 왜 집합의 크기가 큰 것에 작은 것을 붙여야 할까?

항상 참은 아니지만, 확률적으로 노드 수가 적은 것의 트리의 높이가 낮기 때문에, 트리의 높이를 낮추는 데 효과적이다. 트리의 높이를 낮추는 이유는 선택된 노드가 어떤 집합에 속하는 지를 해당 집합의 루트로 알 수 있는데, 높이가 낮을 수록 각 노드에서 루트까지 가는 데 시간이 적게 걸리기 때문이다.

find 대신 함수명으로 getParent...

def getParent(u):#u가 속한 집합의 루트 찾기
    while parent[u]!=u:#집합의 루트가 아니라면 반복.
        parent[u]=parent[parent[u]]#집합의 루트를 찾기 위해 2개씩 건너 뛰면서 부모 갱신
        u=parent[u]#2개 건너 뛴 부모를 자기 자신으로 갱신
    return u#루트를 찾았다면 루트 반환

find함수(getParent)를 실행할 때 입력 노드 x의 <부모의 부모>가 다시 x가 되면서 루트까지 올라가는데 결국 높이가 줄어들게 된다.

노드의 개수 -1만큼 반복하면서 두 노드가 같은 집합에 있는지 isSameSet으로 확인하고 같은 집합이라면 continue, 다른 집합에 속해있다면 union을 해준다.

sum=0#최소 비용 신장 트리에 의한 비용의 총 합
for i in range(0,n):#비용이 가장 작은 것부터 union_find
    if isSameSet(N_E_[i][1],N_E_[i][2]):
        continue
    else:
        union(N_E_[i][1],N_E_[i][2])
        print('사이클을 만들지 않는 최소 비용:',N_E_[i][0])
        sum+=N_E_[i][0]

def isSameSet(u,v):#노드 u,v가 같은 집합에 속하는지 판단
    global x,y
    x=getParent(u)
    y=getParent(v)
    if x==y:
        return True
    else:
        return False

각 집합에 속한 노드의 총 개수를 파악하기 위해 size라는 배열을 쓴다. 각 노드의 부모가 자기 자신인 parent 배열이 있었는데 이 배열과 비슷하게 인덱스는 각 노드가 속한 집합을 가리키고, 값은 그 집합에 있는 노드의 개수를 의미한다.

def union(u,v):#큰 트리에 작은 트리를 넣는다.
    if size[x]>size[y]:#y 집합이 작다면
        parent[y]=x#y집합의 루트를 x집합의 루트로.
        size[x]+=size[y]#큰 집합의 노드 수에 작은 집합의 노드 수 합치기
    else:
        parent[x]=y
        size[y]+=size[x]

최종 Kruskal's Algorithm Code - 다른 코드들은 이해가 안가서 최대한 간단하게 최적화해서 만듦.

N_E_=[ #connected nodes and weight for each edges.
    [12,1,7],
    [28,1,4],
    [67,1,2],
    [17,1,5],
    [24,2,4],
    [62,2,5],
    [20,3,5],
    [37,3,6],
    [13,4,7],
    [45,5,6],
    [73,5,7]
]
n=len(N_E_)
nodes=7#노드의 총 갯수
parent=[i for i in range(0,nodes+1)]#각 노드(i번째 인덱스)는 i의 부모를 갖도록 초기화.
print('초기에 각 노드가 속하는 집합',parent)
size=[1]*n#트리의 높이를 낮게 만들기 위한 배열
N_E_.sort()
print('비용을 기준으로 정렬된 Nodes for Edge',N_E_)
x=0
y=0
def getParent(u):#u가 속한 집합의 루트 찾기
    while parent[u]!=u:#집합의 루트가 아니라면 반복.
        parent[u]=parent[parent[u]]#집합의 루트를 찾기 위해 2개씩 건너 뛰면서 부모 갱신
        print('p',parent[u])
        u=parent[u]#2개 건너 뛴 부모를 자기 자신으로 갱신
    return u#루트를 찾았다면 루트 반환
def union(u,v):#큰 트리에 작은 트리를 넣는다.
    if size[x]>size[y]:#y 집합이 작다면
        parent[y]=x#y의 루트를 x집합의 루트로.
        size[x]+=size[y]#큰 집합에 작은 집합 합치기
    else:
        parent[x]=y
        size[y]+=size[x]
def isSameSet(u,v):#노드 u,v가 같은 집합에 속하는지 판단
    global x,y
    x=getParent(u)
    y=getParent(v)
    if x==y:
        return True
    else:
        return False
sum=0#최소 비용 신장 트리에 의한 비용의 총 합
for i in range(0,n):#비용이 가장 작은 것부터 union_find
    if isSameSet(N_E_[i][1],N_E_[i][2]):
        continue
    else:
        union(N_E_[i][1],N_E_[i][2])
        print('사이클을 만들지 않는 최소 비용:',N_E_[i][0])
        sum+=N_E_[i][0]
print('각 노드가 속하는 집합:',parent)
print('비용 합:',sum)

출처는 

https://www.youtube.com/watch?v=i4ZDgJS0_yM

https://www.youtube.com/watch?v=Z_ug3JRxu2s

https://www.youtube.com/watch?v=_ocho3EzDH4