[kotlin] 코틀린으로 크루스칼 알고리즘 구현하기

14 Dec 2023

kotlin

크루스칼 알고리즘은 그래프 이론에서 최소 비용으로 모든 정점을 연결하는 최소 비용 신장 트리(Minimum Spanning Tree, MST)를 찾는 알고리즘이다.

크루스칼 알고리즘 개요

크루스칼 알고리즘은 최소 신장 트리를 찾는 알고리즘 중 하나로, 간선을 정렬한 뒤에 최소 비용의 간선부터 순서대로 선택하여 사이클을 형성하지 않는 최소 신장 트리를 만든다.

코틀린으로 크루스칼 알고리즘 구현하기

다음은 코틀린으로 크루스칼 알고리즘을 구현한 예제이다.

data class Edge(val src: Int, val dest: Int, val weight: Int)

class KruskalAlgorithm(private val vertices: Int, private val edges: List<Edge>) {
    private val parent = IntArray(vertices) { it }

    private fun find(v: Int): Int {
        var vertex = v
        while (parent[vertex] != vertex) {
            vertex = parent[vertex]
        }
        return vertex
    }

    private fun union(u: Int, v: Int) {
        val x = find(u)
        val y = find(v)
        parent[x] = y
    }

    fun executeKruskal(): List<Edge> {
        val result = mutableListOf<Edge>()
        val sortedEdges = edges.sortedBy { it.weight }

        var i = 0
        var e = 0
        while (e < vertices - 1) {
            val nextEdge = sortedEdges[i]
            i++
            val x = find(nextEdge.src)
            val y = find(nextEdge.dest)

            if (x != y) {
                result.add(nextEdge)
                e++
                union(x, y)
            }
        }
        return result
    }
}

fun main() {
    val vertices = 4
    val edges = listOf(
        Edge(0, 1, 10),
        Edge(0, 2, 6),
        Edge(0, 3, 5),
        Edge(1, 3, 15),
        Edge(2, 3, 4)
    )
    val kruskalAlgorithm = KruskalAlgorithm(vertices, edges)
    val minSpanningTree = kruskalAlgorithm.executeKruskal()
    for (edge in minSpanningTree) {
        println("${edge.src} - ${edge.dest}: ${edge.weight}")
    }
}

위의 예제는 4개의 정점과 5개의 간선을 가진 그래프에 크루스칼 알고리즘을 적용한 코드이다. 결과는 다음과 같다.

- 3: 4
- 3: 5
- 1: 10

이렇게 코틀린으로 간단하게 크루스칼 알고리즘을 구현할 수 있다.

마치며

코틀린을 사용하여 크루스칼 알고리즘을 구현해봤는데, 간결하고 가독성 있게 알고리즘을 구현할 수 있다는 점이 좋다. 이를 통해 그래프 이론과 최소 신장 트리 알고리즘에 대한 이해를 높일 수 있었다.

참고문헌:

https://en.wikipedia.org/wiki/Kruskal%27s_algorithm