[Algorithm] 📈 최소 신장 트리 (MST, Minimum Spanning Tree)

📖 최소 신장 트리(MST)

🍄 신장 트리(Spanning Tree)

• 연결 그래프에서 그래프 탐색을 통해서 생기는 트리 엣지로 이루어진 사이클을 갖지 않는 최소 부분 그래프를 의미한다.
• 그래프의 모든 정점이 서로 연결되어 있으면서, 순환구조가 반복되지 않는다.
• 최소 부분이란 - 모든 정점을 포함하고, 간선의 개수 : 정점의 개수 -1

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

• 최소 신장 트리란 Spanning Tree중에서 사용된 가중치의 값이 최소인 트리이다.

위와 같이 각 간선들의 길이의 합의 최소가 되는 연결 트리가 MST이다.
이를 구하기 위해서는 2가지 알고리즘이 있다.

• Prim MST 알고리즘 (단계적 확장)
• Kruskal MSt 알고리즘 (Greedy)

🍄 Prim MST

• Tree 와 NotTree를 구분하여 정점을 한 개씩 추가해가면서 T를 채워나간다.

🍄 Kruskal MST

그리디 알고리즘의 일종으로 보통 최소 힙을 이용하여 구한다.
모든 그래프 정점을 최소힙에 넣음으로써 시작한다.

• 시간복잡도 : O(ElogE)

🕸 4번의 사이클 판단 - Union & Find 활용

Union-Find

• 서로소 집합을 표현할 때 사용하는 알고리즘

3가지 연산

• make-set(x)
  • 초기화, arr[i] = i
• union(x, y)
  • 합치기
  • x, y가 속한 집합을 합치는 과정, 일반적으로 parent = x, child = y
  • O(N)
• find(x)
  • 찾기, x가 속한 집합의 최상위 노드 반환
  • O(N-1), 트리의 높이와 시간 복잡도가 동일하다.
  • 경로 압축한 경우 상수 시간

union-find 코드 구현

#### make(){
  for(int i=0; i < N; i++){
    root[i] = i;
  }
}

union(x, y)

boolean union(int from, int to){
  int fromRoot = find(from);
  int toRoot = find(to);

  if(fromRoot == toRoot) return false;
  else root[toRoot] = fromRoot;
  return true;
}

find(x)

int find(int x){
  if(root[x] == x) {
    return x;
  } else{
    return find(root[x]); // 재귀를 이용하는 방식
    return root[x] = find(root[x]);
  }
}

🍄 크루스컬 vs 프림

프림의 시간복잡도 : O( E log(V)) 크루스칼의 시간복잡도 : O( E log(E)) 즉, 그래프 내의 간선이 많은 경우 - 프림알고리즘 간선이 적은 경우 - 크루스칼 알고리즘

🔗 관련 예시

tag:MST

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁