최소신장트리(MST) 나만의 정리

최소 신장 트리(Minimum Spanning Tree)

• 최소 신장 트리(mst)란 ?
  • N개의 정점으로 이루어진 무방향 그래프에서 N개의 정점과 N-1개의 간선으로 이루어진 트리
  • 최소 신장 트리란 무방향 가중치 그래프에서 사이클을 형성하지 않고 가중치의 합이 최소를 구하는 트리 알고리즘
  • 대표적인 알고리즘으로 Prim 알고리즘, Kruskal 알고리즘, dijkstra알고리즘이 있다

0. 목차

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

1. Prim 알고리즘

• 하나의 정점에서 연결된 간선들 중에 하나씩 선택면서 MST를 만들어가는 방식
  1. 임의 정점을 하나 선택해서 시작
     • 선택한 정점과 인접하는 정점들 중의 최소비용의 간선이 존재하는 정점을 선택
  2. 모든 정점이 선택될 때 까지 1,2과정을 반복
• 프림알고리즘의 경우 인접행렬 or 인접리스트로 풀수있고 우선순위큐인 heapq 활용하여 시간복잡도를 줄일수도있다.

# 인접행렬로 푼 문제
V, E = map(int,input().split())
adj = [[0]*V for _ in range(E)]
for i in range(E):
    s,e,c = map(int,input().split())
    adj[s][e] = c
    adj[e][s] = c

INF = float('inf')  # 무한
key = [INF]*V       # 각각의 노드 사이에서 최소 가중치 값이 있음
p = [-1]*V          # 각각 객체에는 before 노드번호 있음
mst = [False] * V   # 시작점이 다른 정점으로 이동을 했냐?? 의 유무

key[0] = 0
cnt = 0
result = 0  # 모든 가중치의 합
while cnt < V:
        min = INF
        u = -1
        ############################################################
        # 인접 정점중 가중치값이 있는 key 배열에서 가장 작은 min값을 찾은뒤 
        # 해당 노드번호로 이동을 위한 u를 정의
        ############################################################
        for i in range(V):
            if not mst[i] and key[i] < min:
                min = key[i]    
                u = i

        ############################################################
        # 이동한 정점의 방문표시를 위한 true를 하고 result에 가중치를 더해준다
        ############################################################
        mst[u] = True   # 이동한 정점인 u가 방문했음을 표시
        result += min
        cnt += 1

        ############################################################
        # 이동한 정점에서의 인접정점의 가중치(key)를 모두 저장시키고,
        # 기존의 저장되있던 가중치보다 작을경우에도 다시 갱신을 한다,
        # adj[u][w] > 0 : 인접행렬이 있고
        # not mst[w]    : 방문를 하지 않고
        # key[w] > adj[u][w] : 기존의 저장된 가중치보다 작을경우에만
        # 해당 인접 정점에 가중치를 저장하고 현재 위치 표시(p)를 한다.
        # 주의!! 이동을 한것은 아니다!! 임시로 저장해둔것!!
        ############################################################
        for w in range(V):
            if adj[u][w] > 0 and not mst[w] and key[w] > adj[u][w]:
                key[w] = adj[u][w]
                p[w] = u

print(key)        # 노드간의 가중치
print(p)        # p배열의 각각의 현재 위치 index에 있는 숫자가 현재위치 이전의 노드번호
print(mst)        # 방문배열
print(result)    # 최단거리를의 가중치의 합
'''
7 11
0 5 60
0 1 32
0 2 31
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51
'''

2. Kruskal 알고리즘

• 간선을 하나씩 선택해서 mst를 찾는 알고리즘
  1. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬
  2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴
     • 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택
  3. n-1개의 간선이 선택될때까지 2번을 반복
• KRUSKAL 알고리즘의 관건은 사이클의 존재를 찾고 제외시키는것
  • => 정점의 대표자가 같으면 사이클이 발생을 의미,
• KRUSKAL 알고리즘을 구현하기 위해서는 상호집합배타의 개념을 알고있어야한다.

알고리즘 구현

# make_set : 모든 정점에 대해 집합 생성
def make_set(x):
    p[x] = x

# 대표자를 찾는 함수(== 같은 집합인지를 알아보는 함수)
def find_set(x):
    if p[x] == x:
        return x
    else:
        p[x] = find_set(p[x])
        return p[x]

# x,y 두 함수를 합칠경우 x,y중 대표를 찾은뒤 랭크가 큰쪽이 부모가 되는거
def union(x, y):
    px = find_set(x)
    py = find_set(y)
    if rank[px] > rank[py]:  # 대표가 px
        p[py] = px
    else:
        p[px] = py  # 대표가 py
        if rank[py] == rank[py]:  # 랭크가 같으면 py의 랭크를 +=1 해준다
            rank[py] += 1


V, E = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(E)]

# 간선을 간선의 가중치기준으로 정렬
edges.sort(key=lambda x: x[2])

p = [0] * V     # 대표가 있는 배열
rank = [0] * V  # tree의 높이를 저장하는 배열

# 모든 정점에 대해 집합을 만든다
for i in range(V):
    make_set(i)

result = 0
mst = []  # 최소 가중치를 위한 경로를 저장
cnt = 0
# 모든 간선에 대해서 반복 -> V-1개의 간선이 선택될때까지
for i in range(E):
    # s:시작점, e:도착점, c:가중치
    s, e, c = edges[i][0], edges[i][1], edges[i][2]
    ##############################################################
    # 사이클이 아닐때만 간선을 선택
    # =>kruskal 알고리즘의 목표는 사이클을 돌지 않고 최단거리로 이동하는것
    # 사이클이 같을경우는 대표자가 같을경우와 같은말임
    # 대표자가 같을 경우를 찾기위해 find_set 함수를 통해 대표자를 찾는다.
    ##############################################################

    if find_set(s) == find_set(e):
        # 같을경우 continue하여 for문으로
        continue

    # 간선이 사이클이 아닐경우(== 두 정점의 대표가 다르다면)
    # => mst에 간선정보 더하기/ 두 정점을 합친다 => union
    result += c
    mst.append(edges[i])
    union(s, e)  # 두 간선집합이 사이클이 아닐때 => union함수를 통해 합쳐준다
    cnt += 1
    if cnt == V - 1: break

print(mst)
print(result)
'''
입력
7 11
0 5 60
0 1 32
0 2 31
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51
'''

3. Dijkstra 알고리즘

• 모든 정점의 가중치를 비교하며 최단거리를 구하기 위한 알고리즘
• 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
• 시작점 ~ 끝 장점까지 최단경로를 구할때 필요한 알고리즘
• dijkstra(다익스트라) 알고리즘(음의 가중치를 허용하지 않음)
• 모든 정점들에 대한 최단경로를 위한 알고리즘
• Floyd-Warshall (플로이드 워샬)알고리즘

알고리즘 구현

# dist, selected 배열 준비
# 시작점 선택
# 모든 정점이 선택될때 까지
# 아직 선택되지 않고 dist값이 최소인 정점 : u
# 정점 u의 최단거리 결정
# 정점 u에 인접한 정점에 대해서 간선완화

V,E = map(int,input().split())
# 인접리스트 생성
adj = { i : [] for i in range(V)}
for i in range(E):
    s,e,c = map(int,input().split())
    adj[s].append([e,c])

INF = float('inf')
# dist, selected 배열 준비
dist = [INF]*V          # 결국, 시작점에서 각각의 정점까지 최소의 가중치값
selected = [False]*V    # 방문표시를 위한 배열
dist[0] = 0                # 시작점을 위한 설정
cnt = 0
# print(adj)
while cnt < V:
    # 현재 정점의 인접정점중 dist(가중치)가 최소인 정점찾은뒤 해당 위치를 u에 할당
    min = INF
    u = -1
    for i in range(V):
        if not selected[i] and dist[i] < min:
            min = dist[i]
            u = i
    # 가중치가 최소인 노드의 위치 u를 찾은뒤 방문표시
    selected[u] = True

    # 간선완화
    # 이동한 정점의 도착정점과 가중치를 통해 다음정점에 정의되있던 가중치와 비교하며 갱신을 진행한다.
    for w, cost in adj[u]:  # 도착정점, 가중치
        if dist[w] > dist[u]+cost:    # 다음 정점의 누적가중치가 누적가중치 + 두 정점간 가중치보다 클경우 
            dist[w] = dist[u]+cost    # 새로 갱신을 진행 => 최소값을 찾아야하기 때문에
    cnt +=1

# 결국 dist에는 각 시작점에서 각 정점까지의 최소 가중치(최단거리)가 있다.
print(dist)
'''
다익스트라 + 인접리스트
입력
6 11
0 1 3
0 2 5
1 2 2
1 3 6
2 1 1
2 3 4
2 4 6
3 4 2
3 5 3
4 0 3
4 5 6
'''

tip

• 프림의 경우에는 모든 node를 돌면서 최소가중치를 찾는데 유용하게 쓰임
  • 서울에서 출발하여 부산을 갈때 서울 => 속초 => 부산보다 서울 => 대전 => 부산 방향으로 가는게 더 빠르게 갈수있음
  • 위 예시처러 여러 경로가 있을때 가장 최소의 거리를 구할때 유용
• Dijkstra은 시작정점만을 기준으로 모든 정점의 최단거리를 구할때 유용하게 쓰임
  • Dijkstra은 서울을 기준으로 의정부, 시흥, 속초, 부산 등등 여러 도시를 가기 위한 최단 거리를 구할때 유용