Minimum Spanning Tree (MST)

Spanning Tree

Spanning Tree란?

• 그래프 내의 모든 정점을 포함하는 트리
• Spanning Tree = 신장 트리 = 스패닝 트리
• Spanning Tree는 최소 연결 부분 그래프입니다.
  • 최소 연결 = 간선의 수가 가장 적습니다.
  • n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 됩니다. 이것이 바로 Spanning Tree가 됩니다.
• 즉, 그래프에서 일부 간선을 선택해서 만든 트리

Spanning Tree의 특징

• DFS, BFS

  을 이용하여 그래프에서 신장 트리를 찾을 수 있습니다.

  • 탐색 도중에 사용된 간선만 모으면 만들 수 있습니다.

• 하나의 그래프에는 많은 신장 트리가 존재할 수 있습니다.

• Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안됩니다.

  • 사이클이란?
    • 경로 중에서 시작점과 도착점이 같은 경우를 사이클이라고 합니다.
    • 예시) ‘A’->C->B->’A’ ‘A’->C->E->B->’A’ ‘A’->C->D->E->B->’A

• 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결합니다.

Spanning Tree의 사용 사례

통신 네트워크 구축

• 예를 들어, 회사 내의 모든 전화기를 가장 적은 수의 케이블을 사용하여 연결하고자 하는 경우
• n개의 위치를 연결하는 통신 네트워크를 최소의 링크(간선)를 이용하여 구축하고자 하는 경우, 최소 링크의 수는 (n-1)개가 되고, 따라서 Spanning Tree가 가능해집니다.

MST

MST란?

• Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리
  • MST = Minimum Spanning Tree = 최소 신장 트리
• MST는 연결된(connected) 무방향(undirected)의 가중치(weight) 그래프를 가정합니다.
  • 각 간선의 가중치들은 방금 전에 언급한 비용(cost)을 의미합니다.
  • 다시 말하면 MST는 모든 정점을 연결하여 트리를 생성하는데,
  • 사용된 간선들의 가중치(비용)의 합을 최소화 하는 트리를 찾는 것이 목적입니다.
• 즉, 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것입니다.

MST의 특징

1. 간선의 가중치의 합이 최소여야 합니다.
2. n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 합니다.
3. 사이클이 포함되어서는 안됩니다.

MST의 사용 사례

• 통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우

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

MST 구현 방법

Kruskal MST 알고리즘

• 탐욕적인 방법(greedy method)을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것입니다.
  • MST(최소 비용 신장 트리) 가 1) 최소 비용의 간선으로 구성됨 2) 사이클을 포함하지 않음 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택합니다.
  • 간선 선택을 기반으로 하는 알고리즘입니다.
  • 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법입니다.
• [과정]
  1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
  2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택합니다.
     • 즉, 가장 낮은 가중치를 먼저 선택합니다.
     • 사이클을 형성하는 간선을 제외합니다.
  3. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가합니다.

구현 코드

# 크루스칼 알고리즘
 
 
# 모든 간선의 정보를 저장할 클래스. a는 한 쪽 노드, b는 다른 한 쪽 노드이며 dist는 a와 b 사이의 가중치(거리)이다.
class Edge:
    def __init__(self, a, b, dist):
        self.a = a
        self.b = b
        self.dist = dist
 
 
# 루트 노드를 반환하는 함수.
# 루트 노드를 구할 때 그냥 root[x]해도 되겠지만 집합 처리 개념을 사용하기 위해 함수로 따로 빼냈다.
def find_set(x):
    return root[x]
 
 
# 두 트리를 병합하는 함수. 일관성을 위해 노드 번호가 더 작은 것을 루트로 만든다.
def union_set(a, b):
    a = find_set(a)
    b = find_set(b)
    if a < b:
        root[b] = a
    else:
        root[a] = b
 
 
# edges에는 [정점 a, 정점 b, a-b 사이의 거리]를 담은 Edge 객체들이 저장되어 있다.
edges = list()
edges.appendb(Edge(1, 7, 12))
edges.append(Edge(1, 4, 28))
edges.append(Edge(1, 2, 67))
edges.append(Edge(1, 5, 17))
edges.append(Edge(2, 4, 24))
edges.append(Edge(2, 5, 62))
edges.append(Edge(3, 5, 20))
edges.append(Edge(3, 6, 37))
edges.append(Edge(4, 7, 13))
edges.append(Edge(5, 6, 45))
edges.append(Edge(5, 7, 73))
 
n = len(edges)
root = [i for i in range(n)]  
# 모든 트리의 루트를 저장. 맨 처음에는 노드가 하나의 트리이므로 자기 자신이 루트이다.
 
total = 0  # 최단 거리
 
edges.sort(key=lambda x: x.dist)  # 우선 간선을 가중치 순으로 정렬. 가중치가 작은 순으로 순회
 
for edge in edges:  # 모든 간선에 대해서 반복한다.
    if find_set(edge.a) != find_set(edge.b):
    # 두 노드가 포함된 트리의 루트가 서로 다를 때(=두 트리를 합쳐도 사이클이 생기지 않을 때)
        union_set(edge.a, edge.b)  # 두 노드(가 포함되어 있는 트리)를 병합
        total += edge.dist
print(total)

Prim MST 알고리즘

• 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법
  • 정점 선택을 기반으로 하는 알고리즘입니다.
  • 이전 단계에서 만들어진 신장 트리를 확장하는 방법입니다.
• [과정]
  1. 시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함됩니다.
  2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장합니다.
     • 즉, 가장 낮은 가중치를 먼저 선택합니다.
  3. 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복합니다.

!

MST 관련 문제

• 최소 스패닝 트리-백준1197번

• 네트워크 연결-백준1922번

참고자료

• https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html
• https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html