[Coding Test][Python][Shortest Path] Kruskal 알고리즘 개념 및 예제, Union - Find 자료구조

 

 

1. Kruskal 알고리즘이란?

그래프의 Minimum Spanning Tree(MST, 최소 신장 트리) 를 구하는 대표적인 알고리즘입니다.

Minimum Spanning Tree란 그래프의 모든 Vertex가 연결하면서 Edge의 Weight의 합이 최소가 되는 Tree를 의미합니다.

알고리즘 특징

• Edge를 중심으로 접근하여 MST를 구성
• Greedy 알고리즘 사용
• Undirected Weighted Graph에 적용가능
• 시간 복잡도 : $O(E log E)$

2. Kruskal 알고리즘 동작 과정

위의 그래프에서 Kruskal 알고리즘을 적용해보겠습니다.

1) 모든 Edge를 가중치가 작은순으로 정렬

Edge의 Weight가 작은 순으로 정렬한 후 가장 작은 Weight를 가진 Edge를 선택합니다.

2) 정렬된 Edge를 차례대로 선택하면서 MST에 추가

이 때, 선택된 Edge를 MST에 추가할 때 Cycle이 발생하지 않는지 확인해야합니다.

 

정렬된 Edge를 차례대로 선택합니다.

 

이 때, 다음 최소 Weight를 가진 Edge는 Vertex 5번과 Vertex 8번을 잇는 Edge인데, 이를 MST에 포함시키면 Cycle이 발생하게 됩니다.

MST는 Tree이기 때문에 절대 Cycle이 생겨서는 안됩니다.

따라서, Kruskal 알고리즘에서 가장 중요한 것은 Edge를 MST에 추가할 때 Cycle이 생기는지 안생기는지 판별을 하는 것입니다.

이를 위해서는 Union - Find 자료구조을 적용해서 해결할 수 있습니다.

(Union - Find 자료구조에 대해서는 글 마지막에 적어두었습니다.)

 

특정 Edge를 선택했을 때, 선택된 Edge의 두 Vertex에 대해 Find 연산을 수행하여 Parent(Root)가 같은지 확인합니다. 이 때, Parent가 같다면 Cycle이 발생하는 것이므로 MST에 포함시켜서는 안됩니다.

두 Vertex의 Parent가 같지 않다면 Cycle이 발생하지 않는 것이므로 두 Vertex에 대해 Union 연산을 수행하고, 해당 Edge를 MST에 추가합니다.

 

정리하자면, Kruskal 알고리즘은 Edge의 Weight가 작은 것부터 순서대로 추가합니다. 이때 추가하려는 Edge의 두 Vertex에 Find 연산을 수행한 후 Cycle이 발생하지 않는다면 Union 연산을 수행 후 MST에 추가합니다.

3) 모든 Vertex가 연결될 때까지 반복

3. Kruskal 알고리즘 구현

위 그림에 대해서 Kruskal 알고리즘을 수행해보겠습니다.

1) Edge 초기화 및 정렬

V, E = 9, 13
edges = [
    [1, 2, 12],
    [1, 3, 13],
    [2, 3, 11],
    [2, 5, 8],
    [3, 4, 5],
    [3, 6, 3],
    [4, 5, 2],
    [5, 7, 7],
    [5, 8, 6],
    [6, 8, 1],
    [7, 8, 14],
    [7, 9, 9],
    [8, 9, 10]
]

# Edge의 Weight가 작은 순으로 정렬
edges.sort(key=lambda x : x[2])

2) Union - Find 자료구조 정의

parent = [i for i in range(V+1)]
def find(x):
    if parent[x] == x:
        return x
    return find(parent[x])

def union(x, y):
    x, y = find(x), find(y)

    if x != y:
        parent[x] = y

 

자료구조이므로 Class로 정의하는데 더 깔끔하여 Class로 정의하였습니다.

class UnionFind():
    def __init__(self, V):
        self.parent = [i for i in range(V+1)]

    def find(self, x):  
        if self.parent[x] == x:
            return x
        return self.find(self.parent[x])

    def union(self, x, y):
        parent_x, parent_y = self.find(x), self.find(y)

        if parent_x != parent_y:
            self.parent[parent_x] = parent_y

 

3) Kruskal 알고리즘 정의

Function으로 Union - Find를 정의한 Kruskal 알고리즘입니다.

def kruskal(edges):
    MST = []
    total_weight = 0

    # Weight가 작은 Edge부터 선택(정렬된 상태의 Edges)
    for edge in edges:
        u, v, weight = edge
        if find(u) != find(v):
            union(u, v)
            MST.append(edge)
            total_weight += weight
            
            if len(MST) == V-1:
                break
            
    return MST, total_weight

 

Class로 Union - Find를 정의한 Kruskal 알고리즘입니다.

def kruskal(edges):
    uf = UnionFind(V)

    MST = []
    total_weight = 0

    # Weight가 작은 Edge부터 선택(정렬된 상태의 Edges)
    for edge in edges:
        u, v, weight = edge
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            MST.append(edge)
            total_weight += weight
            
            if len(MST) == V-1:
                break
    return MST, total_weight

 

4) Kruskal 알고리즘 실행

MST, total_weight = kruskal(edges)
print(MST)
print(total_weight)

[[6, 8, 1], [4, 5, 2], [3, 6, 3], [3, 4, 5], [5, 7, 7], [2, 5, 8], [7, 9, 9], [1, 2, 12]]
47

 

---

※ Union - Find 자료구조

1. Union Find 자료구조란 ? 

여러 개의 원소가 있고, 여러 개의 집합이 있을 때, 특정 원소가 어떤 집합에 속해있는지(Find) 확인하고, 특정 집합을 합칠 때(Union) 사용하는 자료구조입니다. Disjoint Set(서로소 집합)이라고도 합니다.

• Union : 두 개의 집합을 하나의 집합으로 만드는 연산
• Find :특정 원소가 어떤 집합에 속해 있는지 찾는 연산(집합의 root를 찾는 연산)

2. 특징

• 집합들이 서로 중복되지 않으며, 집합 간 교집합이 없는 상태로 관리
• Cycle 판별, 연결성 확인 등에 사용
• 최적화 된 경우 연산당 시간복잡도가 거의 $O(1)$에 가깝게 동작

3. 동작 과정

1) 자기 자신이 root가 되도록 초기화

먼저 서로 연결 되어있지 않은 상황으로, 초기 배열의 값은 자기 자신입니다.(전부 다른 집합)

2-1) Union 연산

Union 연산을 통해 두 Node가 같은 집합에 속해있음을 나타낼 수 있습니다.

아래 그림은 Union(1, 3), Union(5, 6)을 수행한 그림입니다.

이렇게 Union 연산을 통해 두 Node를 합치게 되면 uf 배열의 값은 같은 집합인 것을 나타낼 뿐만 아니라, 실제 Node가 가리키고 있는 Parent Node의 번호도 됩니다.

 

이 상황에서 Union(5, 1)을 하게 되면 연산 과정이 조금은 달라집니다.

우선, 두 Node의 Parent Node를 따라 올라 갈 수 있는데 까지 계속 올라가야 합니다.(Find 연산)

이렇게 두 Node의 Parent Node를 찾으면 Node 5의 Parent인 uf[6]에 Node 1의 Parent 인 Node 3을 넣어주어 Union 연산을 수행하게 됩니다.(즉, Node 6의 Parent 가 Node 3)

 

 

Union 연산 코드입니다.

def union(X, Y):
	parent_X, parent_Y = find(X), find(Y)
    uf[parent_X] = parent_Y

2-2) Find 연산

앞서 Union 연산에서 잠깐 설명 했듯이, 각 Node의 최종 Parent node를 찾는 연산입니다.

 

아래 그림에서 Find(5)를 수행하면 Node 3을 찾아야 합니다.

그렇다면 구현은 아래와 같이 합니다.

x로 시작하여서 uf[x]를 계속 올라가다가, 더 이상 올라갈 곳이 없다면 ($uf[x] == x$) x의 값을 반환하면 됩니다.

 

Find 연산 코드입니다.

def find(X):
	if uf[X] == X:
    	return X
    return find(uf[X])

 

전체 코드입니다.

N = 8
parent = [i for i in range(N+1)]


def find(X):
    if parent[X] == X:
        return X
    
    return find(parent[X])

def union(X, Y):
    X, Y = find(X), find(Y)
    parent[X] = Y


union(1, 3)
union(5, 6)
union(5, 1)
print(parent[1:])
print(find(5))

[3, 2, 3, 4, 6, 3, 7, 8]
3