프림 알고리즘

- MST(Minimum Spanning Tree)를 만드는 방법 중 하나입니다.
- 현재 트리를 기준으로 가장 최소인 점을 찾아나가는 방식입니다.
- 사이클을 확인할 필요가 없습니다. (현재트리를 기준으로 하기 때문에 사이클이 생기지 않습니다.)

 

---

 

프림 알고리즘은 현재까지 생성된 트리를 기준으로 가장 최소 비용의 간선을 선택해서 트리를 확장시켜 나갑니다.
현재 트리를 기준으로 한다는 말 속에는 이미 방문한 점은 방문하지 않는다는 말이 포함되어 있습니다.
때문에 자연스럽게 사이클이 생기지 않습니다 :)

과정은 간단합니다. 

1. 현재 트리를 기준으로 최소 비용으로 방문 가능한 점을 방문합니다.

2. 새로운 점을 기준으로 최소 간선의 목록을 업데이트 합니다.

직접 문제를 하나 풀어보면 쉽게 이해하실 수 있으실거에요.
같이 예를 살펴보죠 :) 

 

저희의 목적은 방문 가능한 노드들 중에서 최소 비용이 드는 길을 선택하는거에요. (방문한 노드는 다시 방문하지 않습니다.)
길을 선택했으면 방문 가능한 노드들이 더 생겨나겠죠? 이걸 기준으로 최소 비용이 드는 길을 업데이트 해줍니다.

먼저 시작 노드를 정합니다. 0부터 시작해볼게요.
그럼 1, 2 번 노드가 방문이 가능해지고 각각 5, 4가 비용이 최소 비용이 됩니다.

그럼 5, 4중에서 최소 비용인 4를 선택해야겠죠? 2번을 방문합니다.
이미 방문한 0은 제외하고 새롭게 3, 4번 노드를 방문할 수 있게 되었습니다.

이제 최소 비용은 2가 되겠네요. 1번 노드를 방문합니다.
3번 노드를 방문할 수 있는 다른 길이 생겼지만 이미 최소 비용인 6보다 크기 때문에 업데이트 하지 않습니다.

이제 감 잡으셨죠? 최소 비용인 3번 노드를 방문합니다.
4번 노드로 갈 수 있는 새로운 길이 생겼네요. 최소 비용으로 업데이트 시켜줍니다.

이제 마지막 5번 노드만 남았습니다. 새로운 길이 생겼으나 최소비용과 동일합니다. 둘 다 선택이 가능하겠네요.

마지막 길까지 선택해주면 MST가 완성됩니다.
어렵지 않죠??
차근차근 따라오시면 쉽게 이해하셨으리라 생각해요 :)

구현 

문제는 구현이죠... 워낙 유명한 이론이기 때문에 이미 다른 언어로는 많은 코드가 있으니 참고하시면 될 것 같구요.

저는 Swift로 구현해보았습니다.

최소값을 구하는 부분을 Heap을 사용한다던지, 좀 더 좋은 방법으로 구할 수 있을 것 같은데,

추후에 업데이트 해보겠습니다.

/**
 * 현재 노드에 연결되어 있는 노드만 확인할 것이기 때문에
 * 간단하게 목적지와 비용만 저장하는 Edge 를 정의합니다.
 */
struct Edge {
    var destination: Int
    var cost: Int
}

func updateDist(_ tree: [Edge], dist: inout [Int?]) -> [Edge] {
    for edge in tree {
        if let d = dist[edge.destination] {
            if d > edge.cost {
                dist[edge.destination] = edge.cost
            }
        } else {
            dist[edge.destination] = edge.cost
        }
    }
    
    return tree
}

func prim(_ n: Int, _ costs: [[Int]]) -> Int {
    
    // 최소 비용을 저장할 배열
    var dist = [Int?](repeating: nil, count: n)
    
    // 방문 체크 배열
    var visit = [Bool](repeating: false, count: n)
    
    // 방문한 노드의 개수 ( 방문 체크 배열에서 확인해도 되지만.. 그냥 간단하게 변수를 하나 만들었습니다. )
    var visitCount = 0
    
    // 현재 방문 노드를 저장합니다. 0에서 시작합니다.
    var now = 0
    
    // 최소비용을 저장한다.
    var minimumCost = 0
    /**
     * 배열의 인덱스가 해당 노드가 되고 연결된
     * 연결된 선을 저장합니다.
     */
    var tree = [[Edge]](repeating: [], count: n)
    
    /**
     * Setup Tree
     * 선의 양 끝을 둘다 저장해줘야 합니다.
     */
    for cost in costs {
        tree[cost[0]].append(Edge(destination: cost[1], cost: cost[2]))
        tree[cost[1]].append(Edge(destination: cost[0], cost: cost[2]))
    }
    
    visit[now] = true
    visitCount += 1
    
    // 탐색
    while visitCount < n {
        let tree = updateDist(tree[now], dist: &dist)
        
        // 최소값 구하기
        var minCost: Int? = nil
        for i in 0..<n {
            guard !visit[i], let d = dist[i] else {continue}
            
            if let min = minCost {
                if min > d {
                    minCost = d
                    now = i
                }
            } else {
                minCost = d
                now = i
            }
        }
        
        visit[now] = true
        visitCount += 1
        minimumCost += minCost!
    }
    
    
    return minimumCost
}


// 입력: ( Int: 노드의 개수, [[Int]]: [[출발 노드, 끝 노드, 비용]] )
// 예상결과: 23
prim(6, [[0, 1, 5], [0, 2, 4], [1, 2, 2], [1, 3, 7], [2, 3, 6], [2, 4, 11], [3, 5, 8], [3, 4, 3], [4, 5, 8]])

 

감사합니다. :)