최소 신장 트리

• 부분 그래프(Subgraph): 그래프의 정점과 간선의 일부를 선택하여 만든 그래프
• 신장 부분 그래프(Spanning Subgraph): 그래프의 모든 정점을 포함하는 부분 그래프
• 신장 포레스트(Spanning Forest): 사이클이 없는 신장 부분 그래프
• 신장 트리(Spanning Tree): 모든 정점이 연결된 신장 포레스트
• 최소 비용 신장 트리(Minimum Spanning Tree): 간선의 가중치의 모든합이 최소인 신장 트리

최소 신장 트리(Minimum Spanning Tree)

• 최소 비용으로 모든 정점을 연결하는 비용을 구하는 알고리즘
• 종류
  -Prim's Algorithm
  -Kruskal's Algorithm

Prim's Algorithm

• 시간 복잡도: O(V^2), O(Elog(E)), O(E+VlogV)

1. 맨 처음 정점을 MST에 넣어줌.
2. MST에 있는 정점에서 뻗어 나가는 간선들 중에서 가중치가 가장 작은 간선을 선택해줌.
3. 만약 MST에 추가할 수 있다면 MST에 추가해 줌.

이미지 도식화

 

코드

int n,m,c[10101],d[10101];
vector<pair<int,int>> g;
int prim(){
  int ret=0;
  for(int i=1;i<=n;i++) d[i]=1e9;
  d[1]=0;
  for(int i=1;i<=n;i++){
    int v=-1;
    for(int j=1;j<=n;j++){
      if(c[i]) continue;
      if(v==-1||d[v]>d[i]) v=i;
    }
    c[v]=1;
    ret+=d[v];
    for(auto [i,w]:g[v]) d[i]=min(d[i],w);
  }
  return ret;
}

 

정점 찾기

• 정점을 빠르게 찾기 위해서는 min-heap을 사용하여서 찾을 수 있음.

코드

int n,m,C[10101],D[10101];
vector<pair<int,int>> g;
int prim(){
  int ret=0;
  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
  c[1]=1;
  for(auto [i,w]:g[1]) q.push({w,i});
  while(!q.empty()){
    auto [c,v]=q.top();
    q.pop();
    if(C[v]) continue;
    C[v]=1;
    ret+=c;
    for(auto [i,w]:g[v]) q.push({w,i});
  } 
  return ret;
}

 

시간 복잡도

• 각 간선을 한 번씩 보기 때문에 거리 갱신은 최대 O(E) 번 발생
• Heap에 원소를 O(E)번 삽입
• Heap의 크기는 최대 O(E)이므로 시간 복잡도는 O(E logE)

Kurskal's Algorithm

• 시간 복잡도: O(E logE)
• Spanning Tree에 간선을 하나씩 포함시키는 방식

1. 모든 간선을 가중치에 따라서 오름 차순으로 정렬시킴
2. 가중치가 작은 간선부터 보면서, 사이클이 생기지 않는다면 해당 간선을 MST에 추가해 줌.
   -도중에 트리가 여러 개 발생할 수 있기 때문에 u와 v가 같은 트리에 있는지 확인해야 함.

이미지 도식화

 

코드

int n,m,p[10101];
vector<tuple<int,int,int>> E;
int Find(int v) {
  return v==p[v]?v:p[v]=Find(p[v]);
}
bool Union(int u,int v){
  return Find(u)!=Find(v)&&(p[p[u]]=p[v],true);
}
int f(){
  int ret=0;
  for(int i=1;i<=n;i++) p[i]=i;
  sort(E.begin(),E.end());
  for(auto [w,u,v]:E) if(Union(u,v)) ret+=w;
  return ret;
}

 

시간 복잡도

• 간선 정렬: O(E logE)
• Union Find연산: O(log V) 연산을 O(E) 번 수행
• 시간 복잡도: O(E logE)