TIL. 127 프림 알고리즘

프림 알고리즘

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

Prim 알고리즘의 동작

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

프림 알고리즘 동작 과정

프림 알고리즘 파이썬 코드

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://blog.tomclansys.com/66?category=1066976 [톰 클란시의 IT 블로그:티스토리]