프림 알고리즘

 

프림알고리즘

프림 알고리즘은 그래프에서 최소 스패닝 트리(Minimum Spanning Tree, MST)를 구하는 알고리즘 중 하나이다.

MST란 원래 그래프의 모든 정점을 포함하면서 사이클이 없는 트리다.

최소 스패닝 트리는 그래프의 모든 정점을 가장 적은 비용으로 연결하는 트리를 말한다. 프림 알고리즘의 동작 방식은 

 

• 1. 임의의 정점을 선택하여 시작
• 2. 이 정점은 초기에 최소 스패닝 트리에 포함
• 3. 선택한 정점과 연결된 간선들 중에서 가장 가중치가 작은 간선을 선택
• 4. 이 간선으로 연결된 정점을 MST에 추가
• 5. MST에 포함된 정점들과 연결된 간선들 중에서 가장 가중치가 작은 간선을 선택

 모든 정점을 MST에 포함시킵니다. 프림 알고리즘은 우선순위 큐 를 사용하여 간선들을 관리하면 효율적으로 구현할 수 있다.

우선순위 큐를 사용하여 간선의 가중치를 기준으로 가장 작은 값을 빠르게 찾아낼 수 있기 때문이다.

프림 알고리즘은 그래프가 희소 그래프 인 경우에 유리하며, 간선의 개수(E)가 정점의 개수(V)보다 작을 때(즉, E << V^2) 효율적이다

이러한 경우 프림 알고리즘이 크루스칼 알고리즘보다 빠르게 동작할 수 있다. 간선의 개수가 매우 많은 경우에는 크루스칼 알고리즘이 프림 알고리즘보다 더 효율적일 수 있다.

 

구현 방식.

 

N ,M = map(int,sys.stdin.readline().split(" "))

visited = [False]*(N+1)
lst = [[] for _ in range(N+1)]
heap = [[0, 1]]

for _ in range(M):
    # 간선 , 가중치
    s, e, w = map(int, input().split())
    lst[s].append([w, e])
    lst[e].append([w, s])

count = 0
res = 0
while heap:
    if count == N:
        break
    a, b = heapq.heappop(heap)

    if not visited[b]:
        visited[b] = True
        res += a
        count += 1
        for i in lst[b]:
            heapq.heappush(heap,i)
print(res)

lst 에 연결된 간선들과, 가중치 값을 넣어준다.

 

1. 임의의 정점 0 을 선택하면

heap을 도는 동안, 0과 선택된 간선들중에 가장 작은 값이 맨 위에 있으니 그 간선이 아직 방문 되지 않았으면

그 간선을 방문처리해주고 visiteid[b] = True

가중치 값을 더해주고 res += a

b에서 뻗어 나가는 다른 가중치들을 heapq.heappush 해주므로 다음 while문 돌때 가장 최솟값을 뽑을 수 있게된다.

 

방문을 다하면 count == N  종료시켜주면 된다.

 

동작 그림이 궁금하다면

 

https://velog.io/@chosj1526/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%94%84%EB%A6%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Prims-Algorithm

[알고리즘] 프림 알고리즘 (Prim's Algorithm)

여기를 봐주시면 될것 같다.