[파이썬으로 배우는 알고리즘] 프림(Prim) 알고리즘

프림(Prim) 알고리즘

2022.07.28 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 최소 신장 트리(MST)

[파이썬으로 배우는 알고리즘] 최소 신장 트리(MST)

 

만약 최소 신장 트리의 개념과 프림 알고리즘의 개념을 잘 모르신다면 위의 포스팅한 글을 보고 간단한 개념을 알고 오시는 게 좋을 것 같습니다!

 

프림 알고리즘은 크루스칼 알고리즘과 더불어 그리디 알고리즘을 기반으로 최소 신장 트리를 구하는 대표적인 알고리즘입니다. 오늘은 프림 알고리즘을 사용해서 최소 신장 트리를 구하는 세세한 과정과 코드까지 구현해보는 시간을 갖도록 하겠습니다. 

 

---

프림 알고리즘의 동작 방식

 

1) 그래프에 속하지 않은 연결된 노드들 중 간선의 가중치가 작은 순으로 노드를 그래프에 포함시켜야 하기 때문에 그래프와 연결된 노드들을 간선의 가중치를 우선순위로 저장하는 우선순위 큐를 가지고 프림 알고리즘을 적용합니다. 또한 이미 그래프에 속한 노드에는 적용시키지 않기 위해서 connected 테이블로 포함된 노드인지 확인합니다.

2022.07.19 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap)

[파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap)

 

 

2) 노드 1을 시작 노드로 하여 우선순위 큐에 삽입합니다. 시작 노드이기 때문에 간선 가중치는 0이 됩니다.

 

3) 노드 1을 우선순위 큐에서 빼주면서 그래프에 포함시킵니다. 노드 1과 연결되어 있으면서 그래프에 포함되지 않은 노드들을 우선순위 큐에 삽입합니다. 노드 2, 3, 4 

 

4) 노드 2를 우선순위 큐에서 빼주면서 그래프에 포함시킵니다. 노드 2와 연결되어 있으면서 그래프에 포함되지 않은 노드들을 우선순위 큐에 삽입합니다. 노드 4, 5

 

5) 노드 4를 우선순위 큐에서 빼주면서 그래프에 포함시킵니다. 노드 4와 연결되어 있으면서 그래프에 포함되지 않은 노드들을 우선순위 큐에 삽입합니다. 노드 3, 5

 

6) 우선순위 큐에서 제일 먼저 처리해야 하는 노드 4는 이미 그래프에 포함되어 있기 때문에 아무 작업도 하지 않고 우선순위 큐에서 삭제합니다.

 

7) 노드 3을 우선순위 큐에서 빼주면서 그래프에 포함시킵니다. 노드 3과 연결되어 있으면서 그래프에 포함되지 않은 노드들을 우선순위 큐에 삽입합니다. 노드 5

 

8) 노드 5를 우선순위 큐에서 빼주면서 그래프에 포함시킵니다. 노드 5와 연결되어 있으면서 그래프에 포함되어 있지 않은 노드는 없습니다.

 

9) 우선순위 큐가 비게 되므로 종료합니다.

 

---

프림 알고리즘 구현

코드

import heapq as hq

def prim(start):
    heap = list()
    # 연결되어 있는지 확인하는 리스트
    connected = [False] * (NODE_CNT + 1)
    
    sum_w = 0
    
    hq.heappush(heap, (0, start))
    sum_w = 0
    
    print('#####################')
    print('Minimum Spanning Tree')
    
    # 우선순위 큐에 데이터가 있는 동안
    while heap:
        weight, v = hq.heappop(heap)
        # 뺀 노드가 그래프에 포함되어 있지 않은 경우
        if not connected[v]:
            # 그래프에 포함 처리
            connected[v] = True
            sum_w += weight
            print('Connected Nodes:', v, 'Weight:', weight)
            for i in range(1, NODE_CNT + 1):
                if graph[v][i] != 0 and not connected[i]:
                    hq.heappush(heap, (graph[v][i], i))
                    
    print('Sum of weight:', sum_w)
    print('#####################')
    
if __name__ == "__main__":
    NODE_CNT = 5
    graph = [[0] * (NODE_CNT + 1) for _ in range(NODE_CNT + 1)]
    root = list(range(NODE_CNT + 1))
    graph[1][2], graph[1][3], graph[1][4] = 1, 8, 3
    graph[2][1], graph[2][4], graph[2][5] = 1, 2, 7
    graph[3][1], graph[3][4], graph[3][5] = 8, 4, 5
    graph[4][1], graph[4][2], graph[4][3], graph[4][5] = 3, 2, 4, 6
    graph[5][2], graph[5][3], graph[5][4] = 7, 5, 6
                
    prim(1)

결과

프림 알고리즘의 시간 복잡도 = O(E log V) (E는 간선의 개수, V는 노드의 개수)

인접 행렬로 구성된 그래프에서 모든 간선에 대해 우선순위 큐 삽입 연산을 적용하기 때문! (O(2E), O(log V))

 

2022.07.29 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 크루스칼(Kruskal) 알고리즘

[파이썬으로 배우는 알고리즘] 크루스칼(Kruskal) 알고리즘