"최소 비용 신장 트리(Minimum Spanning Tree: MST)"를 찾는 방법

간선에 방향이 없는 그래프에서
"최소 비용 신장 트리(Minimum Spanning Tree: MST)"를 찾는 방법


신장 트리(Spanning Stees)
간선에 방향이 없는 그래프에서 
신장 트리는 
모든 정점들을 연결 할 수 있는 트리를 의미
부분 그래프가 아니라 부분 트리(tree) 임
트리에는 싸이클이 포함될 수가 없음

그래서, 어떤 그래프의 신장트리는 여러가지가 될 수 있다는 의미

    A
   /  \
  B -- C  이건 그래프: 정점3개, 간선 3개

    A
   /  \
  B    C  이건 트리: 정점3개, 간선 2개

     A
   /  
  B -- C  이건 트리: 정점3개, 간선 2개

    A
      \
  B -- C  이건 트리: 정점3개, 간선 2개

"최소 비용 신장 트리" 로 개념 확장: 간선에 가중치가 있는 경우
세가지 신장트리는 
어떤 간선이 빠졌는지에 따라서,
남아있는 간선들의 가중치의 합이 서로 다름

     A 
 1 /  \ 2
  B -- C  그래프 (간선에 가중치가 있는 경우)
    3

     A
 1 /  \ 2
  B    C  신장 트리: 전체 비용= 1+2 = 3

     A
 1 /  
  B -- C  신장 트리: 전체 비용= 1+3 = 4
     3

      A
         \ 2
  B -- C  신장 그래프: 전체 비용= 2+3 = 5
     3

신장 트리 중에서 가중치의 합이 최소가 되는 것을
"최소 비용 신장 트리"라고 부름
줄여서 "최소 신장 트리" 라고 부름
앞에서, 최단 거리 찾을때는
가중치를 거리라고 많이 불렀는데.
여기서는, 비용으로 이해하는 것이 직관적임

현실에서는 
전력망을 구축한다던가, 인터넷 케이블을 설치한다든가, 할때와 같이
필요한 곳들이 모두 연결되면서도 비용이 최소가 되어야 하는 경우. 에 응용

참고로,
최소 비용 신장 트리에서는
정점의 개수 - 1 = 간선의 개수
즉, 정점을 모두 연결할 수 있는 최소한의 간선 개수

최소 비용 신장 트리 찾을때: 
1) 프림(Prim) 알고리즘 사용
다익스트라와 유사

최소신장트리를 찾는 과정은
정점들을 하나하나 더해가는 과정으로 이해 가능
목표: 모든 정점들을 연결 시키는 것, 이때 전체 비용을 줄이고 싶은 것
방법:
그리디 전략 사용: 간선의 비용이 가장 적은 것을 선택

0번 부터 시작한다고 하면,
0번에서 연결되어있는 간선 들 중,
가중치가 가장 작은 간선을 선택
그럼, 그 가장 작은 간선과 연결된 정점은 
신장 트리에 포함시킴
나머지 정점들도 모두 포함되도록 진행
신장 트리에 포함된 모든 정점들에서
연결된 모든 간선들에서 
가중치가 가장 작은 간선을 선택
그 연결된 정점을 신장트리에 포함시킴
신장 트리에 포함된 모든 정점들에서
연결된 모든 간선들에서
가중치가 가장 작은 간선을 선택
그 연결된 정점을 신장트리에 포함시킴
신장 트리에 포함된 모든 정점들에서
연결된 모든 간선들에서
가중치가 가장 작은 간선을 선택
그 연결된 정점을 신장트리에 포함시킴
... 계속
이런식으로 모든 정점들이 추가가 될때까지 진행을 하면 
최소 비용 신장 트리를 찾을 수 있음
어떤 정점의 간선을 먼저 추가할 지는
"우선 순위 큐"를 사용


2) 크러스컬(Kruskal) 알고리즘
간선들을 가중치가 작은 순서대로 정렬해놓고
하나하나 더해가는 단순한 그리디 알고리즘

새로운 간선이 불필요하게 싸이클을 만드는 경우에는 추가를 하면 안됨
    A
   / |<-- 추가 하면 안됨. 싸이클 생성됨
 B--C

반대로, 서로다른 그룹 두개를 연결시켜서 하나로 만들어주는 간선이라면 꼭 추가를 해야 함 
          A--B
          | <-- 추가 해야 됨. 하나로 만들어줌
   C--D

어떤 간선을 추가할지 말지를 판단할때, 
유니언-파인드(Union-Find) 알고리즘 사용
=> 연결관계를 하나하나 늘려는 과정에서,
두 정점이 같은 그룹에 속해있는지, 아니면 서로 다른 그룹 인지를 판단할때 사용