Spanning Tree 신장 트리

💡 그래프 내의 모든 정점을 포함하는 트리

• 그래프에서 일부 간선을 선택해서 만든 트리
• 그래프의 최소 연결 부분 그래프
  • 최소 연결 == 간선 수가 가장 적음
  • n개의 정점을 가지는 그래프의 최소 간선 수는 n-1개

MST, Minimum Spanning Tree

💡 Spanning Tree 중 사용된 간선들의 가중치 합이 최소인 트리
즉, 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
-> 사이클 없는 == 트리

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

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

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

모든 노드를 연결할 때 가장 적은 비용이 드는 방법을 찾아라

조건

• 간선의 가중치의 합이 최소여야 함

• n개의 정점을 가지는 그래프에 대해 반드시 n-1개의 간선만을 사용

• 사이클이 포함되어선 안됨

+ 가중치 있는 그래프 표현

1.

2.

MST 구현 방법

1. Prim 알고리즘
2. Kruskal 알고리즘

Prim 알고리즘

개념

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

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

• 임의 정점을 하나 선택

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

조건

• 정점 선택을 기반으로 하는 알고리즘

• 임의의 간선을 선택하고 선택한 간선의 정점으로 부터 가장 낮은 가중치를 갖는 정점을 선택

  • 이전단계에서 만들어진 신장 트리를 확장
  • 모든 정점이 선택될 때까지 반복

구현

"""
5 6
1 2 3
1 3 7
2 3 1
3 4 4
2 5 2
5 4 2
"""

def prim(start, V):  # MST 가중치의 합을 리턴하는 함수. 1~V번 노드인 경우
    key = [INF] * (V + 1)  # key[i] i가 MST에 연결되는 비용
    key[1] = 0
    MST = [0] * (V + 1)
    pi = [0] * (V + 1)

    for _ in range(V):  # 모든 정점이 MST에 포함될 때 까지
        # MST에 포함되지 않은 정점 중 key[u]가 최소인 u 찾기
        u = 0
        minV = INF

        for i in range(1, V + 1):
            if MST[i] == 0:
                if key[i] < minV:
                    u = i
                    minV = key[i]
        MST[u] = 1  # key[u]가 최소인 u를 MST에 추가

        for v in range(V + 1):  # u에 인접인 v에 대해
            if MST[v] == 0 and adj[u][v] != 0:
                if key[v] > adj[u][v]:  # u를 이용해 기존보다 더 작은 비용으로 MST에 연결된다면
                    key[v] = adj[u][v]
                    pi[v] = u  # v는 u와 연결해서 MST에 포힘될 예정

    return sum(key[start:])  # MST 가중치의 합 리턴

V, E = map(int, input().split())
INF = 10000
# 인접행렬
adj = [[0] * (V + 1) for _ in range(V + 1)]

for _ in range(E):
    u, v, w = map(int, input().split())
    adj[u][v] = w
    adj[v][u] = w  #  무방향 그래프에서 MST 구성

# print(prim(0, V))  # 노드 시작 번호 0인 경우(교재 예시)
print(prim(1, V))  # 노드 시작 번호 1인 경우(코드 주석의 예시)

# 우선순위큐를 사용하지 않는 코드
'''
5 6
1 2 3
1 3 7
2 3 1
3 4 4
2 5 2
5 4 2
'''

V, E = map(int, input().split())
INF = 10000
# 인접행렬
adj = [[INF]*(V+1) for _ in range(V+1)]

for i in range(V+1):
    adj[i][i] = 0

for _ in range(E):
    u, v, w = map(int, input().split())
    adj[u][v] = w
    adj[v][u] = w  #  무방향 그래프에서 MST 구성

key = [INF]*(V+1)  # key[i] i가 MST에 연결되는 비용
key[1] = 0
MST = [0] * (V+1)
pi = [0] * (V+1)

for _ in range(V):  # 모든 정점이 MST에 포함될 때 까지
    # MST에 포함되지 않은 정점 중 key[u]가 최소인 u 찾기
    u = 0
    minV = INF
    for i in range(1, V+1):
        if MST[i]==0:
            if key[i] < minV:
                u = i
                minV = key[i]
    MST[u] = 1  # key[u]가 최소인 u를 MST에 추가
    for v in range(1, V+1):  # u에 인접인 v에 대해
        if MST[v] == 0 and u!=v and adj[u][v]< INF:
            if key[v] > adj[u][v]:  # u를 이용해 기존보다 더 작은 비용으로 MST에 연결된다면
                key[v] = adj[u][v]
                pi[v] = u    # v는 u와 연결해서 MST에 포힘될 예정
print(key)
print(pi)

KRUSKAL 알고리즘

• 그리디 알고리즘

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

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

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

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

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

동작 과정

1. 간선 데이터를 비용에 따라 오름차순으로 정렬
2. 간선 데이터를 확인하며 형제의 간선이 사이클을 발생시키는지 확인
3. 사이클이 발생하지 않는 경우 MST에 포함
4. 사이클이 발생하는 경우 MST에 포함 X
5. 모든 간선에 대하여 2번 위 과정을 반복

구현

'''
6 11
0 1 32
0 2 31
0 5 60
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51
'''

def find_set(x): # x가 속한 집합의 대표 리턴 
    while x != rep[x]: # x == rep[x]까지 
        x = rep[x]
    return x 

def union(x,y): 
    rep[find_set(y)] = find_set(x)

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

# make_set
rep = [i for i in range(V+1)]
graph = []
for _ in range(E):
    v1, v2, w = map(int,input().split())
    graph.append([v1,v2,w])

# 가중치 기준 오름차순 정렬
graph.sort(key=lambda x : x[2])

# N개 정점 (V+1), N-1 개의 간선 선택 
N = V +1
s = 0 # MST에 포함된 간선의 가중치의 합 
cnt = 0
MST = []
for v,u,w in graph :  # 가중치가 작은 것부터 
    if find_set(u) != find_set(v) : # 사이클이 생기지 않으면 
        cnt += 1
        s += w # 가중치 합 
        MST.append([u,v,w])
        union(u,v)
        if cnt == N-1: # MST 구성 완료
            break

print(s)
print(MST)