[kotlin] 프림(Prim) 알고리즘에서 사용하는 자료 구조

08 Dec 2023

kotlin

프림(Prim) 알고리즘은 그래프의 최소 신장 트리를 찾는 알고리즘으로, 그래프에서 간선의 가중치 합이 최소가 되는 트리를 찾습니다. 이 알고리즘을 구현하기 위해 다양한 자료 구조가 사용됩니다.

우선순위 큐

프림 알고리즘에서 가장 중요한 자료 구조는 우선순위 큐입니다. 우선순위 큐는 각 정점의 키 값을 저장하고, 이 중 가장 작은 키 값을 가진 정점을 빠르게 찾을 수 있습니다. 프림 알고리즘에서는 각 정점의 키 값과 현재 트리에 속한 정점들과의 연결 상태를 우선순위 큐에 저장합니다.

import java.util.*

fun prim(graph: Array<IntArray>) {
    val n = graph.size
    val key = IntArray(n) { Int.MAX_VALUE }
    val mstSet = BooleanArray(n)
    val parent = IntArray(n)

    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
    key[0] = 0
    pq.add(0 to 0)

    while (pq.isNotEmpty()) {
        val u = pq.poll().second
        mstSet[u] = true

        for (v in graph.indices) {
            if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                key[v] = graph[u][v]
                parent[v] = u
                pq.add(key[v] to v)
            }
        }
    }

    // 최소 신장 트리 출력
    for (i in 1 until n) {
        println("${parent[i]} - $i : ${graph[i][parent[i]]}")
    }
}

위 코드에서 pq는 우선순위 큐로, 각 정점의 키 값과 정점 번호의 쌍을 저장합니다. 또한 key 배열은 현재 트리와 연결된 간선의 가중치를 저장합니다.

결론

프림 알고리즘은 우선순위 큐와 배열을 이용해 간단하게 구현할 수 있습니다.

프림 알고리즘에 대한 자세한 내용은 “Introduction to Algorithms” 책을 참고하시기 바랍니다.