3-5. 최소비용 신장트리

최소비용 신장트리

 

최소 신장 트리  (Minimum Spanning Tree) 

 

• 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것.
• 사례 : 도로 건설, 전기 회로, 통신 ,배관 등등

흔히 아는 트리는 rooted 트리 라고 한다.

싸이클이 없고 연결된(connected), 무방향( Undirected) 그래프를 트리라고 부른다.

 

• Undirected ( 무방향 ) weight( 가중치 ) 그래프이고, 가중치들은 모두 양수이다.
• 싸이클이 없어야 된다.
  • 싸이클이 존재한다고 가정해보자. 그렇다면 싸이클 상의 랜덤한 한 엣지를 버리더라도 모든 노드들은 연결됨.
• 노드가 n 개인 트리는 항상 n-1 개의 엣지를 가짐.
• 해가 유일하지는 않음
• 구현은 Kruskal 알고리즘과 Prim 알고리즘 두 가지 방법으로 가능.

 

Generic MST 알고리즘

• 처음 A는 공집합 이다.
• 집합 A에 대해서 안전한 엣지를 하나 찾은 후 이것을 A에 더해준다.
• 엣지의 개수가 n-1 개가 될 때까지 반복한다. ( MST는 노드가 n 개라면 항상 n-1 개의 엣지를 가진다. )

Kruskal 알고리즘

• 탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것
• 간선 선택을 기반으로 하는 알고리즘
• 이전 단계에서 만들어진 Spanning Tree 와 상관없이 무조건 최소 비용 간선만을 선택하는 방법
• 단 간선을 선택할때 해당 간선을 선택함으로서 사이클이 생기지 않는 간선을 택한다
• 즉 이 간선을 선택했을때 사이클이 생기는지 안생기는지 유무를 검사해야 한다

 

Prim 알고리즘

• 시작 정점에서부터 출발하여 MST 집합을 단계적으로 확장해나가는 방법
• 정점 선택을 기반으로 하는 알고리즘
• 이전 단계에서 만들어진 Spanning Tree 를 확정하는 방법
• 즉 사이클 검사가 필요하지 않다
• 간선이 많은 그래프를 MST 로 만들 때 적합