[백준 파이썬 1197번 최소 스패닝 트리] 크루스칼 알고리즘, 프림 알고리즘

1197번: 최소 스패닝 트리

1197번: 최소 스패닝 트리

트리의 정의

1. 트리란 사이클이 없이 모든 정점이 연결되어있는 그래프다.
2. 왼쪽 자식이 어쩌구, 오른쪽 자식이 어쩌구 이딴 얘기는 트리의 정의에 포함되지 않는다
3. 루트가 있어야 한다는 조건 이런것도 없다.

트리는 그저 사이클이 없이 모든 정점이 연결되어있는 그래프이므로, 하나의 노드에 자식 노드가 여러개일 수 있다.

*이진트리와 헷갈리지 말자!

 

스패닝 트리 = 신장 트리

그래프의 부분 그래프를 지칭

어떤 그래프(트리가 아니어도 됨)가 있고, 그 그래프의 모든 정점을 지나는 트리를 만들면, 그게 바로 스패닝 트리다.

*최소 스패닝 트리 → 지도가 주어져 있고 모든 점들을 잇는 최소거리라고 생각하면 될 듯

 

크루스칼 알고리즘

언제 쓰나요? -> 최소 스패닝 트리를 구할 때 -> 최소거리로 모든 노드를 연결할 때

 

노드들의 부모들이 같을 때 트리에 넣으면 사이클 발생 → 부모들이 같은지만 체크

핵심은 자식들의 부모를 바꿔주는 것이 아니라 부모들의 부모를 바꿔준다는 것

-> 가장 최상위 부모를 바꿈으로서 밑에 자식들의 부모도 모두 바뀌는 원리

이후 사이클이 생기지 않게 하나하나 담으면 정렬이 되어 있기 때문에 최소값을 찾는다

 

[Python] 최소 신장 트리를 찾는 크루스칼(Kruskal) 알고리즘

[Python] 최소 신장 트리를 찾는 크루스칼(Kruskal) 알고리즘

import sys

input = lambda: sys.stdin.readline().rstrip()

V, E = map(int, input().split())

# Kruskal Algorithm
# <https://techblog-history-younghunjo1.tistory.com/262>
edges = []
for _ in range(E):
    A, B, C = map(int, input().split())
    edges.append((A, B, C))
edges.sort(key=lambda x: x[2])  # C(Cost)가 적은 것부터 정렬

# Union-Find
parent = [i for i in range(V + 1)]

def get_parent(x):
    if parent[x] == x:
        return x
    parent[x] = get_parent(parent[x])  # get_parent 거슬러 올라가면서 parent[x] 값도 갱신
    return parent[x]

def union_parent(a, b):
    a = get_parent(a)
    b = get_parent(b)

    if a < b:  # 작은 쪽이 부모가 된다. (한 집합 관계라서 부모가 따로 있는 건 아님)
        parent[b] = a
    else:
        parent[a] = b

def same_parent(a, b):
    return get_parent(a) == get_parent(b)

answer = 0
for a, b, cost in edges:
    # cost가 작은 edge부터 하나씩 추가해가면서 같은 부모를 공유하지 않을 때(사이클 없을 때)만 확정
    if not same_parent(a, b):
        union_parent(a, b)
        answer += cost
print(answer)

 

+23.09.25

프림 알고리즘

간선의 개수가 작은 경우에는 크루스칼, 간선의 개수가 많은 경우에는 프림

크루스칼 시간 복잡도 O(E log E)

프림 시간 복잡도 O(E log V)

* E = 간선의 수, V = 노드의 수

 

https://ongveloper.tistory.com/376

[알고리즘] 크루스칼(Kruskal)과 프림(Prim)

from heapq import heappush, heappop
import sys; input=sys.stdin.readline

def prim(start, weight):
    visit = [0] * (V + 1) # 정점 방문 처리
    q = [[weight, start]] # 힙 구조를 사용하기 위해 가중치를 앞에 둠
    ans = 0 # 가중치 합
    cnt = 0 # 간선의 개수
    while cnt < V: # 간선의 개수 최대는 V-1
        k, v = heappop(q)
        if visit[v]: continue # 이미 방문한 정점이면 지나감
        visit[v] = 1 # 방문안했으면 방문처리
        ans += k # 해당 정점까지의 가중치를 더해줌
        cnt += 1 # 간선의 갯수 더해줌
        for u, w in G[v]: # 해당 정점의 간선정보를 불러옴
            heappush(q, [w, u]) # 힙에 넣어줌
    return ans

V, E = map(int, input().split())
G = [[] for _ in range(V + 1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    G[u].append([v, w])
    G[v].append([u, w])

print(prim(1, 0))