[백준-9372] 상근이의 여행 을 풀고 문제를 푼 사람들의 의견을 보던 중, 이 문제는 DFS, BFS로도 풀 수도 있지만 최소 스패닝 트리로 풀어도 된다고 적혀있었다.
그래서 최소 스패닝 트리가 무엇인지 알아보려고 한다.

참고 링크

• http://www.ktword.co.kr/test/view/view.php?m_temp1=3444
• https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

스패닝 트리(Spanning Tree : 신장 트리)

스패닝 트리란?

: 노드 간 경로가 오직 하나 뿐인 토폴로지

• 루프 순환이 없는 그래프의 일종
• 주로, 루프 순환의 방지를 위한 트리 특성을 갖는 그래프

특징

• DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다.
  -> 탐색 도중에 사용된 간선만 모으면 만들 수 있다.

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

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

• 무방향 그래프의 일종
  -> 비순환(루프 순환이 없음)
  -> 모든 노드들이 연결되어 있어야 함
  -> 간선 갯수가 노드 - 1 개 여야 한다.

• 사실상, 신장 트리 구조는
  -> 최상의 정점(중심)을 루트 노드로 하고,
  -> 모든 그룹 멤버들을 자손으로 갖는 트리구조 이다.

• 특징
  -> 모든 정점들의 연결에 끊임이 없어야 함
  -> (간선의 수 + 1) = (정점의 수)

사용 사례

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

최소 스패닝 트리(MST : Minimum Spanning Tree)

• 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지지 않는다.
• MST는 간선에 가중치를 고려하여 최소 비용의 스패닝 트리를 선택하는 것을 말한다.
• 즉, 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이다.

특징

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

사용 사례

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

최소비용 신장 트리 생성 알고리즘

• 신장 트리의 생성
  -> 주어진 그래프에서 정점들은 모두 포함하면서 사이클(루프 순환)을 없애는 것

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

대표적인 예

• 프림 알고리즘(Prim Algorithm)
  -> 하나의 정점을 시작으로 트리를 점차 확장시켜가며 신장 트리를 만들어감

1. 임의의 정점부터 시작
2. 연결된 연결선 중 최소 가중치를 갖는 연결선을 추가
3. 루프를 만들지 않음
4. 점차 선택된 정점들에 부속된 연결선들 중 최소 가중치 연결선을 추가하며 신장트리 작성

• 쿠르스칼 알고리즘(Kruskal Algorithm)
  -> 루프를 만들지 않으면서 최소 가중치를 갖는 연결선을 하나씩 추가하며 신장트리 작성