[자료구조] 신장 트리, 최소 비용 신장 트리

신장 트리 (Spanning Tree)

• 신장(Spanning) : 모든 노드를 포함한다는 의미
• 트리의 일종이기 때문에 cycle이 없어야 한다.
• 기존 그래프가 가진 모든 노드를 순환 없이 서로 연결시킨 트리
• 트리 간선 : 신장 트리에 포함된 간선
• 비트리 간선: 신장 트리에 포함되지 않은 간선

원본 그래프

 

신장 트리

​

 

---

최소 비용 신장 트리 (Minimum Cost Spanning Tree)

• 무향 가중 그래프의 신장 트리 중에서 가중치의 합이 최소인 신장 트리
• 최소 신장 트리 구하는 알고리즘 : Prim(프림), Kruskal(크루스칼)

1197번: 최소 스패닝 트리

 

1. 크루스칼 (Kruskal) 알고리즘

• 노드를 모두 추가한 상태에서 시작
• 시간복잡도 : O(E log E)
• 정점 수 대비 간선 수가 적은 경우에 유리
• 남아있는 간선 중 최소 비용을 가지는 간선 선택 후 사이클이 생기는지 검사

1. 모든 간선을 비용 순으로 오름차순 정렬
2. 낮은 비용의 간선을 차례대로 선택하여 신장 트리를 완성해나감 (단, 사이클을 형성하지 않는 간선들만 선택해야됨)

​

2. 프림 (Prim) 알고리즘

• 트리를 확장시켜 최소 비용 신장 트리를 만든다.
• 시간복잡도 : O(E log V)
• 정점 수 대비 간선 수가 많은 경우에 유리
• 임의의 시작 노드 1개만을 추가하여 시작
• 현재 신장 트리와 연결될 간선 중에서 가장 적은 비용을 가지는 간선 선택

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.collections.ArrayList

import kotlin.math.min

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))


val INF = Int.MAX_VALUE
var V = 0
var E = 0

var graph = ArrayList<ArrayList<Edge>>()

fun solution() {

    var strtok = StringTokenizer(br.readLine())
    V = strtok.nextToken().toInt()
    E = strtok.nextToken().toInt()

    for(i in 0..V)
        graph.add(ArrayList())

    for(i in 0 until E)
    {
        strtok = StringTokenizer(br.readLine())
        var from = strtok.nextToken().toInt()
        var to = strtok.nextToken().toInt()
        var weight = strtok.nextToken().toInt()

		//무향 그래프이므로 양쪽 다넣음
        graph.get(from).add(Edge(from, to, weight))
        graph.get(to).add(Edge(to, from, weight))
    }


    bw.write(prim().toString())
}

fun prim():Int
{
    var result = 0

	//현재 방문 가능한 edge들 보관하는 우선순위 큐 (가장 낮은 가중치의 간선부터 반환)
    var edges = PriorityQueue<Edge>({ o1, o2 -> o1.weight - o2.weight })
    var queue : Queue<Int> = LinkedList()
    
    //임의의 시작점 1
    queue.offer(1)

    var visted = BooleanArray(V+1)
    visted[1] = true

    while (!queue.isEmpty())
    {
        var now = queue.poll()

        for(e in graph[now])
        {
        	//아직 방문 안한 노드와 연결된 간선들 추가
            if(!visted[e.to])
                edges.offer(e)
        }

		//현재 방문 가능한 노드 중 가장 작은 가중치의 간선과 연결된 노드를 방문
        while(!edges.isEmpty())
        {
            var e = edges.poll()

            if(!visted[e.to])
            {
                result += e.weight
                visted[e.to] = true
                queue.offer(e.to)
                break
            }
        }
    }
    return result
}


data class Edge(var from : Int, var to : Int, var weight : Int)


fun main() {
    solution()


    br.close()
    bw.close()
}