최소 신장 트리(MST, Minimum Spanning Tree)

신장 트리 (Spanning Tree)

그래프 내의 모든 정점을 포함하는 트리

• 그래프의 최소 연결 부분 그래프.
  • 최소 연결 : 간선의 수가 가장 적다
  • n개의 정점을 가지는 그래프 = 최소 간선의 수는 n-1개 = n-1개의 간선으로 연결 = 트리 형태
• DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다.
  • 탐색 도중에 사용된 간선들을 모음
• 하나의 그래프에는 많은 신장 트리가 존재
• 정점(Vertex) : 모두 포함
• 사이클 : X (트리임)
• 최소 신장 트리(MST)란?
• 가장 간선의 가중치 합이 가장 작은 트리를 의미한다. (최소 비용)MST 사용 사례
• 통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우

1. 도로 건설
   • 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제
2. 전기 회로
   • 단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제
3. 통신
   • 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제
4. 배관
   • 파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 연결하는 문제

크루스칼 알고리즘과 프림 알고리즘의 선택 기준

1. 프림 알고리즘 (Prim's Algorithm)

• 특징: 시작 정점에서 출발하여 연결된 정점들을 하나씩 추가해 가며 MST를 구성합니다.
• 적합한 상황:
  • 밀집 그래프 (Dense Graph): 정점 간의 간선이 많은 경우에 유리합니다.
  • 인접 리스트 또는 인접 행렬로 그래프가 표현된 경우.
  • 그래프의 크기가 크고 간선이 많을 때 효율적입니다.

2. 크루스칼 알고리즘 (Kruskal's Algorithm)

• 특징: 모든 간선을 오름차순으로 정렬한 후, 사이클이 생기지 않도록 간선을 하나씩 추가하며 MST를 구성합니다.
• 적합한 상황:
  • 희소 그래프 (Sparse Graph): 간선의 수가 상대적으로 적은 경우에 유리합니다.
  • 간선 리스트로 그래프가 주어졌을 때.
  • 그래프의 크기가 작고 간선이 적을 때 효율적입니다.

요약

• 프림 알고리즘은 밀집 그래프에서 유리하며, 시작 정점이 중요합니다.
• 크루스칼 알고리즘은 희소 그래프에서 유리하며, 간선 기반 접근 방식을 사용합니다.

크루스칼 알고리즘(Kruskal's Algorithm)

크루스칼 알고리즘이란

• 탐욕적인 방법(greedy method)을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것동작 과정

1. 간선 정렬 : 모든 간선을 가중치의 오름차순으로 정렬
2. 간선 선택 : 정렬된 간선 중에서 사이클을 만들지 않는 간선을 선택
3. 사이클 검사 : 사이클이 형성되면 그 간선을 버리고, 아니면 신장 트리에 추가한다.
4. 반복 : 모든 정점이 연결될 때까지 이 과정을 반복
   예시
5. A -2- B -3- C | /| /| 6 5 4 7 5 | / | / | D -1- E -2- F

```

크루스칼 알고리즘 동작 과정

• 간선 정렬:
  • 간선 가중치 오름차순: [D - E (1), A - B (2), E - F (2), B - C (3), B - E (4), B - D (5), C - F (5), A - D (6), E - C (7)]
• 간선 선택:
  • D - E (1) 선택 (사이클 없음)
  • A - B (2) 선택 (사이클 없음)
  • E - F (2) 선택 (사이클 없음)
  • B - C (3) 선택 (사이클 없음)
  • B - E (4) 선택 (사이클 없음)
  • B - D (5)는 선택하지 않음 (사이클 생성)
  • C - F (5)는 선택하지 않음 (사이클 생성)
  • A - D (6)은 선택하지 않음 (사이클 생성)
  • E - C (7)은 선택하지 않음 (사이클 생성)
• MST 결과:
  • 선택된 간선: [D - E (1), A - B (2), E - F (2), B - C (3), B - E (4)]
  • 이 간선들로 이루어진 트리가 최소 신장 트리입니다.

최종 요약

• MST 간선: [D - E (1), A - B (2), E - F (2), B - C (3), B - E (4)]
• 이 간선들의 가중치 합은 1 + 2 + 2 + 3 + 4 = 12입니다.크루스칼 알고리즘 구현
• Union-Find 알고리즘 사용

코드 내용

# Union-Find 구현 (클래스 없이)
# 두 집합을 합치는 함수
def union(parent, rank, u, v):
    root_u = find(parent, u)  # u가 속한 집합의 루트 찾기
    root_v = find(parent, v)  # v가 속한 집합의 루트 찾기

    if root_u != root_v:  # 두 노드가 다른 집합에 속해 있다면 (사이클이 생기지 않으면)
        # 랭크(rank)가 높은 쪽을 부모로 설정
        if rank[root_u] > rank[root_v]:
            parent[root_v] = root_u  # v의 부모를 u의 루트로 설정
        elif rank[root_u] < rank[root_v]:
            parent[root_u] = root_v  # u의 부모를 v의 루트로 설정
        else:
            parent[root_v] = root_u  # u와 v의 랭크가 같다면 u를 루트로 하고 랭크를 증가시킴
            rank[root_u] += 1

# 특정 노드가 속한 집합의 루트를 찾는 함수 (경로 압축)
def find(parent, u):
    if parent[u] != u:  # 루트 노드가 자기 자신이 아닐 경우 (즉, 부모가 있는 경우)
        parent[u] = find(parent, parent[u])  # 부모 노드의 루트를 재귀적으로 찾고 경로 압축
    return parent[u]  # 루트 노드를 반환

# 크루스칼 알고리즘 구현 함수
def kruskal(V, edges):
    parent = list(range(V))  # 초기에는 각 노드가 자기 자신을 부모로 가지도록 설정
    rank = [0] * V  # 모든 노드의 랭크를 0으로 초기화
    mst = []  # MST (최소 신장 트리)에 포함될 간선들을 저장할 리스트

    edges.sort(key=lambda x: x[2])  # 간선들을 가중치 기준으로 오름차순 정렬

    for u, v, weight in edges:  # 정렬된 간선들을 하나씩 확인
        if find(parent, u) != find(parent, v):  # u와 v가 다른 집합에 속해 있다면 (사이클이 생기지 않으면)
            union(parent, rank, u, v)  # u와 v를 같은 집합으로 합침
            mst.append((u, v, weight))  # 해당 간선을 MST에 추가

    return mst  # 완성된 MST를 반환

# 예제 그래프
V = 6  # 정점의 수 (A, B, C, D, E, F를 각각 0, 1, 2, 3, 4, 5로 나타냄)
edges = [
    (0, 1, 2),  # A - B 간선의 가중치 2
    (0, 3, 6),  # A - D 간선의 가중치 6
    (1, 2, 3),  # B - C 간선의 가중치 3
    (1, 3, 4),  # B - D 간선의 가중치 4
    (1, 4, 5),  # B - E 간선의 가중치 5
    (2, 5, 7),  # C - F 간선의 가중치 7
    (2, 4, 4),  # C - E 간선의 가중치 4
    (3, 4, 1),  # D - E 간선의 가중치 1
    (4, 5, 2),  # E - F 간선의 가중치 2
]

# 크루스칼 알고리즘을 실행하여 MST 생성
mst = kruskal(V, edges)

# 결과 출력
print("MST의 간선들:")
for u, v, weight in mst:
    print(f"{u} - {v}: 가중치 {weight}")

궁금한 점

1. 왜 rank를 사용해야 할까

# union을 rank 없이 함수 구현
def union(parent, u, v):
    # u와 v의 루트를 각각 찾음
    root_u = find(parent, u)
    root_v = find(parent, v)

    # 두 루트가 다를 경우, 한쪽을 다른 쪽에 병합
    if root_u != root_v:
        parent[root_v] = root_u  # v의 루트를 u의 루트에 병합

• rank 배열 없이도 union 함수를 작성 할 수 있다. 'rank' 배열은 주로 두 트리를 병합할 때, 더 낮은 높이(또는 깊이)의 트리를 더 높은 트리 아래에 병합하여 트리의 높이를 최소화하기 위한 것이다. 이를 통해 'find'의 연산의 평균 시간 복잡도를 줄일 수 있다.
• 서로 다른 그래프 집합이 생성 될 때 rank를 사용하지 않으면 2개만 루트 노드를 바꿔주면 될 것을 100개를 바꿔줘야 할 수도 있다. 밑에 parent 예를 바라보자

A	B	C	D	E	F	G	H
A	A	C	C	C	C	C	C

• A와 C를 연결하려 한다. RANK를 사용하지 않으면 A,B 두 개만 C로 바꿔주면 되는데 C~H까지 6개가 A로 바꿔야 할 경우가 생긴다. 더 많아지게 되면 시간 복잡도는 바꿔야할 개수만큼 늘어날 것이다.
• rank 배열을 사용해서 깊이를 부여하고 깊이가 더 큰 C에 A와 B가 맞춘다.
• 결론 : rank를 사용하여 find의 연산의 효율을 향상 시킨다.

2. union-find 알고리즘을 왜 사용할까?
   • union-find 알고리즘을 사용해 같은 집합(그래프)인지 분별이 가능하다. (사이클 검사)
   • 예를 들어 1번과 2번 노드가 같은 부모일 때, 1번과 2번을 연결하면 사이클이 생긴다.
   • 프림 알고리즘(Prim's Algorithm)

• 정점 중심 알고리즘
• 하나의 정점에서 시작하여, 연결된 간선 중에서 가장 작은 가중치를 가진 간선을 선택해면서 트리를 확장해 나가는 방식동작 과정

1. 시작 정점 선택 : 임의의 정점에서 시작한다.
2. 간선 추가 : 현재 트리와 연결된 간선 중 가중치가 가장 작은 간선을 선택해 트리에 추가한다.
3. 반복 : 모든 정점이 트리에 포함될 때까지 이 과정을 반복한다.

예시

  A -2- B -3- C
  |    /|    /|
  6   5 4   7 5
  | /   | /   |
  D -1- E -2- F

프림 알고리즘의 동작 과정

1. 시작 정점 선택: A를 시작 정점으로 선택합니다.
2. 간선 추가: A와 연결된 간선 중 가중치가 가장 작은 A-B (2)를 선택합니다.
3. 트리 확장:
   • B와 연결된 간선 중 가중치가 가장 작은 B-C (3)를 선택합니다.
   • C와 연결된 간선 중 가중치가 가장 작은 C-F (5)를 선택합니다.
   • F와 연결된 간선 중 가중치가 가장 작은 E-F (2)를 선택합니다.
   • E와 연결된 간선 중 가중치가 가장 작은 D-E (1)를 선택합니다.

이렇게 해서 선택된 간선들은 [A-B (2), B-C (3), C-F (5), E-F (2), D-E (1)]입니다.

프림 알고리즘의 구현(python)

import heapq

def prim(graph, start):
    mst = []  # 최소 신장 트리를 저장할 리스트
    visited = [0] * len(graph)  # 방문한 정점을 기록할 리스트

    # (가중치, 정점)으로 우선순위 큐 초기화
    priority_queue = [(0, start)] 

    while priority_queue:
        weight, u = heapq.heappop(priority_queue)  # 가장 작은 가중치를 가진 간선 선택
        if not visited[u]:
            visited[u] = 1
            mst.append((weight, u))
            for v, w in graph[u]:  # 정점 u에 연결된 모든 간선을 확인
                if not visited[v]:  # 방문되지 않은 정점만 큐에 추가
                    heapq.heappush(priority_queue, (w, v))

    return mst

# 그래프를 인접 리스트로 표현 (정점, 간선 가중치)
graph = {
    0: [(1, 2), (3, 6)],
    1: [(0, 2), (2, 3), (4, 5), (3, 4)],
    2: [(1, 3), (5, 7), (4, 4)],
    3: [(0, 6), (1, 4), (4, 1)],
    4: [(1, 5), (3, 1), (2, 4), (5, 2)],
    5: [(2, 7), (4, 2)]
}

# 0번 정점부터 시작하는 프림 알고리즘 실행
mst = prim(graph, 0)

print("MST의 간선들:")
for weight, vertex in mst:
    print(f"가중치 {weight}, 정점 {vertex}")

프림 알고리즘 동작 과정 요약

1. A에서 시작하여 B (2)를 선택합니다.
2. B에서 C (3)를 선택합니다.
3. C에서 F (5)를 선택합니다.
4. F에서 E (2)를 선택합니다.
5. E에서 D (1)을 선택합니다.

최종 MST

프림 알고리즘에 의해 얻어진 최소 신장 트리(MST)는 [A-B (2), B-C (3), C-F (5), E-F (2), D-E (1)]입니다.