최소 신장 트리(Minimum Spanning Tree, MST) : 가장 경제적인 방식으로 모든 지점을 연결한다

스패닝 트리(Spanning Tree)

원래 그래프의 모든 정점을 포함하면서 사이클 없이 연결된 부분 그래프를 의미한다. 

 

스패닝 트리 조건

1. 모든 정점을 포함한다.
   스패닝 트리는 원래 그래프의 모든 정점을 반드시 포함한다. 스패닝 트리는 그래프의 모든 요소를 '포괄(span)'한다는 의미에서 그 이름이 유래했다. 
2. 정확히 (n-1)개의 간선을 가집니다. (여기서 n은 그래프의 정점 수)
   n개의 정점을 가진 그래프의 스패닝 트리는 정확히 (n-1)개의 간선을 가진다. 이는 모든 정점을 연결하는 데 필요한 최소한의 간선 수 이다. 
3. 사이클(순환)을 포함하지 않는다.
   스패닝 트리에는 사이클이 존재하지 않는다. 즉, 어떤 정점에서 출발하여 다시 그 정점으로 돌아오는 경로가 없다.
4. 연결되어 있다. (모든 정점 간에 경로가 존재)
   스패닝 트리는 연결 그래프이다. 즉, 트리 내의 모든 정점 쌍 사이에 경로가 존재한다. 

스패닝 트리의 성질

• 그래프의 모든 정점을 최소한의 간선으로 연결한다. 
  스패닝 트리는 그래프의 모든 정점을 연결하는 가장 경제적인 방법을 제공한다. (→ 네트워크 설계) 
  
• 임의의 두 정점 사이에 유일한 경로가 존재한다. 
  스패닝 트리에서는 임의의 두 정점 사이에 유일한 경로가 존재한다. (→ 네트워크 라우팅 단순화)
• 어떤 간선을 제거하면 그래프가 두 개의 분리된 부분으로 나뉜다. 
  스패닝 트리에서 어떤 간선을 제거하면, 그래프가 두 개의 분리된 부분으로 나뉜다. (→ 네트워크 취약점 분석)

---

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

스패닝 트리의 특별한 경우로 최소 신장 트리(Minimum Spanning Tree, MST)가 있다. 이는 간선에 가중치가 있는 그래프에서, 모든 정점을 포함하면서 간선의 가중치 합이 최소인 스패닝 트리를 말한다. MST는 Kruskal 알고리즘이나 Prim 알고리즘을 통해 효율적으로 찾을 수 있다. 

 

• Kruskal's Algorithm: 간선을 가중치 순으로 정렬하여 사이클을 형성하지 않는 선에서 추가
• Prim's Algorithm: 임의의 정점에서 시작하여 트리를 점진적으로 확장

Kruskal vs Prim Algorithm

두 알고리즘의 실행 결과 :

• 크루스칼 : B - C : 1, A - C : 2, C - D : 3, C - E : 6
• 프림 (A에서 시작): A - C : 2, C - B : 1, C - D : 3, C - E : 6

 

Kruskal's Algorithm 작동 방식 

1. 간선 정렬: 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬한다. 
2. 초기화: 각 정점을 독립된 집합으로 초기화한다. 서로소 집합(Disjoint Set) 자료구조를 사용하여 구현한다. 
3. 간선 선택: 정렬된 간선 리스트에서 가장 가중치가 작은 간선부터 차례로 선택한다. 
4. 사이클 검사: 선택한 간선이 현재의 MST에 추가될 때 사이클을 형성하는지 검사한다. 이는 두 정점이 같은 집합에 속해 있는지 확인하는 것으로 구현한다. 
5. 간선 추가: 사이클을 형성하지 않는 경우, 해당 간선을 MST에 추가하고 두 정점을 같은 집합으로 합친다. 
6. 반복: 3-5 단계를 (정점 수 - 1)개의 간선이 선택될 때까지 반복한다. 

Kruskal's Algorithm 코드 

class DisjointSet:
    def __init__(self, vertices):
        # 각 정점을 자신을 가리키도록 초기화
        self.parent = {v: v for v in vertices}
        # 각 정점의 랭크(트리의 높이)를 0으로 초기화
        self.rank = {v: 0 for v in vertices}

    def find(self, item):
        # 경로 압축을 사용하여 루트 노드를 찾음
        if self.parent[item] != item:
            self.parent[item] = self.find(self.parent[item])
        return self.parent[item]

    def union(self, x, y):
        # 두 집합을 합치는 연산
        xroot, yroot = self.find(x), self.find(y)
        
        # 랭크가 낮은 트리를 랭크가 높은 트리 밑에 붙임
        if self.rank[xroot] < self.rank[yroot]:
            self.parent[xroot] = yroot
        elif self.rank[xroot] > self.rank[yroot]:
            self.parent[yroot] = xroot
        else:
            # 랭크가 같은 경우, 한 쪽을 루트로 선택하고 랭크를 1 증가
            self.parent[yroot] = xroot
            self.rank[xroot] += 1

def kruskal(graph):
    # 모든 간선을 가중치 기준으로 정렬
    edges = [(w, u, v) for u, edges in graph.items() for v, w in edges.items()]
    edges.sort()  # 가중치 오름차순 정렬

    vertices = list(graph.keys())
    disjoint_set = DisjointSet(vertices)
    mst = []  # 최소 신장 트리를 저장할 리스트

    for w, u, v in edges:
        # 사이클을 형성하지 않는 경우에만 간선 추가
        if disjoint_set.find(u) != disjoint_set.find(v):
            disjoint_set.union(u, v)
            mst.append((u, v, w))

        # 모든 정점이 연결되면 종료 (간선의 수가 정점 수 - 1이 되면)
        if len(mst) == len(vertices) - 1:
            break

    return mst

# 예시 그래프
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'A': 4, 'C': 1, 'D': 5},
    'C': {'A': 2, 'B': 1, 'D': 3, 'E': 6},
    'D': {'B': 5, 'C': 3, 'E': 7},
    'E': {'C': 6, 'D': 7}
}

# 크루스칼 알고리즘 실행
mst = kruskal(graph)
print("Kruskal's 알고리즘으로 찾은 최소 신장 트리:")
for edge in mst:
    print(f"{edge[0]} - {edge[1]} : 가중치 {edge[2]}")

Prim's Algorithm 작동 방식 

1. 시작 정점 선택: 임의의 정점을 시작점으로 선택한다. 
2. 초기화: 선택한 시작 정점을 MST 집합에 추가하고, 나머지 정점들은 미방문 집합에 둔다. 
3. 간선 탐색: MST 집합에 있는 정점들과 인접한 모든 간선 중 가장 가중치가 작은 간선을 선택한다. 
4. 정점 추가: 선택한 간선으로 연결된 미방문 정점을 MST 집합에 추가한다. 
5. 반복: 3-4 단계를 모든 정점이 MST 집합에 포함될 때까지 반복한다. 

 

 

Prim's Algorithm 코드 

import heapq

def prim(graph, start):
    mst = []  # 최소 신장 트리를 저장할 리스트
    visited = set([start])  # 방문한 정점을 추적하는 집합
    
    # 시작 정점과 연결된 모든 간선을 우선순위 큐에 추가
    edges = [(w, start, v) for v, w in graph[start].items()]
    heapq.heapify(edges)  # 간선을 가중치 기준으로 최소 힙 구성

    while edges:
        w, u, v = heapq.heappop(edges)  # 가장 가중치가 작은 간선 선택
        
        if v not in visited:  # 아직 방문하지 않은 정점이라면
            visited.add(v)  # 정점을 방문 처리
            mst.append((u, v, w))  # 최소 신장 트리에 간선 추가

            # 새로 추가된 정점과 연결된 간선들을 우선순위 큐에 추가
            for next_v, next_w in graph[v].items():
                if next_v not in visited:  # 방문하지 않은 인접 정점에 대해서만
                    heapq.heappush(edges, (next_w, v, next_v))

        # 모든 정점이 연결되면 종료 (간선의 수가 정점 수 - 1이 되면)
        if len(mst) == len(graph) - 1:
            break

    return mst

# 예시 그래프
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'A': 4, 'C': 1, 'D': 5},
    'C': {'A': 2, 'B': 1, 'D': 3, 'E': 6},
    'D': {'B': 5, 'C': 3, 'E': 7},
    'E': {'C': 6, 'D': 7}
}

# 프림 알고리즘 실행 (시작 정점: 'A')
mst = prim(graph, 'A')
print("Prim's 알고리즘으로 찾은 최소 신장 트리:")
for edge in mst:
    print(f"{edge[0]} - {edge[1]} : 가중치 {edge[2]}")