프림 알고리즘 vs 크루스칼 알고리즘

신장 트리(spanning tree)

 

그래프에서

1. 모든 정점을 포함하고

2. 정점간 서로 연결되면서 사이클이 존재하지 않는 그래프 ( 이 조건은 트리 조건 )

즉, 모든 정점을 포함하는 트리를 신장 트리라 한다.

 

아래 정점이 3개로 연결된 그래프에서 신장트리는 몇개일까?

3개 이다.

간선에 가중치가 있을 경우,

신장트리 3개 중에 값의 합이 최소인 것이 최소 비용 신장트리이다.

 

최소비용 신장 트리를 구하는 방법?

 

프림 알고리즘.

 

정점 선택 기반 알고리즘

정점을 하나 선택한 후, 정점에 연결된 간선 중 가장 가중치가 작은 간선을 선택한다.

 

visit 함수 초기화, 덱이 비어있을때 까지 반복
덱에 첫번째 정점을 넣고 반복문 시작
pq에 해당 정점의 모든 간선을 집어넣는다.
pq에서 정점하나를 뽑아 방문했던 노드면 스킵한다.
해당 정점을 덱에 넣고 visit=True

 

예시

from collections import defaultdict
import heapq

def get_mst_by_prim(graph, start_vertex):
    
    mst     = defaultdict(set)
    visited = set()
    edges   = []
    
    # first init
    visited.add(start_vertex)
    for to, cost in graph[start_vertex].items():
        heapq.heappush(edges, (cost, start_vertex, to))

    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst[frm].add(to)
            
            for to_next, cost in graph[to].items():
                if to_next not in visited:
                    heapq.heappush(edges, (cost, to, to_next))

    return mst

example_graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1, 'D': 1, 'E': 4},
    'C': {'A': 3, 'B': 1, 'F': 5},
    'D': {'B': 1, 'E': 1},
    'E': {'B': 4, 'D': 1, 'F': 1},
    'F': {'C': 5, 'E': 1, 'G': 1},
    'G': {'F': 1},
}

mst = get_mst_by_prim(graph, 'A')
print(mst)
# {'A': set(['B']),
#  'B': set(['C', 'D']),
#  'D': set(['E']),
#  'E': set(['F']),
#  'F': set(['G'])}

 

크루스칼 알고리즘

 

간선 리스트를 가중치에 따라 오름차순으로 정렬한다음 하나씩 뽑는다. 두 정점이 연결되어 있지 않다면 두 정점을 union해서 연결한다.

 

이 때 연결은 단순히 인접한다는 뜻이 아니다. 위의 네트워크 연결처럼 이어져있다는 뜻, 즉 서로소집합의 개념에서 같은 집합이라는 뜻이다.

 

이 때, 각 정점들이 같은 연결상황(집합)에 속하는지 판별하고 합치는 과정에서 서로소집합의 개념이 사용된다.

 

프림 vs 크루스칼

 

프림의 알고리즘 시간 복잡도는 $ O(n^{2}) $ 이다.

크루스칼 알고리즘의 시간 복잡도는 $ O(elog_{2}e )$ 이다.

 

따라서, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우에 크루스칼 알고리즘이 적합하고

그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)의 경우는 프림 알고리즘이 적합하다.

 

 

https://bradfieldcs.com/algos/graphs/prims-spanning-tree-algorithm/

Prim’s Spanning Tree Algorithm

https://mattlee.tistory.com/46

<prim의 mst="" 알고리즘=""> 기본개념과 알고리즘</prim의>