[WEEK03] 신장트리와 최소신장트리 (크루스칼 + 프림 알고리즘)

1. 신장트리

Spanning Tree

- 신장트리는 그래프 알고리즘 문제로 자주 출제되는 문제유형

- 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

- 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립조건이기도 함

 

신장트리

최소신장트리 알고리즘 (MST; Minimum Spanning Tree)

- 신장트리 중에서 최소 비용으로 만들 수 있는 신장트리를 찾는 알고리즘

 

2. 크루스칼 알고리즘

특징

- 대표적인 최소신장트리 알고리즘 중의 하나

- 그리디 알고리즘으로 분류

- 모든 간선에 대해 정렬을 수행한 뒤에 가장 짧은 간선부터 집합에 포함시킴

  (이때 사이클을 발생시킬 수 있는 간선의 경우 집합에 포함시키지 않음 => 최적의 해 보장)

 

알고리즘 구현과정

1. 간선 데이터를 비용에 따라 오름차순으로 정렬

2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인

    2-1. 사이클이 발생하지 않는 경우 최소 신장트리에 포함시킴

    2-2. 사이클이 발생하는 경우 최소 신장트리에 포함시키지 않음

3. 모든 간선에 대해 2번의 과정을 반복

 

시간복잡도

- 간선의 개수가 E일때,  O(ElogE)의 시간복잡도를 가짐

출처 : https://devraphy.tistory.com/83

1) 모든 정점을 독립적으로 만듦 (부모 노드를 자기자신으로 초기화) -> O(V)

2) 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬 -> O(ElogE)

    - 각 엣지별로 트리를 모두 돌면서 자기보다 크거나 작은 엣지가 있는지 확인하는 과정

3) 2개 부분집합 각각의 루트노드를 확인(find)하고 서로 다른경우 union -> O(1)

    -링크참고

 

 

소스코드 (출처 : 이코테)

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
        
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a 
    else:
        parent[a] = b 
        
# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split( ))
parent = [0] * (v + 1) # 부모 테이블 초기화

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0 

# 부모 테이블 상에서 부모를 자기자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i 
    
    
# 모든 간선에 대한 정보를 입력받기
for _ in range(e):
    a, b, cost = map(int, input().split())
    # 비용 순으로 정렬하기 위해서 튜플의 첫번째 원소를 비용을 설정
    edges.append((cost, a, b))
    
# 간선을 비용순으로 정렬
edges.sort()

# 간선을 하나씩 확인하며
for edge in edges:
    cost, a, b = edge
    # 사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost 
        
print(result)

 

3. 프림 알고리즘

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법

 

동작방법

1. 시작 단계에서는 시작정점만이 MST(최소 비용 신장트리) 집합에 포함됨

2. 앞 단계가 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장

    (즉, 가장 낮은 가중치를 먼저 선택)

3. 위의 과정을 (n-1)개의 간선을 가질 때까지 반복

 

시간복잡도

우선순위 큐일 때 : O(Elog V)

 

1) 모든 노드에 대해 탐색을 하는 과정 : O(Vlog V)

- 모든 노드에 탐색 진행 : O(V)

- 우선순위큐를 사용하여 매 노드마다 최소간선 찾기 : O(logV)

=> O(Vlog V)

2) 각 노드의 인접간선 찾는시간 : O(Elog V)

- 모든 노드의 차수와 같으므로 : O(2E) = O(E)

- 각 간선에 대해 힙에 넣는 과정 O(logV)

=> O(Elog V)

 

1) + 2)로 O(Vlog V + Elog V) = O(Elog V)

 

 

우선순위 큐가 아닌 배열로 구현시 : O(V^2)

 

1) 최소간선을 갖는 정점 탐색

=> O(V ^ 2)

2) 탐색결과를 기반으로 각 정점의 최소비용 연결정점 탐색

=> O(1)

 

1) + 2)로 O(V^2)

 

소스코드

# https://8iggy.tistory.com/159
# 프림 알고리즘

from collections import defaultdict
import heapq

def mst():
    v, e = 6, 9
    edges = [[1, 2, 6], [1, 3, 3], [2, 3, 2], [2, 4, 5],
             [3, 4, 3], [3, 5, 4], [4, 5, 2], [4, 6, 3], [5, 6, 5]]
    graph = defaultdict(list)
    for start, end, weight in edges:
        graph[start].append((end, weight))
        graph[end].append((start, weight))
        
    mst_graph = [[0] * v for _ in range(v)]
    mst_nodes = [-1 for _ in range(v)]
    visited = [True for _ in range(v)]
    
    q = [(0, 1, 1)]
    while q:
        cost, node, prev = heapq.heappop(q)
        if not visited[node-1]:
            continue
        visited[node-1] = False
        mst_graph[node-1][prev-1] = 1
        mst_graph[prev-1][node-1] = 1
        mst_nodes[node-1] = cost 
        
        for end, weight in graph[node]:
            if visited[end - 1]:
                heapq.heappush(q, (weight, end, node))
    
    print(f'MST cost is {sum(mst_nodes)}')
    mst_graph[0][0] = 1
    for row in mst_graph:
        print(*row)
        
mst()

 

 

[출처]

서적 : 이것이 취업을 위한 코딩테스트다

블로그 :

https://devraphy.tistory.com/83

https://8iggy.tistory.com/159