플레찍었으니 정리해보는 알고리즘 노트 - 5 유니온파인드, 최소 신장 트리, 위상정렬

유니온 파인드 알고리즘이란?

그래프 알고리즘의 일종으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.

 

def find(x,parent):
    if x != parent[x]:
        parent[x] = find(parent[x],parent)
    return parent[x]

def union(a,b,parent):
    a = find(a,parent)
    b = find(b.parent)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

 특정 노드의 루트 노드를 찾는 find함수와 두 노드를 합치는 union 함수로 이루어져있다.

find 함수는 재귀함수를 이용해 특정 노드의 루트 노드가 나올때까지(자기 자신이 부모일때까지) 반복해서 찾아내고

union함수는 find 함수를 이용해 주어진 두 노드의 루트 노드를 찾은 후 작은 수 큰 수의 부모 노드가 되도록 변경한다.

 

그래프의 간선이 생길 시 union함수를 이용해 두 노드를 합치는 과정을 반복한다면

특정한 두개의 노드가 주어졌을때 find 함수를 이용해 두 그래프의 루트 노드를 비교하고 같은 그래프에 속하는지 알 수 있다.

 

최소 신장 트리(MST, Minimum Spanning Tree)란?

 

그래프의 일부 간선을 선택해 그래프 내의 모든 정점을 최소 비용으로 연결해낸 트리이다.

크루스칼 알고리즘이 가장 대표적인 구현방법인데 실제로는 유니온 파인드 알고리즘을 사용해서 쉽게 구현할 수 있다.

 

크루스칼 알고리즘은 그리디 알고리즘의 일종으로 사이클이 발생하지 않는 최소 가중치의 간선만을 골라나가 연결하는 방법이다.

간선을 연결할때 union 함수를 사용한다면 특정한 간선을 연결하면 사이클이 발생하는지를 find 함수를 통해 알아낼 수 있다.

 

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

import sys,heapq
  
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a,b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    elif b < a:
        parent[a] = b
        
v,e = map(int,sys.stdin.readline().strip().split())
parent = list(range(0,v+1))
route = []
ans = 0

for i in range(e):
    a,b,c = map(int,sys.stdin.readline().strip().split())
    heapq.heappush(route,(c,a,b))
    
while route:
    c,a,b = heapq.heappop(route)
    if find(a) != find(b):
        ans += c
        union(a,b)
        
print(ans)

최소비용의 간선을 구하는 데에는 힙 자료구조를 사용하면 빠르게 구할 수 있다.

 

 

위상 정렬 알고리즘이란?

순서가 정해진 작업을 수행하기 위해 그래프를 이용해 순서를 결정하는 알고리즘이다.

 

가장 많이 사용하는 방법은 큐를 이용한 방법이다.

1. 그래프의 두 정점이 연결된 경우 도착지점의 진입차수를 1개씩 증가시킨다.

2. 진입차수가 0인 정점을 큐에 삽입한다.

3. 큐에서 원소를 하나씩 꺼내며 연결된 간선을 제거한다.(연결된 정점의 진입차수를 1개씩 감소시킨다)

4. 진입차수가 0이 된 정점을 새롭게 큐에 삽입한다.

5. 큐가 빌 때까지 3-4의 과정을 반복한다.

 

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().strip().split())
indegree = [0]*(n+1) #진입차수 배열
graph = [[] for _ in range(n+1)]
que = deque()

for i in range(m):
    a,b = map(int,sys.stdin.readline().strip().split())
    graph[a].append(b)
    indegree[b] += 1
    
for i in range(1,n+1):
    if indegree[i] == 0:
        que.append(i)
        
while que:
    now = que.popleft()
    print(now,end = " ")
    
    for nextPoint in graph[now]:
        indegree[nextPoint] -= 1
        if indegree[nextPoint] == 0:
            que.append(nextPoint)