[Swift 알고리즘]MST-Eager-Prim (array version)

MST를 구현하는 알고리즘 중 하나인 Prim 알고리즘이다. Prim을 공부하면서 알게된 것은 다익스트라 알고리즘과 굉장히 비슷하다는 것이다. 또한 Prim 알고리즘은 greedy 알고리즘으로 구현했다는 느낌이다. 하지만 약간 계속 정점을 늘려가면서 연결되어있는 최소 cost를 찾는다는 점이 다익스트라와 비슷하다.

간단한 idea

현재 선택된 vertex와 연결된 정점 중에 edge의 weight가 가장 작은 vertex를 찾는 것이다. 최소신장 트리는 edge의 갯수가 정점의 갯수 -1(V-1)때까지 반복하는 것이다. 최소값을 찾아올 때, 선형탐색으로 가장 작은 값을 찾아올 수도 있지만, Priority queue를 사용해서 가져오는 경우도 존재한다. 모든 신장트리는 cycle이 생기면 안된다. kruskal 알고리즘은 unionfind라는 자료구조를 사용해서 cycle 판별을 하지만, prim 알고리즘은 방문한 정점은 더이상 신경쓰지 않기 때문에, 자연스럽게 cycle은 발생하지 않는다. 

dist[]라는 distance 배열 두고, 시작한다. 처음에 dist[]은 다 INF(무한대)로 고정해놓는다. 그리고 prim 알고리즘을 시작한다. prim 알고리즘은 연결되어있는 vertex 중 weight가 최소인 vertex를 찾아간다. 현재 내가 고른 vertex를 node라고 할때, 노드의 인접된 모든 vertex와 그를 연결하는 edge의 weight을 조사한다. 이때, 현재까지 갱신한 dist속의 값보다 작은 weight을 찾는다면 dist를 갱신해준다.

위와 같이 이미 한번 골랐던 정점 index는 더이상 갱신되지 않는다. 또한 처음에 10 즉 5번vertex를 골랐다면, 인접행렬[5][i]와 dist를 비교하면서 작은값을 갱신한다. 갱신 후 가장 작은 값을 찾는다면, 27 즉 4번 vertex를 고른 것이다. 이제는 인접행렬[4][i]와 dist[i]를 비교한다. 이렇게 이어가면서, dist가 V-1번 갱신한다면 MST를 찾은 것이다.

array based Prim 알고리즘 시간복잡도 - O(V^2)

프림 알고리즘은 정점을 기준으로 for loop를 돌기 때문에, 정점의 숫자가 edge숫자보다 적은 dense graph일때 더 유용하다. 최소 정점을 찾기 위해서 선형탐색을 한번 시도한다. O(V), 이를 통해 발견한 최소 정점을 통해서 최소정점과 연결된 정점들 중에, 가장 작은 것을 찾는다. 이 역시 O(V)이다. 이 2가지 행위를 모든 정점에서 시도하기 때문에, 결국 O(V^2)이다.

코드

var INF = 999
var adjMat : [[Int]] = [[0, 29, INF, INF, INF, 10, INF],
                         [29, 0, 16, INF, INF, INF, 15],
                         [INF, 16, 0, 12, INF, INF, INF],
                         [INF, INF, 12, 0, 22, INF, 18],
                         [INF, INF, INF, 22, 0, 27, 25],
                         [10, INF, INF, INF, 27, 0, INF],
                         [INF, 15, INF, 18, 25, INF, 0]]

var nodeNum = adjMat.count
var visited = [Bool](repeating: false, count: nodeNum)
var distance = [Int](repeating: INF, count: nodeNum)

func getSmallIndex(_ number: Int) -> Int {
    var min = INF
    var index = 0
    for i in 0..<number {
        if(distance[i] < min && !visited[i]){
            min = distance[i]
            index = i
        }
    }
    return index
}

func prim(_ start: Int, _ nodeNUm: Int){
    distance[start] = 0
    for i in 0..<nodeNum {
        var node = getSmallIndex(nodeNum)
        visited[node] = true
        for j in 0..<nodeNum{
            if adjMat[node][j] != INF{
                if !visited[j] && (adjMat[node][j] < distance[j]) {
                    distance[j] = adjMat[node][j]
                }
            }
        }
    }
}
prim(0,7)
print("distance ", distance)
print("ㄱㅓ리: ", distance.reduce(0,+))