신장트리_SpanningTree, MST

신장트리(Spanning Tree)

• 그래프 내의 모든 정점을 포함하는 트리
• 그래프의 최소 연결 부분 그래프다.
  • 최소연결 : 간선의 수가 가장 적다
  • n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 spanning tree가 된다.
• 그래프에서 일부 간선을 선택해서 만든 트리

특징

• BFS,DFS 를 이용해서 그래프에서 신장트리를 찾을 수 있다.
  • 탐색 도중에 사용된 간선만 모으면 만들 수 있다.
• 하나의 그래프에서 많은 신장 트리가 존재할 수 있다.
• Spanning tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다.
• Spanning tree는 그래프에 있는 n개의 정점을 정확히 (n-1.)개의 간선으로 연결해야 한다.

최소 신장트리 MST(Minimum Spanning Tree)

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

특징

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