프림

■ 프림 알고리즘

1) 정의 :

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

> 앞단계에서 만들어진 MST(Minimum spanning tree)의 인접 정점 중, 최소 간선으로 연결된 정점을 선택하여

   트리를 확장(낮은 가중치 선택)

> 트리가 V-1의 간선을 가질 때 까지 반복

> 시간복잡도 : O(V^2), 적은 노드 V 일 때 유리

 

2) 사용 그래프 구조 :

> 인접행렬 ( 노드에 시간복잡도가 비례하므로! )

 

 

■ 알고리즘

다음과 같은 과정 거침

def get_min_node(node_num, visited, distances):
	# 임의의 미방문 노드 설정
    for i in range(node_num):
        if not visited[i]:
            v = i
            break
    for i in range(node_num):
        if not visited[i] and distances[i] < distances[v]:
            v = i # 가장 작은 distance를 가진 v값을 찾아줌

    return v


def prim(start, graph):
    # 사용 변수
    node_num = len(graph) # 그래프 노드 개수
    distances = [float('inf')] * node_num
    visited = [False] * node_num

    # 시작노드의 distance 값을 0
    distances[start] = 0
    
    # for loop 2번
    for _ in range(node_num): # 정점 개수만큼 반복
        node = get_min_node(node_num, visited, distances)
        visited[node] = True    # node 를 방문했다 표시

        for j in range(node_num):
            if graph[node][j] != float('inf'): #선택 노드 기준으로 간선이 존재한다면
                if not visited[j] and graph[node][j] < distances[j]:
                    distances[j] = graph[node][j]
    
    return distances

 

 

■ 분석

def get_min_node(node_num, visited, distances):
	# 임의의 미방문 노드 설정
    for i in range(node_num):
        if not visited[i]:
            v = i
            print(f'arbitary seleced v : {v}')
            break
    for i in range(node_num):
        if not visited[i] and distances[i] < distances[v]:
            v = i # 가장 작은 distance를 가진 v값을 찾아줌
    print(f'final v : {v}')
    return v


def prim(start, graph):
    # 사용 변수
    node_num = len(graph) # 그래프 노드 개수
    distances = [float('inf')] * node_num
    visited = [False] * node_num

    # 시작노드의 distance 값을 0
    distances[start] = 0
    
    # for loop 2번
    for _ in range(node_num): # 정점 개수만큼 반복
        node = get_min_node(node_num, visited, distances)
        visited[node] = True    # node 를 방문했다 표시
        
        print(f'node selected : {node}')
        print(f'visited 상태 : {visited}')
        print(f'distances before update : {distances}')
        for j in range(node_num):
            print(f'sweeping curr node : {j}')
            if graph[node][j] != float('inf'): #선택 노드 기준으로 간선이 존재한다면
                if not visited[j] and graph[node][j] < distances[j]:
                    print(f'graph[node][j] : {graph[node][j]}, distances[j] : {distances[j]}')
                    distances[j] = graph[node][j]
                else:
                    print(f'already visited! OR distance already less than comparison!')
            else:
                print(f'no edge, skip!')
        print(f'distances after update : {distances}')
        print(f'\n'*2)
        
    return distances

INF = float('inf')
adj_mat = [[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]]
           
           
           
print(f'result distance : {prim(0, adj_mat)}')
print(f'result distance sum : {sum(prim(0, adj_mat))}')
>>>
arbitary seleced v : 0
final v : 0
node selected : 0
visited 상태 : [True, False, False, False, False, False, False]
distances before update : [0, inf, inf, inf, inf, inf, inf]
sweeping curr node : 0
already visited! OR distance already less than comparison!
sweeping curr node : 1
graph[node][j] : 29, distances[j] : inf
sweeping curr node : 2
no edge, skip!
sweeping curr node : 3
no edge, skip!
sweeping curr node : 4
no edge, skip!
sweeping curr node : 5
graph[node][j] : 10, distances[j] : inf
sweeping curr node : 6
no edge, skip!
distances after update : [0, 29, inf, inf, inf, 10, inf]



arbitary seleced v : 1
final v : 5
node selected : 5
visited 상태 : [True, False, False, False, False, True, False]
distances before update : [0, 29, inf, inf, inf, 10, inf]
sweeping curr node : 0
already visited! OR distance already less than comparison!
sweeping curr node : 1
no edge, skip!
sweeping curr node : 2
no edge, skip!
sweeping curr node : 3
no edge, skip!
sweeping curr node : 4
graph[node][j] : 27, distances[j] : inf
sweeping curr node : 5
already visited! OR distance already less than comparison!
sweeping curr node : 6
no edge, skip!
distances after update : [0, 29, inf, inf, 27, 10, inf]



arbitary seleced v : 1
final v : 4
node selected : 4
visited 상태 : [True, False, False, False, True, True, False]
distances before update : [0, 29, inf, inf, 27, 10, inf]
sweeping curr node : 0
no edge, skip!
sweeping curr node : 1
no edge, skip!
sweeping curr node : 2
no edge, skip!
sweeping curr node : 3
graph[node][j] : 22, distances[j] : inf
sweeping curr node : 4
already visited! OR distance already less than comparison!
sweeping curr node : 5
already visited! OR distance already less than comparison!
sweeping curr node : 6
graph[node][j] : 25, distances[j] : inf
distances after update : [0, 29, inf, 22, 27, 10, 25]



arbitary seleced v : 1
final v : 3
node selected : 3
visited 상태 : [True, False, False, True, True, True, False]
distances before update : [0, 29, inf, 22, 27, 10, 25]
sweeping curr node : 0
no edge, skip!
sweeping curr node : 1
no edge, skip!
sweeping curr node : 2
graph[node][j] : 12, distances[j] : inf
sweeping curr node : 3
already visited! OR distance already less than comparison!
sweeping curr node : 4
already visited! OR distance already less than comparison!
sweeping curr node : 5
no edge, skip!
sweeping curr node : 6
graph[node][j] : 18, distances[j] : 25
distances after update : [0, 29, 12, 22, 27, 10, 18]



arbitary seleced v : 1
final v : 2
node selected : 2
visited 상태 : [True, False, True, True, True, True, False]
distances before update : [0, 29, 12, 22, 27, 10, 18]
sweeping curr node : 0
no edge, skip!
sweeping curr node : 1
graph[node][j] : 16, distances[j] : 29
sweeping curr node : 2
already visited! OR distance already less than comparison!
sweeping curr node : 3
already visited! OR distance already less than comparison!
sweeping curr node : 4
no edge, skip!
sweeping curr node : 5
no edge, skip!
sweeping curr node : 6
no edge, skip!
distances after update : [0, 16, 12, 22, 27, 10, 18]



arbitary seleced v : 1
final v : 1
node selected : 1
visited 상태 : [True, True, True, True, True, True, False]
distances before update : [0, 16, 12, 22, 27, 10, 18]
sweeping curr node : 0
already visited! OR distance already less than comparison!
sweeping curr node : 1
already visited! OR distance already less than comparison!
sweeping curr node : 2
already visited! OR distance already less than comparison!
sweeping curr node : 3
no edge, skip!
sweeping curr node : 4
no edge, skip!
sweeping curr node : 5
no edge, skip!
sweeping curr node : 6
graph[node][j] : 15, distances[j] : 18
distances after update : [0, 16, 12, 22, 27, 10, 15]



arbitary seleced v : 6
final v : 6
node selected : 6
visited 상태 : [True, True, True, True, True, True, True]
distances before update : [0, 16, 12, 22, 27, 10, 15]
sweeping curr node : 0
no edge, skip!
sweeping curr node : 1
already visited! OR distance already less than comparison!
sweeping curr node : 2
no edge, skip!
sweeping curr node : 3
already visited! OR distance already less than comparison!
sweeping curr node : 4
already visited! OR distance already less than comparison!
sweeping curr node : 5
no edge, skip!
sweeping curr node : 6
already visited! OR distance already less than comparison!
distances after update : [0, 16, 12, 22, 27, 10, 15]



result distance : [0, 16, 12, 22, 27, 10, 15]
arbitary seleced v : 0
final v : 0
node selected : 0
visited 상태 : [True, False, False, False, False, False, False]
distances before update : [0, inf, inf, inf, inf, inf, inf]
sweeping curr node : 0
already visited! OR distance already less than comparison!
sweeping curr node : 1
graph[node][j] : 29, distances[j] : inf
sweeping curr node : 2
no edge, skip!
sweeping curr node : 3
no edge, skip!
sweeping curr node : 4
no edge, skip!
sweeping curr node : 5
graph[node][j] : 10, distances[j] : inf
sweeping curr node : 6
no edge, skip!
distances after update : [0, 29, inf, inf, inf, 10, inf]



arbitary seleced v : 1
final v : 5
node selected : 5
visited 상태 : [True, False, False, False, False, True, False]
distances before update : [0, 29, inf, inf, inf, 10, inf]
sweeping curr node : 0
already visited! OR distance already less than comparison!
sweeping curr node : 1
no edge, skip!
sweeping curr node : 2
no edge, skip!
sweeping curr node : 3
no edge, skip!
sweeping curr node : 4
graph[node][j] : 27, distances[j] : inf
sweeping curr node : 5
already visited! OR distance already less than comparison!
sweeping curr node : 6
no edge, skip!
distances after update : [0, 29, inf, inf, 27, 10, inf]



arbitary seleced v : 1
final v : 4
node selected : 4
visited 상태 : [True, False, False, False, True, True, False]
distances before update : [0, 29, inf, inf, 27, 10, inf]
sweeping curr node : 0
no edge, skip!
sweeping curr node : 1
no edge, skip!
sweeping curr node : 2
no edge, skip!
sweeping curr node : 3
graph[node][j] : 22, distances[j] : inf
sweeping curr node : 4
already visited! OR distance already less than comparison!
sweeping curr node : 5
already visited! OR distance already less than comparison!
sweeping curr node : 6
graph[node][j] : 25, distances[j] : inf
distances after update : [0, 29, inf, 22, 27, 10, 25]



arbitary seleced v : 1
final v : 3
node selected : 3
visited 상태 : [True, False, False, True, True, True, False]
distances before update : [0, 29, inf, 22, 27, 10, 25]
sweeping curr node : 0
no edge, skip!
sweeping curr node : 1
no edge, skip!
sweeping curr node : 2
graph[node][j] : 12, distances[j] : inf
sweeping curr node : 3
already visited! OR distance already less than comparison!
sweeping curr node : 4
already visited! OR distance already less than comparison!
sweeping curr node : 5
no edge, skip!
sweeping curr node : 6
graph[node][j] : 18, distances[j] : 25
distances after update : [0, 29, 12, 22, 27, 10, 18]



arbitary seleced v : 1
final v : 2
node selected : 2
visited 상태 : [True, False, True, True, True, True, False]
distances before update : [0, 29, 12, 22, 27, 10, 18]
sweeping curr node : 0
no edge, skip!
sweeping curr node : 1
graph[node][j] : 16, distances[j] : 29
sweeping curr node : 2
already visited! OR distance already less than comparison!
sweeping curr node : 3
already visited! OR distance already less than comparison!
sweeping curr node : 4
no edge, skip!
sweeping curr node : 5
no edge, skip!
sweeping curr node : 6
no edge, skip!
distances after update : [0, 16, 12, 22, 27, 10, 18]



arbitary seleced v : 1
final v : 1
node selected : 1
visited 상태 : [True, True, True, True, True, True, False]
distances before update : [0, 16, 12, 22, 27, 10, 18]
sweeping curr node : 0
already visited! OR distance already less than comparison!
sweeping curr node : 1
already visited! OR distance already less than comparison!
sweeping curr node : 2
already visited! OR distance already less than comparison!
sweeping curr node : 3
no edge, skip!
sweeping curr node : 4
no edge, skip!
sweeping curr node : 5
no edge, skip!
sweeping curr node : 6
graph[node][j] : 15, distances[j] : 18
distances after update : [0, 16, 12, 22, 27, 10, 15]



arbitary seleced v : 6
final v : 6
node selected : 6
visited 상태 : [True, True, True, True, True, True, True]
distances before update : [0, 16, 12, 22, 27, 10, 15]
sweeping curr node : 0
no edge, skip!
sweeping curr node : 1
already visited! OR distance already less than comparison!
sweeping curr node : 2
no edge, skip!
sweeping curr node : 3
already visited! OR distance already less than comparison!
sweeping curr node : 4
already visited! OR distance already less than comparison!
sweeping curr node : 5
no edge, skip!
sweeping curr node : 6
already visited! OR distance already less than comparison!
distances after update : [0, 16, 12, 22, 27, 10, 15]



result distance sum : 102

 

---

참조 :

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

[알고리즘] Prim 알고리즘 이란 - Heee's Development Blog

https://sexy-developer.tistory.com/58

[알고리즘 자습]그래프(Graph) - 5. 최소 신장 트리 - 프림(Prim) 알고리즘, 파이썬