최소 신장 트리 - Prim's Algorithm vs. KrusKal's Algorithm

1. Prim's Algorithm

2. Kruskal's Algorithm

3. Prim vs. Kruskal

 

1. prim's Algorithm

프림 알고리즘에 대한 설명은 아래 문제에 자세히 적어두었다.

https://potatoscatteringsmile.tistory.com/112

[백준 2024/02/13] 1922번 네트워크 연결

 

2. Kruskal's Algorithm

class DisjointSet:

    def __init__(self, n):
        self.parent = list(range(n + 1))

    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        self.parent[root_x] = root_y


def kruskal(n, edges) -> int:
    """
    n: 정점의 개수
    edges: (정점1, 정점2, 가중치)의 리스트
    """

    # 간선을 가중치 순으로 정렬
    edges.sort(key=lambda x: x[2])
    disjoint_set = DisjointSet(n)
    result = 0
    used_edges = 0

    # 가중치가 낮은 간선부터 선택
    for idx, adj, cost in edges:
        # 각 노드의 부모 노드 탐색
        # 사이클이 생기지 않는다면 간선을 선택
        # 부모 노드가 같다 = 이 간선을 선택하면 사이클이 생긴다!
        if disjoint_set.find(idx) != disjoint_set.find(adj):
            disjoint_set.union(idx, adj)
            result += cost
            used_edges += 1
            # 간선의 개수가 n - 1개가 되면 탐색 종료!
            if used_edges == n - 1:
                break

    return result

 

위에서 부터 하나씩 설명해보도록 할 것이다.

 

def __init__(self, n):
	self.parent = list(range(n + 1))

이 부분은 DisjointSet이 호출되었을 때, self.parent 라고 불리는 list를 만들어주는 것이다. 그 크기는 노드의 개수 + 1 이다.

+ 1을 해준 이유는, 노드가 1부터 시작할 경우에, index 0 번은 사용이 안되기 때문이다.

 

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

 

이는 부모노드를 찾아주는 코드이다.

만약 self.parent[x] 가 자기 자신이라면, 해당 노드가 부모 노드인 것이므로, x를 바로 return 해주었다.

아닐 경우엔, 자신의 부모 노드를 다시 find 함수에 넣는다. 이렇게 재귀적으로 불러와서, 자기 자신이 부모 노드인 노드까지 찾도록 한다.

 

ex) 

1의 부모 노드 2

2의 부모 노드 4

4의 부모 노드 6

6의 부모 노드 6 이라고 할 때, 

 

fins(1)이 들어갔다고 가정해보자,

 

우선 self.parent[1] == 1 이 아니기 때문에 if 문 안에 들어가지 못한다.

self.parent[1] 이 2 이기 때문에, self.find(2) 가 다시 들어가게 되고, ... 이걸 반복 하다보면 

6이 return 되게 된다.

 

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        self.parent[root_x] = root_y

 

union의 경우, root가 다를 때, 즉, 노드를 연결하고자 할 때 해당 노드들의 부모노드가 같아지도록 설정하는 방법이다.

둘 중 하나의 부모노드를 통일 시켜 준다. => self.parent[root_x] = root_y 를 하는 이유가 이것이다.

 

if root_x == root_y 를 왜 해주는 것인가 의문이 들기도 하였다. 왜냐하면 

kruskal 함수에서 if disjoint_set.find(idx) != disjoint_set.find(adj) 로 이미 같지 않음을 확인시켜주기 때문이다.

이는, disjointset.union을 kruskal 함수 뿐만 아니라, 다른 함수에서도 사용할 수 있도록 범용적으로 코딩이 되었기 때문이다.

 

    edges.sort(key=lambda x: x[2])

이후 오름차순으로 정렬시켜 준다.

 

 for idx, adj, cost in edges:
        # 각 노드의 부모 노드 탐색
        # 사이클이 생기지 않는다면 간선을 선택
        # 부모 노드가 같다 = 이 간선을 선택하면 사이클이 생긴다!
        if disjoint_set.find(idx) != disjoint_set.find(adj):
            disjoint_set.union(idx, adj)
            result += cost
            used_edges += 1
            # 간선의 개수가 n - 1개가 되면 탐색 종료!
            if used_edges == n - 1:
                break

    return result

sort를 완료하였기 때문에, for 문을 돌려서 간선이 적은 것부터 불러온다.

만약에 2개의 노드가 부모 노드가 다를 경우엔, cycle이 형성되지 않기 때문에 이어주기로 마음 먹는다.

 

이제 두 노드가 같은 부모 노드를 가지고 잇어야 하기 때문에, union_set.union(idx, adj) 로 같게 만들어 준다.

 

이후, cost를 더해주고, 사용한 edge 도 하나 증가해준다.

edge를 저장하는 이유는 사용한 edge 수가 n-1 (노드의 개수 -1) 이라면 모든 노드를 연결한 것이기 때문에 break로 탈출 시켜 준다.

 

3. Prim vs. Kruskal

<Prim Algorithm>

- 간선의 수가 많은 밀집 그래프에서 Kruskal 알고리즘 보다 더 효율적이다.

- 간선의 수가 많다면 Kruskal의 경우 모두 정렬해야하기 때문에 prim 이 더 효율적이다.

- 연결된 간선을 모두 검사해야하므로, 간선의 수가 적은 희소 그래프에서 비효율적이다. -> 간선의 수가 적다면, 이미 search를 완료해서 간선 대상 혹은 간선 대상이 아님을 이미 판별했음에도, 다른 노드에 가서 또 같은 노드에 대해 다시 판별해야 되기 때문이다.

즉, 간선의 수가 적으면, 이미 search 한 간선을 반복적으로 search 하게 되기 때문에 비효율적이다.

 

<Kruskal Algorithm>

- 간선의 수가 적은 희소 그래프에서 더 효율적이다. 왜냐하면 간선을 먼저 정렬해야하기 때문이다.

- 모든 간선을 검사해야하므로 초기 설정 시간이 더 걸릴 수 있다.

 

<결론>

- Prim 알고리즘 : 밀집 그래프에 더 효율적

- Kruskal 알고리즘 : 희소 그래프에서 더 효율적