Kotlin을 이용한 최소 신장 트리(MST) 알고리즘 구현과 이해

최소 신장 트리(Minimum Spanning Tree, MST)는 그래프의 모든 노드를 최소의 비용으로 연결하는 부분 그래프입니다. 이는 네트워크 설계, 클러스터링, 물류 및 도로 네트워크 최적화 등 다양한 분야에서 활용됩니다. MST를 찾는 대표적인 알고리즘으로는 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 있습니다. Kotlin을 사용하여 이 두 알고리즘을 구현하는 방법을 살펴보겠습니다.

크루스칼(Kruskal) 알고리즘

크루스칼 알고리즘은 그래프의 간선을 가중치에 따라 오름차순으로 정렬한 후, 사이클을 형성하지 않는 선에서 최소 가중치를 가진 간선부터 차례대로 선택하여 MST를 구성하는 방식입니다.

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

class Graph(val vertices: Int) {
    val edges = mutableListOf<Edge>()

    fun addEdge(src: Int, dest: Int, weight: Int) {
        edges.add(Edge(src, dest, weight))
    }

    fun kruskalMST() {
        edges.sortBy { it.weight }
        val parent = IntArray(vertices) { it }
        
        fun find(i: Int): Int {
            if (parent[i] != i) parent[i] = find(parent[i])
            return parent[i]
        }

        fun union(x: Int, y: Int) {
            val xroot = find(x)
            val yroot = find(y)
            parent[xroot] = yroot
        }

        val mst = mutableListOf<Edge>()
        for (edge in edges) {
            val x = find(edge.src)
            val y = find(edge.dest)
            if (x != y) {
                mst.add(edge)
                union(x, y)
            }
        }
        
        mst.forEach { println("${it.src} - ${it.dest}: ${it.weight}") }
    }
}

 

반응형

 

프림(Prim) 알고리즘

프림 알고리즘은 시작 노드에서부터 MST를 점진적으로 확장하는 방식으로, 현재 MST 집합에서 가장 가까운 노드를 선택하여 추가합니다.

fun primMST(graph: Array<IntArray>) {
    val V = graph.size
    val parent = IntArray(V) { -1 }
    val key = IntArray(V) { Int.MAX_VALUE }
    val mstSet = BooleanArray(V) { false }

    key[0] = 0

    for (count in 0 until V - 1) {
        val u = key.withIndex().filter { !mstSet[it.index] }.minByOrNull { it.value }!!.index
        mstSet[u] = true

        for (v in 0 until V) {
            if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u
                key[v] = graph[u][v]
            }
        }
    }

    for (i in 1 until V) {
        println("${parent[i]} - $i: ${graph[i][parent[i]]}")
    }
}

 

이 구현에서는 간선의 가중치를 저장하는 2차원 배열을 사용하여 그래프를 표현합니다. 프림 알고리즘은 주로 밀집 그래프(Dense Graph)에서 효율적입니다.

 

Kotlin을 활용한 크루스칼과 프림 알고리즘 구현은 그래프 이론의 중요한 개념인 최소 신장 트리를 이해하고, 실제 문제에 적용하는 데 있어 강력한 기반을 제공합니다. 각 알고리즘은 특정 상황에서 더 유리할 수 있으므로, 주어진 문제의 특성을 고려하여 적절한 알고리즘을 선택하는 것이 중요합니다. Kotlin의 간결하고 표현력 있는 문법은 알고리즘의 구현과 이해를 돕습니다.