최소신장트리(Minimum Spanning Tree)

이 포스팅은 정보관리기술사의 자료구조/알고리즘 토픽 중 한 가지인 최소신장트리(Minimum Spanning Tree)에 관한 정보를 다룬다. 최소신장트리의 정의, 용어, 알고리즘, 활용 방안 등의 내용을 포함한다. 미흡한 점이 있기에 다른 전문가의 정보도 함께 찾아보시기를 바랍니다. 또한 맞춤법 및 단어 선정, 문법적인 오류, 오탈자가 있거나 불편함이 있을 수 있습니다. 감사합니다.

---

최소신장트리(Minimum Spanning Tree)의 정의

최소신장트리(Minimum Spanning Tree, MST)는 가중치가 부여된 무방향 그래프에서 선택한 트리 중, 모든 노드를 포함하면서 가중치의 합이 최소가 되는 트리를 말한다. 이 트리는 원래 그래프의 모든 노드를 포함하며, 사이클을 형성하지 않습니다. 최소 신장 트리를 찾는 것은 네트워크 설계, 클러스터 분석, 그리고 여러 최적화 문제 등 다양한 분야에서 응용하고 있다.

최소 신장 트리를 찾기 위한 대표적인 알고리즘으로는 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 있다.

---

그래프 용어 정의

• 방향 그래프(Directed Graph): 간선에 방향이 있는 그래프
• 가중치 그래프(Weighted Graph): 간선과 연관된 값이 있는 그래프
• 경로(Path): 한 정점에서 다른 정점까지 도달하기 위해 지나는 일련의 정점(정점 사이에는 간선이 있어야 함)
• 단순경로(Simple Path): 같은 정점을 두 번 지나지 않는 경로
• 순환(Cycle): 한 정점에서 다시 그 정점으로 돌아오는 경로
• 순환 그래프(Cyclic Graph): 순환이 존재하는 그래프
• 경로의 길이(Length): 가중치 그래프에서 경로를 구성하는 간선들의 가중치의 합을 말하며, 비 가중치 그래프에서는 경로를 구성하는 간선의 수를 말함
• 인접 정점(Adjacent Vertex) 정점 Vi와 Vj를 잇는 간선이 있으면 Vi와 Vj는 인접 정점이라 함

최소신장트리 용어

---

최소신장트리를 구하는 두 가지 알고리즘

크루스칼(Kruskal) 알고리즘

크루스칼 알고리즘은 가장 가벼운 가중치를 가진 간선부터 선택하여 MST를 구성한다. 단, 선택된 간선이 사이클을 형성할 때는 그 간선을 제외한다. 이 과정을 모든 노드가 연결될 때까지 반복한다. 크루스칼 알고리즘은 유니온-파인드(Union-Find) 자료구조를 사용하여 효율적으로 사이클을 확인할 수 있다.

 

1. 그래프 내 모든 edge를 가중치 오름차순으로 정리
2. 현 edge 중 가장 작은 edge 선택
3. 두 정점 연결 후 사이클 형성되면 버리고 아니면 신장트리에 삽입
4. 위 과정을 반복, 모든 정점 연결되면 버림

프림(Prim) 알고리즘

프림 알고리즘은 임의의 정점에서 시작하여, MST(Minimum Spanning Tree)에 인접한 간선 중 최소 가중치를 가진 간선을 선택하여 트리를 확장해 나갑니다. 이 과정을 모든 노드가 트리에 포함될 때까지 반복한다. 프림 알고리즘은 우선순위 큐를 사용하여 효율적으로 최소 가중치 간선을 찾을 수 있다.

 

1. 임의의 시작 정점 선택, 루트노드로 삽입
2. 인접 정점 중 가중치가 가장 작은 간선 선택하여 최소 신장 트리에 삽입(사이클 형성되면 버림)
3. 위 과정을 반복, 모든 정점 연결되면 완료

 

차이점

크루스칼 알고리즘은 전체 간선에 대해 가중치를 기준으로 정렬한 후 MST를 구성하는 반면, 프림 알고리즘은 특정 노드에서 시작하여 점진적으로 트리를 확장한다.

크루스칼 알고리즘은 사이클을 형성하지 않는 간선을 선택하는 데 집중하고, 프림 알고리즘은 이미 선택된 노드들과 인접한 간선 중 최소 가중치를 가진 간선을 선택한다.

---

최소신장트리 비용 인접 리스트

비용 인접 리스트는 각 정점의 노드와 노드의 가중치를 표기하여 그래프를 표기하는 방식을 말함

 

최소신장트리 그래프

Python

# 예를 들어, 각 정점과 연결된 간선 및 가중치를 나타내는 인접 리스트

graph = {

'A': [('B', 2), ('C', 3)],

'B': [('A', 2), ('C', 1), ('D', 1), ('E', 4)],

'C': [('A', 3), ('B', 1), ('F', 5)],

'D': [('B', 1), ('E', 1)],

'E': [('B', 4), ('D', 1), ('F', 1)],

'F': [('C', 5), ('E', 1)]

}

---

최소신장트리의 활용 방안

• 네트워크 설계: 최소 신장 트리는 통신 네트워크, 전력 그리드, 컴퓨터 네트워크 등의 설계에 널리 사용된다. 최소한의 비용으로 모든 지점을 연결하여 효율적인 네트워크 설계를 가능하게 한다.(DFS, BFS 활용)
• 클러스터링 알고리즘: 데이터 포인트들 사이의 거리를 기반으로 클러스터를 형성할 때 최소신장트리가 사용될 수 있다. 예를 들어, 머신러닝에서는 MST를 사용하여 데이터를 자연스러운 그룹으로 나누는 데 도움을 준다.
• 회로 설계 및 VLSI(대규모 집적회로) 설계: 전자 회로의 핵심 구성 요소를 연결하는 데 필요한 배선 길이를 최소화하기 위해 MST가 사용된다. 이는 회로의 크기와 비용을 줄이는 데 이바지한다.
• 도로, 파이프라인 및 기타 교통망 설계: 최소 신장 트리는 도로망, 수도 및 가스 파이프라인, 철도망 등의 기반 구축에 있어 총 건설 비용을 최소화하는 데 사용된다.
• 이미지 처리: 이미지의 영역 분할(segmentation)에서 최소 신장 트리를 이용해 이미지의 다른 부분을 구분하기도 한다. 이를 통해 이미지에서 중요한 구조를 식별하고 분석할 수 있다.
• 물류 및 배송: 물류 네트워크에서 각 지점을 최소 비용으로 연결하여 전체 배송 비용을 줄이는 데 MST가 활용된다.