MST(Minimum Spanning Tree)
📢 목차
- 그래프
- 신장트리 (Spanning Tree)
- 최소신장트리 (Minimum Spanning Tree)
1. 그래프
📖 그래프 (Graph)
- 연결되어 있는 원소간의 관계를 표현한 자료구조
- 연결할 객체를 표현하는 정점(Vertex)와 객체를 연결하는 간선(Edge)로 구성된 집합
1-1. 종류
- 무방향 그래프
- 간선에 방향이 없는 그래프
- 방향 그래프
- 간선에 방향이 있는 그래프
- 완전 그래프
- 한 정점에서 모든 정점에 연결되어 최대 간선 수를 갖는 그래프
- 부분 그래프
- 완전그래프가 아닌 그래프
- 연결 그래프
- 떨어져있는 정점이 없는 그래프
- 단절 그래프
- 연결 그래프가 아닌 그래프
- 가중 그래프
- 간선에 가중치가 있는 그래프
- 유향 비순환 그래프(DAG)
- 사이클이 없는 방향 그래프
1-2. 용어
- 차수 : 정점에 부속되어있는 간선의 수
- 진입차수 : 정점을 머리로하는 간선의 수
- 진출차수 : 정점을 꼬리로 하는 간선의 수
- 경로 : 정점 $V_i$에서 정점$V_j$까지 간선으로 연결되는 정점을 순서대로 나열한 리스트
- 단순경로 : 서로 다른 정점으로 연결된 경로
- 사이클 : 단순경로중 시작 정점과 마정점이 같은 경로
1-3. 구현
- 🔽 인접 행렬
- 정점의 개수를 V라고 했을 때, V x V 크기의 2차원 배열을 이용
- 정점의 연결관계를 0과 1로 표현
- 장점
- 정점 V1와 정점 V2의 연결 여부를 O(1)에 알수 있다.
- 단점
- 실제 연결된 정점의 수와 관계없이 연결된 정점을 찾는데 O(n)이 소요됨
public class Graph { private int[,] adjMatrix; public Graph(int N) { adjMatrix = new int[N, N]; } // 무방향 그래프일 경우 public void insert(int i, int j) { adjMatrix[i,j] = 1; adjMatrix[j,i] = 1; } // 방향 그래프일 경우 i -> j public void insert(int i, int j) { adjMatrix[i,j] = 1; } // i와 j가 연결되어있는지 여부 public bool isConnect(int i, int j) { return adjMatrix[i,j] == 1; } // 정점 v의 간선의 수 public int getEdge(int v) { int cnt = 0, length = adjMatrix.getLength(0); for(int i = 0; i< length ; i++) { for(int j= 0; j <= i); j++) { if(adjMatrix[i,j] == 1) cnt++; } } return cnt; } }
- 🔽 인접 리스트
- 각각의 정점에 대하여 인접한 정점 번호를 저장
- 링크드 리스트를 이용해서 구현
- A[i] = i 와 연결된 정점을 링크드 리스트로 포함하고 있음
- 장점
- 정점과 연결된 정점을 찾는데 필요한 만큼만 시간이 소요됨
- 단점
- 정점 V1와 정점 V2의 연결 여부를 알기위해서 연결된 정점을 모두 살펴봐야한다.
public class Graph { private LinkedList<int>[] adjList; public Graph(int N) { adjList= new LinkedList<int>[N]; for(int i = 0; i < N; i++) { adjList[i] = new LinkedList<int>(); } } // 무방향 그래프일 경우 public void insert(int i, int j) { adjList[i].AddLast(j); adjList[j].AddLast(i) } // 방향 그래프일 경우 i -> j public void insert(int i, int j) { adjList[i].AddLast(j) } // i와 j가 연결되어있는지 여부 public bool isConnect(int i, int j) { foreach(int n in adjList[i]) { if(j == n) return true; } return false; } // 정점 v의 간선의 수 public int getEdge(int v) { return adjList[v].Count; } }
2. 신장트리(Spanning Tree)
📖 **신장트리 (Spanning Tree)**
- 그래프 내의 모든 정점을 포함하는 트리
- 그래프의 최소 연결 부분 그래프
- 최소 연결 = 연결 그래프 중에 간선의 수가 최소이다.
- n개의 정정을 가지고 있는 연결 그래프의 최소 간선의 수는 (n-1)
2-1. 특징
- DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다
- 하나의 그래프에는 여러 개의 신장트리가 존재할 수 있다.
- 모든 정점들이 연결되어 있어야 하고, 사이클이 포함되어서는 안된다.
3. 최소신장트리(Minimum Spanning Tree)
📖 최소신장트리 (Minimum Spanning Tree)
- 신장트리에서 사용된 간선들의 가중치 합이 최소인 트리
- 간선들의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소비용이 얻어지지 않는다.
- 객체를 연결할 때 비용이 최소로 되는 경우에 사용된다.
3-1. 특징
- 간선의 가중치의 합이 최소여야 한다.
- n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
- 사이클이 포함되어서는 안된다.
3-2. 구현
1️⃣ Kruskal MST 알고리즘
탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것
- MST(최소 비용 신장 트리) 가 1) 최소 비용의 간선으로 구성됨 2) 사이클을 포함하지 않음 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 한다.
- 간선 선택을 기반으로 하는 알고리즘이다.
- 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이다.
의사코드(Pseudo Code)
- 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
- 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
- 즉, 가장 낮은 가중치를 먼저 선택한다.
- 사이클을 형성하는 간선을 제외한다
- .해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다.
- 🔽 UnionFind.cs 코드
using System;
public class Edge : IComparable<Edge>
{
public int from { get; private set; }
public int to { get; private set; }
public int weight { get; private set; }
public Edge(int from, int to, int weight)
{
this.from = from;
this.to = to;
this.weight = weight;
}
public int CompareTo(Edge other)
{
if (weight < other.weight)
return -1;
if (weight > other.weight)
return 1;
return 0;
}
}- 🔽 UnionFind.cs 코드
public class UnionFind
{
int[] parents;
public UnionFind(int N)
{
parents = new int[N];
}
public int Find(int x)
{
if (parents[x] == x) return x;
return parents[x] = Find(parents[x]);
}
public bool isUnion(int a, int b)
{
a = Find(a);
b = Find(b);
if (a == b) return true;
else return false;
}
public void Union(int a, int b)
{
a = Find(a);
b = Find(b);
if (a < b) parents[b] = a;
else parents[a] = b;
}
}- 🔽 Kruskal.cs 코드
using System;
using System.Collections.Generic;
public class Kruskal
{
public Kruskal(int N, string[] input)
{
List<Edge> edges = new List<Edge>();
UnionFind uf = new UnionFind(N);
foreach (string str in input)
{
string[] split = str.Split(" ");
int from = Convert.ToInt32(split[0]);
int to = Convert.ToInt32(split[1]);
int weight = Convert.ToInt32(split[2]);
edges.Add(new Edge(from, to, weight));
}
edges.Sort();
int sum = 0;
for (int i = 0; i < edges.Count; i++)
{
if (!uf.isUnion(edges[i].from, edges[i].to))
{
sum += edges[i].weight;
uf.Union(edges[i].from, edges[i].to);
}
}
Console.WriteLine(sum);
}
}
2️⃣ Prim MST 알고리즘
시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법
- 정점 선택을 기반으로 하는 알고리즘이다.
- 이전 단계에서 만들어진 신장 트리를 확장하는 방법이다.
의사코드(Pseudo Code)
- 시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다.
- 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
- 즉, 가장 낮은 가중치를 먼저 선택한다.
- 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복한다.
- 🔽 Edge.cs 코드
public class Edge
{
public int to;
public int weight;
public Edge(int to, int weight)
{
this.to = to;
this.weight = weight;
}
}- 🔽 Graph.cs 코드
using System.Collections.Generic;
public class Graph
{
List<Edge>[] edges;
public Graph(int N)
{
edges = new List<Edge>[N];
for(int i = 0; i < N; i++)
{
edges[i] = new List<Edge>();
}
}
public void insert(int from, int to, int weight)
{
edges[from].Add(new Edge(to, weight));
}
public List<Edge> get(int v)
{
return edges[v];
}
}- 🔽 PrimMST.cs 코드
using System;
using System.Collections.Generic;
public class PrimMST
{
public PrimMST(int N, string[] input, int start)
{
Graph graph = new Graph(N);
foreach (string str in input)
{
string[] split = str.Split(" ");
int from = Convert.ToInt32(split[0]);
int to = Convert.ToInt32(split[1]);
int weight = Convert.ToInt32(split[2]);
graph.insert(from, to, weight);
}
PriorityQueue<Edge, int> pq = new PriorityQueue<Edge, int>();
bool[] isVisited = new bool[N];
pq.Enqueue(new Edge(start, 0), 0);
int sum = 0;
while (pq.Count != 0)
{
Edge edge = pq.Dequeue();
int v = edge.to;
int weight = edge.weight;
if (isVisited[v])
continue;
isVisited[v] = true;
sum += weight;
List<Edge> edges = graph.get(v);
foreach (Edge e in edges)
{
if (!isVisited[e.to])
pq.Enqueue(e, e.weight);
}
}
Console.WriteLine(sum);
}
}