신장 트리(Spanning Tree)

신장 트리(Spanning Tree)

---

• 한 그래프의 부분 그래프이며, 그래프에서 모든 정점을 포함한다.
• 정점 간 서로 연결이 되어있어야 한다.
• 사이클이 존재하지 않는다.
• 그래프에서 신장트리는 1개가 아닌 다수일 수 있다.
• 신장트리는 트리이다.
  • 원래 그래프에서 n개의 정점을 가지고 있었다면, 신장 트리는 n개의 정점과 n-1개의 간선을 가진다.

그래프 자료구조에 대한 자세한 설명은 아래 링크에 기술되어 있다.

그래프(Graph)

 

 

 

 

 

최소 비용 신장 트리(MST - Minimum cost Spanning Tree)

---

• 신장 트리이다.
• 가중치 무방향 그래프이다.
• 신장 트리의 비용은 간선의 비용의 합이다.
• 가장 적은 비용의 신장 트리를 찾는 것이 궁극적인 목적이다.

 

 

 

MST를 찾는 알고리즘

 최소 비용 신장 트리를 만드는 알고리즘으로는 대표적으로 세가지가 있다.

 

크루스칼 알고리즘(Kruskal's Algorithm)

• n개의 정점과 0개의 간선으로 시작한다.
• 비용이 적은 간선을 제일 먼저 고려하면서 간선을 추가한다.
• 간선을 추가할 때에는 이미 선택된 간선들과 사이클이 형성되지 않는 간선을 선택해서 추가한다.

프림 알고리즘(Prim's Algorithm)

• 임의의 정점 1개로 시작하여 정점과 간선를 계속 추가해서 n개의 정점를 가지는 트리로 만든다.
• 정점과 간선을 추가할 때는 가장 적은 비용의 간선을 기준으로 추가한다.

솔린 알고리즘(Sollin's Algorithm)

• n개의 정점과 0개의 간선으로 시작한다.
• 각각의 정점 혹은 트리는 다른 정점이나 트리로 가는 가장 적은 비용의 엣지를 선택한다.
• 사이클이 만들어지거나 중복되는 선택을 제거한다. 
• 모든 정점혹은 트리가 이어져 한개의 정점/트리가 될때 까지 반복한다.