최소 신장 트리 (가중 그래프)

이 주제는 여기에서 튜토리얼로 제공된다.

최소 신장 트리 (MST)는 연결된 무방향 가중 그래프에서 모든 정점을 연결하는 간선의 부분 집합이다. 이때 사이클이 없어야 하며, 전체 간선의 가중치 합이 최소가 되어야 한다. 하나의 그래프에 대해 여러 개의 MST가 존재할 수 있다.

그래프의 MST를 계산하는 데는 두 가지 유명한 알고리즘이 있다: 크루스칼 알고리즘과 프림 알고리즘. 두 알고리즘 모두 O(ElogE)의 시간 복잡도를 가지며, 여기서 E는 원본 그래프의 간선 수를 의미한다.

크루스칼 알고리즘

간선을 가중치를 기준으로 정렬한다. 매번 가장 작은 간선을 탐욕적으로 선택하고, 사이클을 형성하지 않는 한 최소 신장 트리(MST)에 추가한다. 크루스칼 알고리즘은 Union Find 데이터 구조를 사용해 추가된 간선이 사이클을 발생시키는지 확인한다. 연결된 모든 정점을 동일한 집합에 넣는 것이 핵심이다. 새로운 간선의 두 정점이 동일한 집합에 속하지 않으면 해당 간선을 MST에 안전하게 추가할 수 있다.

다음 그래프는 단계별 과정을 보여준다:

Graph

준비 단계

// 반환할 값과 Union Find 데이터 구조를 초기화한다.
var cost: Int = 0
var tree = Graph<T>()
var unionFind = UnionFind<T>()
for vertex in graph.vertices {

// 처음에는 모든 정점이 연결되지 않았다.
// 각 정점은 자신만의 개별 집합에 속한다.
  unionFind.addSetWith(vertex)
}

간선 정렬

let sortedEdgeListByWeight = graph.edgeList.sorted(by: { $0.weight < $1.weight })

한 번에 하나의 간선을 가져와 MST에 삽입을 시도한다.

for edge in sortedEdgeListByWeight {
  let v1 = edge.vertex1
  let v2 = edge.vertex2 
  
  // 동일한 집합에 속한다면, 이 간선의 두 정점은 이미 MST에서 연결되었다.
  // 이 간선을 추가하면 사이클이 발생한다.
  if !unionFind.inSameSet(v1, and: v2) {
    // 간선을 MST에 추가하고 최종 비용을 업데이트한다.
    cost += edge.weight
    tree.addEdge(edge)
    
    // 두 정점을 동일한 집합에 넣는다.
    unionFind.unionSetsContaining(v1, and: v2)
  }
}

프림 알고리즘

프림 알고리즘은 모든 간선을 미리 정렬하지 않는다. 대신 우선순위 큐를 사용해 다음으로 가능한 정점을 지속적으로 정렬된 상태로 유지한다. 하나의 정점에서 시작해 방문하지 않은 모든 이웃을 순회하며, 각 이웃에 대해 정점과 현재 정점을 연결하는 간선의 가중치 쌍을 큐에 추가한다. 매번 우선순위 큐의 최상단(가장 작은 가중치를 가진 것)을 탐욕적으로 선택하고, 큐에 추가된 이웃이 아직 방문되지 않았다면 최종 MST에 해당 간선을 추가한다.

다음 그래프는 단계를 보여준다:

Graph

준비

// 반환할 값과 우선순위 큐 데이터 구조를 초기화한다.
var cost: Int = 0
var tree = Graph<T>()
var visited = Set<T>()

// (이웃 정점, 가중치) 쌍 외에, 나중에 MST를 출력하기 위해 부모를 추가한다.
// 부모는 기본적으로 현재 정점이다. 즉, 이웃 정점이 방문되기 전의 이전 정점이다.
var priorityQueue = PriorityQueue<(vertex: T, weight: Int, parent: T?)>(sort: { $0.weight < $1.weight })

어떤 정점에서 시작

priorityQueue.enqueue((vertex: graph.vertices.first!, weight: 0, parent: nil))
// 우선순위 큐의 최상단에서 가져오면 가장 작은 가중치의 간선을 얻을 수 있다.
while let head = priorityQueue.dequeue() {
  let vertex = head.vertex
  if visited.contains(vertex) {
    continue
  }

  // 정점이 이전에 방문되지 않았다면, 해당 간선(부모-정점)이 MST에 선택된다.
  visited.insert(vertex)
  cost += head.weight
  if let prev = head.parent { // 첫 번째 정점은 부모가 없다.
    tree.addEdge(vertex1: prev, vertex2: vertex, weight: head.weight)
  }

  // 방문하지 않은 모든 이웃을 우선순위 큐에 추가한다.
  if let neighbours = graph.adjList[vertex] {
    for neighbour in neighbours {
      let nextVertex = neighbour.vertex
      if !visited.contains(nextVertex) {
        priorityQueue.enqueue((vertex: nextVertex, weight: neighbour.weight, parent: vertex))
      }
    }
  }
}