MST:KruskalアルゴリズムとPrimアルゴリズム

チップ.
1.まずUnion Findの3つの関数を作成します.(findUnion, isUnion, union)
2.Kruskalアルゴリズムは、コストが小さいから合併がないまで追加する方法である.
したがって,ソート後は最小のものから開始すればよいが,これを便利にPriorityQueueとして含み,その後コストを基準に最小の値から抽出を開始すれば終了する.
しかし,MSTを解く際には,Kruskalを盲目的に信じることはできない.
BOJ 2887(惑星トンネル)の問題では、最大100000個の頂点がある.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.math.abs

class BOJ_행성터널 {
    lateinit var planet: Array<List<Long>>
    lateinit var root: IntArray
    fun main() {
        val br = BufferedReader(InputStreamReader(System.`in`))
        val bw = BufferedWriter(OutputStreamWriter(System.`out`))
        val n = br.readLine().toInt()
        planet = Array(n) { emptyList<Long>() }
        root = IntArray(n) { it }
        for (i in 0 until n) {
            planet[i] = br.readLine().split(" ").map { it.toLong() }
        }

        val pq = PriorityQueue<List<Long>>(compareBy { it.last() })
        for (i in planet.indices) {
            for (j in i + 1 until planet.size) {
                pq.offer(listOf(i.toLong(), j.toLong(), getDistance(i, j)))
            }
        }

        var answer = 0L
        while (pq.isNotEmpty()) {
            val (aLong, bLong, dist) = pq.poll()
            val a = aLong.toInt()
            val b = bLong.toInt()
            if (isUnion(a, b)) continue
            union(a, b)
            answer += dist
        }
        bw.write("$answer")
        br.close()
        bw.close()
    }

    fun getDistance(planetA: Int, planetB: Int): Long {
        val a = planet[planetA]
        val b = planet[planetB]
        return minOf(abs(a[0] - b[0]), abs(a[1] - b[1]), abs(a[2] - b[2]))
    }

    fun union(a: Int, b: Int) {
        val (min, max) = listOf(findUnion(a), findUnion(b)).sorted()
        root[max] = min
    }

    fun isUnion(a: Int, b: Int): Boolean {
        return findUnion(a) == findUnion(b)
    }

    fun findUnion(a: Int): Int {
        if (a == root[a]) return a
        root[a] = findUnion(root[a])
        return root[a]
    }
}

このように解くと他の問題のように簡単に通過すると思いますが、メモリが超過しています.
なぜなら、他の問題には2つの状況があるからだ.
1.定点の数が少ないため、必然的に幹線の本数も少ない
2.頂点数が多くても、一部の頂点がつながっているなど、幹線数が少ない
このような場合は、幹線の本数が小さくて通りやすいです.
しかし、これは問題ではありません.頂点が10万個なので、幹線はたっぷり(10万-1)!犬.
数十億で十分だと思います.インターネット上の工場計算機も5000しかありません.
KruskalではなくPrimアルゴリズム.でもPrimでこれを
nは10万なのでn^2=100億です.
その実用的なKruskalも解くことができますxyzを誠実に保存するのではなく、他の方法で保存します.
https://chanhuiseok.github.io/posts/baek-34/
クルーズとフリームの違いは
https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html
こちらはよく整理されています
PREAMアルゴリズムの起動方式はDAEXTRAと似ているそうです.
https://www.apexcel.blog/algorithm/graph/mst/mst/
クルーズとは異なり、フリームは各頂点の情報を必要とするため、各頂点には隣接する頂点の情報が必要である.したがって、2 D配列には、各頂点の隣接する頂点の情報が含まれます.
整理すると、

Kruskal 알고리즘時間複雑度はO(elog₂e)

Prim의 알고리즘時間複雑度はO(n^2)

グラフィック内にわずかな数字しかない「희소 그래프(Sparse Graph)」にはKruskalアルゴリズムが適している;

図表に多数の幹線が存在する「밀집 그래프(Dense Graph)」には、Primアルゴリズムが適切である.

PrimアルゴリズムはUnion Findを使う必要がないので便利です.