17. 프림 알고리즘

출처: https://tinyurl.com/y6l73u5t 

---

프림 알고리즘

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법

Prim 알고리즘의 동작

시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다.
앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
가장 낮은 가중치를 먼저 선택한다.
위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복한다.

https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html

---

프림 알고리즘 동작 과정

출처: https://gmlwjd9405.github.io/images/algorithm-mst/prim-example.png

---

프림 알고리즘 파이썬 코드

import numpy as np
class Prim:
    def __init__(self):
        self.matrix = makeGraph()
        self.matrixLen = len(self.matrix[0])
        self.connected_Weight = np.zeros((self.matrixLen, self.matrixLen))
        self.visited_Vertex = np.zeros(self.matrixLen)
        self.connected_len = 0
        self.totalWeight = 0

    def cycleCheck(self, input_i, input_j):
        chk = False
        arr = []
        visited = np.zeros(self.matrixLen)
        arr.append(input_i)
        visited[input_i] = 1
        while (len(arr)):
            temp = arr.pop()
            if (chk == True):
                return chk
            for i in range(len(self.matrix[0])):
                if ( (self.connected_Weight[temp][i] == 1 or self.connected_Weight[temp][i] == 2) and visited[i] != 1 and temp != i ):
                    if (input_j == i):
                        chk = True
                        return chk
                    else:
                        arr.append(i)
                        visited[i] = 1
                    temp = i
        return chk

    def findLowerValue(self):
        lowest =100
        low_i ,low_j =0, 0
        for i in range(len(self.matrix[0])):
            if ( self.visited_Vertex[i] == 1):
                for j in range(len(self.matrix[0])):
                    if( i != j):
                        chk = self.cycleCheck(i, j)
                        if( chk):
                            self.connected_Weight[i][j] = 2
                            self.connected_Weight[j][i] = 2
                        elif(chk == False and self.matrix[i][j] != 0 and  self.connected_Weight[i][j] != 1  and self.connected_Weight[i][j] != 2):
                            if(self.matrix[i][j] <= lowest):
                                lowest,low_i, low_j = self.matrix[i][j], i,j

        return int(lowest),low_i,low_j

    def Prim(self):
        index = 0
        self.visited_Vertex[index] = 1
        while (self.connected_len < self.matrixLen-1):
            lowest, i, j = self.findLowerValue()
            self.visited_Vertex[i] = 1
            self.visited_Vertex[j] = 1
            self.connected_Weight[i][j] = 1
            self.connected_Weight[j][i] = 1
            self.connected_len += 1
            self.totalWeight += lowest
            print("(", i, ",", j, ")-> weight: ", lowest, "total Weight :", self.totalWeight)


def makeGraph():
    matrix = np.zeros((9, 9))
    matrix[0][1] = 4
    matrix[0][7] = 8  # 0 - degree 2
    matrix[1][0] = 4
    matrix[1][2] = 8
    matrix[1][7] = 11  # 1 - degree 3
    matrix[2][1] = 8
    matrix[2][3] = 7
    matrix[2][8] = 2
    matrix[2][5] = 4  # 2 - degree 4
    matrix[3][2] = 7
    matrix[3][4] = 9
    matrix[3][5] = 14  # 3 - degree 3
    matrix[4][3] = 9
    matrix[4][5] = 10  # 4 - degree 2
    matrix[5][2] = 4
    matrix[5][3] = 14
    matrix[5][4] = 10
    matrix[5][6] = 2  # 5 - degree 4
    matrix[6][5] = 2
    matrix[6][7] = 1
    matrix[6][8] = 6  # 6 - degree 3
    matrix[7][0] = 8
    matrix[7][1] = 11
    matrix[7][6] = 1
    matrix[7][8] = 7  # 7 - degree 4
    matrix[8][2] = 2
    matrix[8][6] = 6
    matrix[8][7] = 7  # 8 - degree 3
    return matrix


def main():
    print('main')
    Prim().Prim()


if __name__ == "__main__":
    main()

#prim python code

결과

과정 + 결과

---

프림 알고리즘 시간 복잡도

Prim 알고리즘의 시간 복잡도는 최소 우선순위 큐를 어떻게 구현하느냐에 따라 다르다.

대표적으로 binary heap , unsorted array으로 구현할 수 있으며

binary heap은 이고, unsorted array는 이다.

---

Prim 알고리즘은 최소 우선순위 큐에서 key 값이 작은 정점을 추출(extract -min) 한 후

그 정점의 인접한 간선의 가중치와 연결된 정점의 key 값을 비교해서

연결된 정점의 key 값을 갱신할지 말지를 결정(Decrease - key)하는 것을 통해 MST를 구현

https://victorydntmd.tistory.com/102