그래프 - MST(최소 비용 신장 트리)

MST(최소비용신장트리)

• 그래프에서 최소 비용 문제

모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리

두 정점 사이의 최소 비용의 경로 찾기

 

• 신장트리

n 개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n - 1개의 간선으로 이루어진 트리

 

• 최소 신장 트리(Minimum Spanning Tree)

무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

 

이러한 MST를 구하는 2가지 알고리즘

 

Prim 알고리즘

• 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식

1) 임의 정점을 하나 선택해서 시작

2) 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택

3) 모든 정점이 선택될 때 까지 1), 2) 과정 반복

 

• 서로소인 2개의 집합 정보를 유지

트리 정점들 - MST를 만들기 위해 선택된 정점들 

비트리 정점들 - 선택되지 않은 정점들

 

시간복잡도 - $n^2$

 

# parent를 사용한 방법
def prim(n):

    total = 0

    for _ in range(V+1):
        min_v = INF
        for i in range(V+1):
            if visit[i]:
                continue
            if W[i] < min_v:
                min_v = W[i]
                u = i

        visit[u] = 1
        total += G[P[u]][u]

        for v in range(V+1):
            if G[u][v] != 0 and visit[v] == 0 and G[u][v] < W[v]:
                W[v] = G[u][v]
                P[v] = u

    return total

for tc in range(1,T+1):
    V, E = map(int,input().split())

    INF = 987654321

    G = [[0] * (V+1) for _ in range(V+1)]
    W = [INF] * (V+1)
    P = list(range(V+1))
    visit = [0] * (V+1)

    W[0] = 0

    for _ in range(E):
        n1, n2, w = map(int,input().split())
        G[n1][n2] = w
        G[n2][n1] = w

    ans = prim(0)

    print(f"#{tc} {ans}")

# parent없이 
def prim(n):

    total = 0

    for _ in range(V+1):
        min_v = INF
        for i in range(V+1):
            if visit[i]:
                continue
            if W[i] < min_v:
                min_v = W[i]
                u = i

        visit[u] = 1

        for v in range(V+1):
            if G[u][v] != 0 and visit[v] == 0 and G[u][v] < W[v]:
                W[v] = G[u][v]

    print(sum(W))
    
for tc in range(1,T+1):
    V, E = map(int,input().split())

    INF = 987654321

    G = [[0] * (V+1) for _ in range(V+1)]
    W = [INF] * (V+1)
    visit = [0] * (V+1)

    W[0] = 0

    for _ in range(E):
        n1, n2, w = map(int,input().split())
        G[n1][n2] = w
        G[n2][n1] = w

    ans = prim(0)

    print(f"#{tc} {ans}")

# heapq 사용
import heapq

def Prim():

    visit = [0] * (V+1)

    heap = []
    heapq.heappush(heap, (0,0))
    ans = 0

    while heap:
        w, v = heapq.heappop(heap)

        if not visit[v]:
            ans += w
            visit[v] = 1

            for idx,wei in G[v]:
                if not visit[idx]:
                    heapq.heappush(heap,(wei,idx))
    return ans

for tc in range(1,T+1):
    V, E = map(int,input().split())

    G = [[] for _ in range(V + 1)]

    for _ in range(E):
        n1, n2, w = map(int,input().split())
        G[n1].append((n2,w))
        G[n2].append((n1,w))

    print(f"#{tc} {Prim()}")

 

 

 

KRUSKAL 알고리즘

• 간선을 하나씩 선택해서 MST를 찾는 알고리즘

서로소 집합 개념 사용

1) 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬

2) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴

 - 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택

3) n - 1개의 간선이 선택될때 까지 2)를 반복

 

시간복잡도 - $mlog(m)$ - 간선 정렬

 

def make_set(x):
    parent[x] = x

def find_set(x):
    while parent[x] != x:
        x = parent[x]
    return x

    # if parent[x] == x:
    #     return x
    # else:
    #     return find_set(parent[x])

# rank X
def union(x, y):
    parent[find_set(y)] = find_set(x)


def kruskal(edges):
    # 초기화
    total = 0
    cnt = 0
    for i in range(V):
        make_set(i)
    # 정렬
    edges.sort(key = lambda x:x[2])
    # 두 정점의 fingset 확인
    for i in range(E):
        if find_set(edges[i][0]) != find_set(edges[i][1]):
            total += edges[i][2]
            cnt += 1
            union(edges[i][0],edges[i][1])
        if cnt == V - 1:
            break
    return total


V, E = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(E)]
parent = [0] * V
print(kruskal(edges))

# rank 및 path compression 사용            
            
def make_set(x):
    parent[x] = x
    rank[x] = 0

def find_set(x):
    if parent[x] != x:
        # path compression 사용
        parent[x] = find_set(parent[x])
    return parent[x]

    # if parent[x] == x:
    #     return x
    # else:
    #     return find_set(parent[x])

# rank O
def union(x, y):
    Link(find_set(x),find_set(y))

def Link(x,y):
    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


def kruskal(edges):
    # 초기화
    total = 0
    cnt = 0
    for i in range(V):
        make_set(i)
    # 정렬
    edges.sort(key = lambda x:x[2])
    # 두 정점의 fingset 확인
    for i in range(E):
        if find_set(edges[i][0]) != find_set(edges[i][1]):
            total += edges[i][2]
            cnt += 1
            union(edges[i][0],edges[i][1])
        if cnt == V - 1:
            break
    return total


V, E = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(E)]
parent = [0] * V
print(kruskal(edges))