[Algorithm] 최소 신장 트리(MST), Kruskal & Prim algorithm

신장 트리(Spanning Tree)

그래프 내의 모든 정점을 포함한 최소 연결 부분 그래프이며 

Tree이기 때문에 사이클이 존재할 수 없다.

 

최소비용 신장 트리 (Minimum Spanning Tree : MST) 

신장 트리 중 간선의 가중치 합이 최소인 트리이다.

 

가중치가 존재하는 무방향 Graph에서 Spanning Tree(이하 신장 트리)를 무작위로 만들어 었을 경우 cost는 다양하게 나옵니다.

하지만 그중에서 최소 비용으로 만드는 신장 트리를 Minimum Spanning Tree(이하 최소비용 신장 트리)라고 한다

 

사진을 보면 Graph에서 Cost(가중치합)을 고려 안한 신장 트리를 제작을 했을 경우 Cost가 13이 나오게 됩니다.

여기서 Cost를 최소한으로 줄여본 신장 트리는 Cost가 7로 최소비용 신장 트리가 완성이 됩니다.

신장트리와 최소 신장트리 예시

 

• 그래프 지식
  
  • 정점(vertex),노드(node): 위치 (그림상에서 원)
  • 간선(edge):  노드를 연결하는 선 ( 그림상에서 검정선)
  • 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
  • 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
  • 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

최소비용 신장 트리를 구현하는 알고리즘이 대표적으로 2가지가 있습니다.

• 크루스칼 알고리즘(Kruskal Algorithm)
• 프림 알고리즘(Prim Algorithm) 

 

1. 크루스칼 알고리즘 (Kruskal Algorithm)

Kruskal은 간선을 구성원의 오름차순으로 정렬하고, 가장 가중치가 낮은 간선부터 선택하여 사이클을 형성하지 않는 경우에만 트리에 추가한다. 이 과정을 반복하여 최소비용 신장 트리를 구성합니다.

 

단계

1. 그래프의 모든 간선을 오름차순으로 정렬
2. 정렬된 간선들 중에서 가중치가 낮은 순서대로 사이클을 형성하지 않는 간선을 선택
3. 간선의 수가 (노드의 수-1)가 충족될 때까지 2번 과정을 반복

그림설명

1. 가장 낮은 가중치 간선(1: 빨간색)을 선택합니다.
2. 그후 가장 낮은 가중치 (1: 빨간색)을 선택합니다.
3. 가중치 낮은 간선(2)중에 한개를 선택합니다.
4. 가중치가 가장 낮은 간선(2)은 사이클을 생성시키기 때문에 제외하고 그다음 가중치 낮은 간선(3)을 선택합니다.
5. 간선의 수(4)가 (노드의 수(5) -1)와 동일하게 되었기 때문에 마무리 짓습니다. 

 

시간복잡도

크루스칼 알고리즘은 간선의 개수가 E개일 때, O(ElogE)의 시간복잡도를 갖는다

많은 시간을 요구하는 곳은 간선의 정렬을 수행하는 부분이다.

정점(노드)의 수를 V라고 하고 최악의 상황을 가정해서 완전그래프의 간선의 개수 E=V*(V-1)/2가 E=V²비례하기에 

E= V²로 가정한다. (고밀도 그래프상황)

따라서 최악의 경우는 O(ElogE) = O(V²logV²) → O(2 * V²logV) →O(V²logV)의 시간복잡도를 갖는다.

 

2. 프림 알고리즘 (Prim Algorithm) 

Prim은 시작노드를 선택후, 노드에 가장 가중치가 낮은 작은  간선을 선택하여 트리를 확장하는 방식으로 동작합니다.  선택된 노드중에 가장 가중치가 낮은 간선을 선택하고 연결을 반복하여 최소 신장 트리를 구성합니다.

 

단계

1. 임의의 시작노드을 선택하여 트리에 추가합니다.
2. 시작노드에 연결된 간선 중 가중치가 최소인 간선을 선택
3. 선택된 노드들 중 가중치가 가장 낮으며 사이클을 형성하지 않는 간선을 선택 
4. 모든 노드들이 선택될 때까지 3번 과정을 반복

그림설명

1. 시작노드(✔)을 무작위로 선정후에  연결된 간선중에 최소의 간선을 선택합니다.
2. 그후 선택된 노드들(✔) 중 가중치가 가장 낮은 간선(1:빨간색)을 선택합니다.
3. 그후 선택된 노드들(✔) 중 가중치가 가장 낮은 간선(1:빨간색)을 선택합니다.
4. 그후 선택된 노드들(✔) 가중치가 가장 낮은 간선(2,3: 보라색)은 사이클을 생성시키기 때문에 제외하고 그다음 가중치 낮은 간선(3:빨간색)을 선택합니다.
5. 모든 노드들이 선택되었기 때문에 마무리합니다.

 

시간복잡도

프림 알고리즘은 노드의 갯수 V개일 때, O(V²)의 시간복잡도를 갖는다.

가장 가중치가 낮은 간선을 배열에서 선형 탐색으로 찾아야하기 때문인데 

배열 대신에 힙 우선순위 큐를 사용하면 O(logV)가 소요되고 그후 각 간선마다 최대 한번씩 검사를 하기에 O(ElogV)가 된다. 

하지만 이또한 저밀도 그래프에서는 O(VlogV)이지만 고밀도 그래프에서는 O(V² logV)이며, 기존의 O(V²)보다 느리다.

1987년 피보나찌힙을 우선순위를 사용하여 가장 빠른 프림 알고리즘이 개발되었다고 한다.

시간복잡도는 O(E + VlogV)이며 저밀도 그래프에서는 O(VlogV) 고밀도에서는 O(V²)이다.

 

 

크루스칼 VS 프림 

크루스칼은 간선 기준으로 각자의 트리에 추가하여 추후 트리를 합쳐 MST를 만드는 방식이다.

프림은 속하지 않은 노드(정점)을 기준으로 하나씩 추가하는 방식이다.

 

위에서 크루스칼을 소개하면서 E=V²로 가정한다 하였는데

이는 V-1 ≤ E ≤ V(V-1)/2 이 성립하기 때문이다.

간선의 갯수(E)가 이범위의 하한과 가까운 그래프는 저밀도 그래프라고 하고 크루스칼 알고리즘이 더 빠르다.

O(VlogV)_크루스칼  ≥ 프림 { O(VlogV)_힙우선순위큐 ≥ O(VlogV)_피보나치우선순위큐 ≥   O(V²)_일반 }

 

간선의 갯수(E)가 이범위의 상한과 가까운 그래프는 고밀도 그래프라고 하고 프림 알고리즘이 더 빠르다.

O(V²logV)_크루스칼  ≤  프림 { O( V²logV)_힙우선순위큐 ≤  O(V²)_피보나치우선순위큐 ≤   O(V²)_일반 }

 

Kruskal 코드_ 링크

 

def kruskal(graph):
    parent = {}  # 각 노드의 부모 노드를 저장할 딕셔너리
    rank = {}    # 각 노드의 랭크를 저장할 딕셔너리
    mst = []     # 최소 신장 트리를 저장할 리스트

    #루트노드 찾는함수
    def find(v):
        if parent[v] != v:
            parent[v] = find(parent[v])
        return parent[v]

    def union(v1, v2): # 두 노드를 하나로 합치는 함수
        root1 = find(v1)
        root2 = find(v2)
        if root1 != root2:
            if rank[root1] < rank[root2]:
                parent[root1] = root2
            elif rank[root1] > rank[root2]:
                parent[root2] = root1
            else:
                parent[root2] = root1
                rank[root1] += 1

    # 각 노드를 자기 자신의 부모로 초기화
    for v in graph:
        parent[v] = v
        rank[v] = 0

    #모든간선을 넣고 정렬
    edges = [] 
    for node, neighbors in graph.items():
        for neighbor, weight in neighbors:
            edges.append((node, neighbor, weight))
    edges.sort(key=lambda x: x[2])
    
    #순회하면서 루트노드가 다르면 다른트리로 인식후 합침
    for u, v, weight in edges:
        if find(u) != find(v):
            union(u, v)
            mst.append((u, v, weight))

    return mst

# 주어진 그래프
graph = {
    'A': [('B', 2), ('C', 3),('E', 3)],
    'B': [('A', 2), ('C', 1), ('D', 1)],
    'C': [('A', 3), ('B', 1), ('D', 2)],
    'D': [('B', 1), ('C', 2),('E', 2)],
    'E': [('A', 3), ('D',2)]
}

# 크루스칼 알고리즘 적용 및 결과 출력
mst = kruskal(graph)
print("최소 신장 트리:")
for edge in mst:
    print(edge)

 

Prim_링크

import heapq
def prim(graph):
    
    num_vertices = len(graph) # 그래프의 정점 개수 
   
    visited = set() # 방문한 정점을 저장하는 set
    
    mst = []# 최소 신장 트리의 간선 리스트
    
    # 임의의 시작 정점을 선택
    start_vertex = list(graph.keys())[0]
    
    
    visited.add(start_vertex) # 시작 정점을 방문으로 기록
    
    # 시작 정점과 연결된 간선을 우선순위 큐에 추가
    edges = [(cost, start_vertex, neighbor) for neighbor, cost in graph[start_vertex]]
    heapq.heapify(edges)
    
    while edges:
        # 최소 비용의 간선을 가져옴
        cost, src, dest = heapq.heappop(edges)
        # 이미 방문한 정점이면 다음 간선 확인
        if dest in visited:
            continue

        # 최소 신장 트리에 간선 추가
        mst.append((src, dest, cost))
        visited.add(dest)# 방문으로 기록
    
        # 새로 추가된 정점과 연결된 간선을 우선순위 큐에 추가
        for neighbor, cost in graph[dest]:
            if neighbor not in visited:
                heapq.heappush(edges, (cost, dest, neighbor))
    
    return mst

graph = {
    'A': [('B', 2), ('C', 3),('E', 3)],
    'B': [('A', 2), ('C', 1), ('D', 1)],
    'C': [('A', 3), ('B', 1), ('D', 2)],
    'D': [('B', 1), ('C', 2),('E', 2)],
    'E': [('A', 3), ('D',2)]
}

mst = prim(graph) #prim 실행

print("최소 신장 트리")
for edge in mst:
    print(edge)

 

 

관련된 포스팅

[Algorithm] Greedy

[Algorithm] 다익스트라 알고리즘(Dijkstra Algorithm)

[Algorithm] Scheduling

[Algorithm] 허프만 코드

[Algorithm] Greedy Code 모음