[Algorithm] MST(최소 비용 신장 트리 선택)

신장 트리

그래프 내 모든 정점이 연결되어있는 트리

• 모든 정점들이 연결 되어 있어야 함
• 사이클을 포함해서는 안됨
  => 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결

MST

Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리

• 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택
• 모든 정점들을 가장 적은 수의 간선과 비용으로 연결

=> 간선의 가중치의 합이 최소여야 함

• 구현 알고리즘
  • Kruskal
  • Prim

Kruskal

1. 가중치 기준으로 오름차순 정렬
2. 선택되지 않은 정점 중에서 가장 낮은 가중치 가진 정점 고름
3. 두 개의 정점이 부모가 같은지 보고(union-find 활용) 다르면 같은 부모로 합 + MST 집합에 추가

• 시간 복잡도
  • 간선 E 개를 효율적인 알고리즘으로 정렬한다면 : $O(ElogE)$
  • 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우에 적합

class Line implements Comparable<Line> {
  int start, end, weight;
  
  public Line(int start, int end, int weight) {
    this.start = start;
    this.end = end;
    this.weight = weight;
  }
  
  @Override
  public int compareTo(Line obj) {
    return Integer.compare(this.weight, obj.weight);
  }
}

public static void main() {
  // 모든 간선에 대해 시작, 끝, 가중치를 가진 클래스로 우선순위 큐에 입력
  PriorityQueue<Line> pq = new PriorityQueue<Line>();
  
  while(!pq.isEmpty()){
    Line line = pq.poll();
    
    int startParent = findParent(line.start);
    int endParent = findParent(line.end);
    
    // 만약 최상위부모노드가 같으면 선택하지 않음
    // 선택된다면 루프가 발생할 수 있기 때문에
    if (start == endParent) 
      continue;
    
    union(line.start, line.end);
  }
}

Union-Find

사이클 생성 여부를 확인하는 방법

int[] parent = new int[n];

// 자기 자신의 부모를 자신으로 초기화
for (int i = 0; i < n; i++) {
  parent[i] = i;
}

for (Node node : nodes) {
  int fromRoot = findParent(node.from);
  int toRoot = findParent(node.to);
  
  if (fromRoot == toRoot)
    continue;

  union(node.from, node.to);
}

public int findParent(int n) {
  if (parent[n] == n) {
    return parent[n];
  }
  else parent[n] = findParent(parent[n]);
}

public void union(int n1, int n2) {
  int p1 = findParent(n1);
  int p2 = findParent(n2);
  
  parent[p1] = p2;
}

Prim

1. 우선순위 큐를 이용하여 임의의 정점부터 인접한 정점 거리 기준으로 정렬
   1. 기준 정점 넣음
   2. 기준에서 갈 수 있는 정점 + 방문 아직 안한 정점들 우선순위 큐에 넣음 : 최소 정점 거리로 자동 정렬됨
   3. 다 방문하면 탈출
2. 최소 거리 정점 꺼내서 다시 인접한 정점 넣고 정렬

• 시간 복잡도
  • $O(V^{2})$
  • 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph) 에 적합