Prim's Algorithm과 증명

Matthew Woo·2022년 1월 10일
0

Algorithm

목록 보기
1/3
post-thumbnail

Prim's Algorithm은 그래프에서 MST(최소신장트리)를 찾는 그리디 알고리즘이다.

minimum spanning tree (MST)이란?

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight - wikipedia

  • minimum
    edge에 가중치가 있는데 이 가중치를 최소로 하는 edge들을 선택하여야 하한다.
  • spanning
    모든 V 영역을 방문한다.
  • tree
    cycle이 발생하지 않는 것을 의미한다. edge를 통해 방문했던 vertax는 다른 edge를 통해 다시 방문해서는 안된다.

Prim's Algorithm

MST를 만들기 위해 반복해서 vertex를 선택함에 있어서
1. 이미 선택되지 않은 vertex이고 (선택된걸 다시 선택하면 cycle 이 생성되면 트리구조가 깨짐)
2. 가중치를 최소화할 수 있는 vertex

위 조건을 만족하는 가장 작은 edge 가중치로 이어진 vertex를 택한다면 MST를 구성할 수 있다는 알고리즘이다.
매 순간 선택에 있어서 가장 최적의 선택을 한 다는 점에서 그리디 알고리즘의 범주에 들어간다.

보다 자세한 과정은 아래 코드의 주석을 참고 바란다.

# example
V = 5
G = [[0, 9, 75, 0, 0],
     [9, 0, 95, 19, 42],
     [75, 95, 0, 51, 66],
     [0, 19, 51, 0, 31],
     [0, 42, 66, 31, 0]]
 

selected = [0, 0, 0, 0, 0] # 방문한 V는 True, 그렇지 않은 V는 False. 전부 False로 초기화

no_edge = 0 # 몇 개의 edge를 선택했는지
count = 0
selected[0] = True # 어떤 V 부터 방문으로하여 시작할 것인지. 어느 지점으로 시작해도 됨. 0, 1, 2 어떤 수를 넣어도 됨

while (no_edge < V - 1): # 아직 선택하지 않은 edge가 있다면 계속 선택.
    minimum = 10e7 # 선택할 수 있는 가중치가 가장 작은 edge를 택하기 위한 기준
    x = 0
    y = 0
    for i in range(V):
        if selected[i]: # 각 방문된 V에서 ~
            for j in range(V):
            	count += 1 # 이 j for문 안으로는 몇 번 실행될까요 반목문을 세개나 씀^^;?
                if ((not selected[j]) and G[i][j]): # ~ 아직 방문되지 않았고, 가중치가 있어 edge가 존하는 것 중 가장 작은 것을 찾기.
                    if minimum > G[i][j]:
                        minimum = G[i][j] # 가장 작은 가중치를 메모
                        x = i # 가장 작은 가중치 edge의 start
                        y = j # 가장 작은 가중치 edge의 end
                        
    print(str(x) + "-" + str(y) + ":" + str(G[x][y])) # edge의 start, end, 가중치 print
    selected[y] = True # start x 는 이미 선택된 V이기에 end를 방문처리해줌
    no_edge += 1 # edge가 하나 더 추가되었음.
    
    '''
    0-1:9
    selected 1 [True, True, 0, 0, 0]
    1-3:19
    selected 3 [True, True, 0, True, 0]
    3-4:31
    selected 4 [True, True, 0, True, True]
    3-2:51
    selected 2 [True, True, True, True, True]
    110 # 가중치 결과값
    50 # n ** 3 for문이 몇번 실행되었는지 결과값
    '''
    
    

how long does it take?

위 코드의 시간 복잡도는 어떻게 될까?

위 코드에서

while (no_edge < V - 1): 부분은 N번 실행된다. 모든 vertex의 수만큼.
for i in range(V): 각 선택에 있어서 방문되어 있는 vertex를 찾기 위해 for문이 돌아가고,
for j in range(V): 방문되어 있는 vertex에서 아직 방문은 하지않았지만 연결된 vertext 들을 찾는 다고 또 for문이 돌아갔다.

아니 잠깐 뭐가 이상하다. 시간복잡도가 n ** 3 세제곱이라고..?

만족스럽지 않은 결과인데 n의 세제곱이나 나오는 이유는 다음과 같다. 간선의 수를 k라 생각하고
vertex 정점의 수를 n이라고 생각했을때 이 두 관계는 다음과 같다

n - 1 <= k <= n(n-1)/2

즉 n번 각 vertext를 돌면서 각 vertext의 간선을 모두 확인하다보니 썩 그리 맘에 들지는 않는다.

이를 개선하는 방법은, 이미 확인한 간선을 다시 확인하지 않는 것 인데, 자료구조를 생성하여(배열) 메모라이징 방식으로 확인한 간선은 다시 탐색하지 않도록 해주거나, 힙큐를 이용한 방법이 있는데 힙큐방식은 다음과 같다.
힙 큐를 이용하여 vertex에서 연결된 간선들을 넣어주고, 그 다음 vertex 를 찾은 뒤에는 또 새로 연결된 간선들을 찾아주면서 최소한의 간선들만 택하는 방식을 사용하면 매번 for문들 돌면서 중복된 간선을 또 확인할 필요가 없어진다.

힙큐로 인해 가장 최소의 가중치를 찾기 위한 for문이 아닌 최소힙으로 도출해내어 더 좋은 효율을 얻을 수 있다.

def prim(graph, start_node):
    visited[start_node] = 1 # 방문 갱신
    candidate = graph[start_node] # 인접 간선 추출
    heapq.heapify(candidate) # 우선순위 큐 생성
    mst = [] # mst
    total_weight = 0 # 전체 가중치

    while candidate:
        weight, u, v = heapq.heappop(candidate) # 가중치가 가장 적은 간선 추출
        if visited[v] == 0: # 방문하지 않았다면
            visited[v] = 1 # 방문 갱신
            mst.append((u,v)) # mst 삽입
            total_weight += weight # 전체 가중치 갱신

            for edge in graph[v]: # 다음 인접 간선 탐색
                if visited[edge[2]] == 0: # 방문한 노드가 아니라면, (순환 방지)
                    heapq.heappush(candidate, edge) # 우선순위 큐에 edge 삽입

    return total_weight

그리디 증명

어느 vertex를 선택하여 시작을 하건간에 매번 선택할 때마다 최소 간선으로 연결된 vertex를 선택하면 어떻게 MST가 도출되는걸까?

MST Lemma(부명제):
A가 그래프 G의 spanning tree라고 하자. e(b) 는 A에 속하지 않은 G의 edge이다.

  1. A에 e(b)를 추가하면 cycle이 형성된다.
  2. 사이클이 형성된 부분에서 edge 빼면 spaning tree 가 형성됨
  3. 가중치가 낮거나 같은 edge를 더한다면 그 더해진 edge로 인한 그래프의 가중치도 낮거나 같다.

위 1, 2 조건을 만족시키면서
MST의 한 부분인 T에다가 방문하지 않은 최소 edge vertex 하나를 붙이더라도 해당 edge가 추가된 T는 MST 속성이 유지된다. 즉 3번, 가중치가 낮은 것을 더했기에 결과도 가중치가 낮다고 할 수 있다.

자꾸 같은 표현을 반복하는 것 같은데 정리하자면,
매 선택에 있어서 방문했던 vertex를 선택을 피하기에 cycle이 형성되지 않고, 매 선택에서 가중치가 가장 낮은 edge를 선택해왔기에 그 결과물의 그래프 또한 가중치는 낮으면서 cycle이 형성되지 않은 MST트리의 조건을 충족시킨다.

  • 본 글은 시간복잡도 관련하여 다소 수정 및 보완 필요합니다. 프림 알고리즘의 경우 memo방식을 사용할 경우 n제곱, 저처럼 메모를 사용하지 않을 경우 n세제곱, 힙큐 방식을 사용할 경우 nlogn. 이후 다잌스트라나 크루스칼 알고리즘을 보고 있는데
    보다 제대로 확인 후 수정할 예정입니다

관련 문제

백준 1197

참고영상

profile
Code Everyday

0개의 댓글