MST   Minimum Spanning Tree, Minimum Cost Spanning Tree   최소 신장 트리, 최소 비용 신장 트리

(2022-08-13)

Minimum Spanning Tree Algorithm, 최소 신장트리 알고리즘, Kruskal Algorithm, 크루스칼 알고리즘, Prim Algorithm, 프림 알고리즘


1. 최소 비용 신장 트리, 최소 신장 트리 구조
   (Minimum Cost Spanning Tree, Minimum Spanning Tree, MST)

  ㅇ 가중 무방향 그래프에서,               ☞ 그래프 종류 (가중치 그래프, 무방향 그래프)참조
  ㅇ 구성가능한 다수의 신장 트리 중에,
  ㅇ 가중치 합이 최소인 것


2. 최소비용 신장트리 생성 알고리즘 (Minimum Spanning Tree, MST)신장 트리의 생성
     - 주어진 그래프에서, 정점들은 모두 포함하면서, 사이클(루프 순환)을 없애는 것

  ㅇ 최소 신장 트리의 생성
     - 주어진 그래프에서, 모든 임의 경로의 가중치 합이 최소가 되도록, 신장 트리를 만드는 것

  ㅇ 최소 신장 트리알고리즘 전략 :  탐욕 알고리즘에 속함
     - 각 단계 마다 그 순간에 가장 좋은 것(최소 가중치 간선)을 선택하게 됨

  ※ [참고] ☞ 탐욕 알고리즘, 그래프 알고리즘, 스패닝 트리 프로토콜 참조


3. MST 알고리즘의 대표적인 例)

  ㅇ 프림 알고리즘 (Prim Algorithm)
     - 하나의 정점을 시작으로 트리를 점차 확장시켜가며 신장 트리를 만들어감
        . 임의 정점부터 시작하며, 
        . 연결된 연결선 중 최소 가중치를 갖는 연결선을 추가하고,
        . 루프를 만들지 않으면서, 
        . 점차 선택된 정점들에 부속된 연결선들 중 최소 가중치 연결선을 추가하면서,
        . 최소 신장트리가 완성됨
     - 최단 경로를 찾는, 다익스트라 알고리즘과 유사하게 동작

  ㅇ 크루스칼 알고리즘 (Kruskal Algorithm)
     - 루프를 만들지 않으면서도, 최소 가중치를 갖는 연결선을 하나씩 추가하며, 신장트리 작성
        . 가중치로 간선을 정렬한 후, 사이클이 형성되지 않도록 하며, 
        . 간선을 하나씩 선택 또는 삭제하며 신장트리를 만들어감
     - 순환을 피하며 단순히 그 시점에 최소 가중치를 갖는 연결선을 선택하며,
        . 연결선 단위신장 트리를 구축하는 탐욕 알고리즘 접근법
     - 최초에는 연결선이 전혀 없는 n개 개별 정점, n개 개별 트리로부터 시작
        . n-1개 연결선을 더하고 나면 모든 트리가 합쳐져서 하나의 신장 트리가 됨

그래프 알고리즘
   1. 그래프 알고리즘   2. 그래프 순회 (DFS,BFS)   3. 깊이 우선 탐색 (DFS)   4. 너비 우선 탐색 (BFS)   5. 위상 정렬   6. 최소 신장 트리   7. 최단 경로   8. 다익스트라 알고리즘   9. 플로이드 알고리즘  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"