알고리즘 - Minimum Spanning Tree

Minimum Spanning Tree

Minimum Spanning Tree 란

모든 정점을 포함하면서 순환하지 않는 트리 중 간선의 합이 가장 작은 트리를 의미합니다.

트리의 특성은 주어진 방향성이 없는 그래프입니다.

신장 트리는 모든 정점을 포함하면서 순환하지 않는 트리입니다.

Minimum Spanning Tree 활용

MST는 아래와 같은 상황에서 사용할 수 있습니다.

• 통신 네트워크를 구축할 때 케이블을 적게 사용하기 위해
• 가장 적은 간선의 가중치 만 사용해 연결해야할 때

Minimum Spanning Tree 구현 방법

• Kruskal 알고리즘
• Prim 알고리즘

Kruskal 알고리즘

Kruskal 알고리즘이란

가장 낮은 간선에서부터 시작해 서로 떨어진 정점들을 합쳐나가는 알고리즘입니다. Kruskal 알고리즘은 Union-Find 알고리즘을 활용해 효율적으로 구현할 수 있습니다

Kruskal 알고리즘 동작

1. 간선을 크기 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택한다.
2. 간선을 선택할 때, 같은 그룹의 간선이면 넘어가고 다른 그룹이면 MST에 추가한다.
3. 최소 신장 트리에 V-1개의 간선을 추가시켰다면 과정을 종료한다.

Kruskal 알고리즘 구현

public List<Node> getSMT(List<Node> nodes) {
  List<Node> answer = new ArrayList<>();

  PriorityQueue<Node> queue = new PriorityQueue<>();
	queue.addAll(nodes);

  while (answer.size() < {EDGE_SIZE} - 1) {
    Node pollNode = queue.poll();
    if (!containsEdge(pollNode, answer)) {
      answer.add(pollNode);
    }
  }

	return answer;
}

private boolean isSameGroup(Node node, List<Node> nodes) {
	// node.start와 node.end가 같은 그룹인지 확인
  return false;
}

private static class Node implements Comparable<Node>{
  int start;
  int end;
  int vertex;

  public Node(int start, int end, int vertex) {
    this.start = start;
    this.end = end;
    this.vertex = vertex;
  }

  @Override
  public int compareTo(Node o) {
    return this.vertex - o.vertex;
  }
}

Union-Find

Union-Find 란

서로소 집합을 그래프로 표현하는 알고리즘입니다.

Union-Find 활용

두 개의 원소가 같은 집합에 속하는 지 파악할 수 있습니다. 크루스칼 알고리즘에서 같은 그룹에 존재하는지

Union-Find 기능

• 연결
  1. 두 원소 중 큰 원소의 값을 작은 원소의 키로 변경합니다.
  2. 입력한 원소를 루트 노드의 키로 변경합니다.
• 찾기 - 두 원소의 루트 노드가 같은지 비교합니다.

Union-Find 구현

public class UnionFind {

  public int getParent(int[] arr, int a) {
    if (arr[a] == a) {
      return a;
    }
    arr[a] = getParent(arr, arr[a]);
    return arr[a];
  }

  public void unionParent(int[] arr, int a, int b) {
    int parentA = getParent(arr, a);
    int parentB = getParent(arr, b);
		// 1. 두 원소 중 큰 원소의 값을 작은 원소의 키로 변경합니다.
    if (parentA > parentB) {
			// 2. 입력한 원소를 루트 노드의 키로 변경합니다.      
			arr[parentB] = parentA;
    } else {
			// 2. 입력한 원소를 루트 노드의 키로 변경합니다.      
			arr[parentA] = parentB;
    }
  }

  public boolean findParent(int[] arr, int a, int b) {
    return getParent(arr, a) == getParent(arr, b);
  }
}

Kruskal with Union Find

public void getSMT(List<Node> nodes) {
  List<Node> answer = new ArrayList<>();
  UnionFind unionFind = new UnionFind(LENGTH);

  PriorityQueue<Node> queue = new PriorityQueue<>();
	queue.addAll(nodes);

  while (answer.size() < LENGTH - 1) {
    Node pollNode = queue.poll();
    if (!unionFind.findParent(pollNode.start, pollNode.end)) {
      answer.add(pollNode);
      unionFind.unionParent(pollNode.start, pollNode.end);
    }
  }

  System.out.println(answer);
}

private static class UnionFind {

  private final int[] arr;

  public UnionFind(int length) {
    arr = new int[length + 1];
    for (int i = 1; i <= length; i++) {
      arr[i] = i;
    }
  }

  public int getParent(int a) {
    if (arr[a] == a) {
      return a;
    }
    arr[a] = getParent(arr[a]);
    return arr[a];
  }

  public void unionParent(int a, int b) {
    int parentA = getParent(a);
    int parentB = getParent(b);
    if (parentA < parentB) {
      arr[parentB] = parentA;
    } else {
      arr[parentA] = parentB;
    }
  }

  public boolean findParent(int a, int b) {
    return getParent(a) == getParent(b);
  }
}

Prim

Prim 이란

프림 알고리즘은 한 정점에서 시작해 확장해 나가는 알고리즘이며, 우선 순위 큐를 활용해 쉽게 구현 할 수 있습니다. Union-Find를 사용하지 않은 Kruskal 알고리즘보다 효율적입니다.

보통 Prim 알고리즘을 사용할 때는 간선들의 합만 구할 때 간편하게 구현할 수 있습니다.

Prim 동작

1. 임의의 정점을 선택해 MST에 추가
2. MST에 포함된 정점에서 MST에 포함되지 않은 정점을 연결하는 간선 중 비용이 가장 작은 것을 MST에 추가
3. MST에 V-1개의 간선이 추가될 때까지 2 번 과정 반복

Prim 구현

public static int getTotalSum(int[][] tree) {
  int length = tree.length;
  int totalSum = 0;
  int index = 0;

  Queue<Node> queue = new PriorityQueue<>();
  boolean[] visited = new boolean[length];
  addNode(tree, length, queue, visited, index);
  int count = 1;

  while (count < length) {
    Node node = queue.poll();
    if (visited[node.edge]) {
      continue;
    }
    count += 1
    totalSum += node.vertex;
    addNode(tree, length, queue, visited, node.edge);
  }

  return totalSum;
}

private static class Node implements Comparable<Node> {

  int edge;
  int vertex;

  public Node(int edge, int vertex) {
    this.edge = edge;
    this.vertex = vertex;
  }

  @Override
  public int compareTo(Node o) {
    return this.vertex - o.vertex;
  }
}

문제 정리

BOJ

• 1197 - 최소 스패닝 트리 ☑️
• 1368 - 물대기 ☑️
• 1944 - 복제 로봇
• 1185 - 유럽 여행

프로그래머스

• Lv3 - 섬 연결하기

LeetCode

• 1584 - Min Cost to Connect All Points
• 1489 - Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree