[알고리즘] 파이썬 프림(prim) & 크루스칼(kruskal) 예제 및 비교

MST(최소신장트리) 문제를 위한 프림 & 크루스칼 알고리즘

- 프림과 크루스칼은 MST(최소 신장 트리) 문제 해결을 위한 알고리즘이다. 

- MST(최소 신장 트리)란 그래프에서 모든 노드를 연결할때 간선의 가중치 합이 최소가 되는 경우를 말한다.   

- 최단 경로 문제와 다른 점은 한 노드에서 다른 모든 노드까지의 거리가 최소가 되는 것이 아니라, 모든 노드를 연결했을 때 최소가 되는 경우를 찾는 것이다.   

- 따라서 특정 노드에서 다른 노드로 가는 간선이 local minimum은 아닐 수 있지만, 결국 global minimum을 위한 것이다.

 

프림(prim) 알고리즘?

- 시작노드를 선정하여 시작노드부터 확보된 모든 간선 중 순환을 피해 최소 간선을 연결하는 방식.

- 모든 노드가 직접 연결되지 않아도 되고 한번만 방문하면 되기 때문에 visited 관리를 잘 해줘야한다.

- 아래 애니메이션에서 B → A →D→ C →E→F 순으로 노드를 방문한다. 

프림 애니메이션 ( 출처 : 위키 )

 

 

프림(prim) 예제 코드

from collections import defaultdict
from heapq import heapify,heappop,heappush

def prim(start_node):
    global result
    print(f'start : {start_node}')
    q = graph_dict[start_node]
    heapify( q ) ## 시작노드 q에 넣기
    visited.append(start_node) # 시작 노드 방문 처리
    while q:
        dist,start,end = heappop(q) # heapq 활용 dist 낮은 순으로 뽑기
        if end not in visited: # 가중치 낮은 간선의 노드가 방문 전이면
            visited.append(end)
            result.append((dist,start,end))
            print(f'{start} → {end} : {dist}')
            for nd,ns,ne in graph_dict[end]: # 방문한 노드의 다음 노드 탐색
                if ne not in visited:
                    heappush(q,(nd,ns,ne))

graph = [(1,'A','B'),(3,'A','D'),
         (3,'B','C'),(2,'B','D'),(6,'B','E'),(5,'B','F'),
         (4,'C','E'),(4,'C','F'),
         (3,'D','E'),
         (2,'E','F')]
graph_dict = defaultdict(list)
# dictionary로 양방향 그래프 구현
for distance,start,end in graph:
    graph_dict[start].append((distance,start,end))
    graph_dict[end].append((distance,end,start))
visited = [] ## 방문 관리 list
result = [] ## 결과 저장 list
prim('B') ## 'B' 노드부터 시작
print(result)

- 문제에서 그래프가 주어지면 해당 그래프를 양방향 그래프로 변환한다.

- 이때, 우선순위큐(heap)을 사용하기위해 가중치(distance)를 가장 첫번째 원소로 tuple을 구성한다. 

- 방문 관리를 위한 visited list를 생성하고 시작 노드를 정한다. 

- 시작 노드부터 heap에 넣고, 방문 후 다음 간선의 가중치가 작은 것부터 탐색한다. 

  → heap 대신 list를 사용하고 매번 오름차순 정렬해도 가능. 

 

 

크루스칼(kruskal) 알고리즘?

- 주어진 간선의 가중치가 작은 순서대로(오름차순) 정렬하여 순서대로 확인한다. 

- 간선 연결 시 순환(Cycle)을 피해 간선을 연결한다. 

- 간선 연결 시 

- 아래 애니메이션에서 e → a, c→d, a→b, b→c 순으로 노드를 방문한다.

- 프림과 다른점은 미리 모든 간선 정보를 알고 노드를 방문한다는 것이다.  ( 프림은 시작점 하나를 선택 )

크루스칼 애니메이션 ( 출처 : 위키 )

 

크루스칼(kruskal) 예제 코드

def find(x):## 최상위 부모노드 찾기
    if parent[x] != x : ## 부모노드와 자기자신의 값이 다르면
        parent[x] = find(parent[x]) ## 최상위 부모노드를 찾을때까지 재귀호출
    return parent[x] ## 결국 최상위 부모노드 뽑힘

def union(x,y): ## 노드 합치기 
    x = find(x) ## x의 부모 노드 구하기
    y = find(y) ## y의 부모 노드 구하기
    
    ## x,y의 부모노드 중 큰 값이 작은 값의 부모가 된다
    if x < y : 
        parent[y] = x
    else :
        parent[x] = y

def kruskal():
    global result,distance
    graph.sort()  ##list를 간선의 가중치 기준으로 오름차순 정렬
    for dist,u,v in graph : ## 가중치 가장 낮은 간선부터 loop
        if find(u) != find(v): ## 두 노드의 부모가 다르면
            union(u,v) ## 두 노드를 연결한다 ( 간선 선택 )
            distance += dist ## 가중치 더하기
            result.append((dist,u,v)) ## 결과값에 저장
            print(f'{u} ↔ {v} : {dist}') 

graph = [(3,'a','b'),(1,'a','e'),
         (5,'b','c'),(4,'b','e'),
         (2,'c','d'),(6,'c','e'),
         (7,'d','e')]
## 순환 검사를 위한 dictionary 구현
parent = dict()
for x in ['a','b','c','d','e']:
    parent[x]=x ## 자기 자신을 부모로 갖는 dict 
result = [] ## 결과 저장 list
distance = 0 ## 간선 합 저장
kruskal()
print(result)
print(distance)

- 문제에서 그래프가 주어지면 각 노드 자기 자신을 부모로 갖는 dictionary를 생성한다. 

  → find, union 함수와 함께 순환(cycle) 검사에 이용할 것이다. 

- 최상위 부모 노드를 찾을 find 함수와 두 노드의 최상위 부모노드 값을 비교할 union 함수를 구현한다. 

  → find(x) : 재귀함수를 통해 자기자신과 부모노드의 값이 같은 최상위 노드를 찾는다. 

  → union(x,y) : x의 최상위 부모 노드와 y의 최상위 부모노드 값을 비교하여 더 큰 값이 부모가 되도록 설정한다. 

- 주어진 graph를 가중치의 오름차순으로 정렬한다.  

- 순서대로 반복하며 순환구조인지 검사 후 아니면 결과값에 반영한다. 

- 만약 간선이 추가로 생기는 문제라면, graph list를 heapq로 선언하여 시간을 줄여야 한다. 

 

 

프림(prim) vs 크루스칼(kruskal)

	프림	크루스칼
시작점 유무	필요	불필요
구현 방식	heapq+DP(동적계획법)	union-find + stack or heapq
시간 복잡도( E:간선수, V:노드수 )	O(ElogV)	O(ElogE)
특징	노드 기준으로 간선을 연결	간선의 가중치만 보고 연결
	→ 노드에비해 간선이 많을때 빠름	→ 간선의 수가 적을때 빠름