동빈나 2021 이코테 _ 8.기타 그래프이론 (union-find, kruskal, topology sort)

본 글은 동빈나 2021 이코테 _ 8. 기타그래프 이론을 정리한 글입니다!

---

서로소 집합 자료구조 _ Union-Find

• 서로소 집합이란 공통원소가 없는 두 집합을 의미한다.
• 서로소 부분집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
• 서로소 집합 자료구조(=합치기 찾기 자료구조)는 두종류의 연산을 지원한다.
  • 합집합(Union) : 두개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 
  • 찾기(find) : 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산

- Union의 인자값으로 각 노드가 들어감 

- 초기에는 각각이 하나의 집합으로 여겨지며 자기자신이 곧 부모가 된다.

- 합치기 연산에서, 일반적으로 두 노드중 값이 더 큰 노드의 부모값을 더 작은노드의 부모로 갱신한다.

• 단, 여기서 부모노드는 루트노드가 아니라는것을 주의해야함 (3번과 4번은 부모노드는 다르지만 서로 같은집합이다)

• 위 사진처럼 손쉽게 집합의 형태를 확인할 수 있다. (총 2개의 집합으로 나뉘어지며, 두 집합은 서로소관계이다)
• 기본적인 형태의 서로소 집합 자료구조에서는 루트노드에 즉시 접근할 수 없다.
  • 루트노드를 찾기위해 부모테이블을 계속 확인해서 거슬러 올라가야함
  •  

---

 서로소 집합 자료구조의 기본 구현

- 유니온파인드 알고리즘을 통해, 여러개의 노드가 존재할때 2개의 노드를 선택해서 현재 두 노드가 같은 집합에 있는지를 판별할 수 있다.

# 특정 원소가 속한 집합을 찾기 -> x의 루트노드를 반환한다.
def find_parent(parent, x):
    #루트 노드를 찾을때까지 따라들어가며 재귀호출 (루트노드는 자기자신이 부모노드이므로)
    if parent[x] != x: #루트노드가 아니면 
        return find_parent(parent, parent[x]) #재귀호출 
    return x #루트노드일때 자기자신을 반환 

#두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
	#각각의 루트노드를 찾는다.
    a = find_parent(parent, a) 
    b = find_parent(parent, b)
    if a<b: #두 노드중 큰 노드의 부모를 바꿔준다.
        parent[b] = a
    else:
        parent[a] = b

#노드와 간선의 개수 입력
v,e = map(int, input().split())
parent = [0] * (v+1) #부모테이블

#초기상태 - 부모를 자기자신으로 초기화
for i in range(1,v+1):
    parent[i] = i

#Union연산 각각 수행
for i in range(e):
    a,b = map(int, input().split())
    union_parent(parent, a, b)

#각 원소가 속한 집합 출력
for i in range(1, v+1):
    print(find_parent(parent, i))

#부모테이블 내용 출력
for i in range(1, v+1):
    print(parent[i])

기본 구현의 문제점

• 합집합 연산이 편향되게 이루어지는 경우 찾기함수가 비효율적으로 동작한다.
• 최악의 경우 찾기함수가 모든 노드를 다 확인하게 되어 시간복잡도가 O(V)가 된다.

찾기함수 최적화방법 - 경로압축

• 찾기함수를 재귀적으로 호출한 뒤에 부모 테이블값을 바로 갱신한다.
• 재귀를 호출한 결과값을 자신의 부모로 갱신 

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    #루트노드가 아니라면 루트 노드를 찾을때까지 재귀호출 (루트노드는 자기자신이 부모노드이므로)
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]
    

즉, 경로압축 기법을 사용하면 찾기함수를 호출한 이후 각 노드에 대하여, 해당 노드의 루트노드가 바로 부모노드가 된다.

ex) 1 <- 2 <- 3 <- 4 <- 5 인 상황에서 5번에 대하여 찾기함수를 실행하면 재귀적으로 호출되며 2,3,4,5 -> 1이 된다.

---

서로소 집합을 활용한 사이클 판별

• 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할때 사용할 수 있다.
  • 참고로 방향그래프에서의 사이클여부는 DFS를 이용하여 판별할 수 있다.
• 사이클 판별 알고리즘
  
  • 각 간선을 하나씩 확인하며 두 노드의 루트노드를 확인한다.
    • 루트노드가 다르다면, 두 노드에 대하여 Union연산을 수행한다. (간선이 존재한다 -> 둘은 같은집합이다 -> 루트를 같게한다)
    • 루트노드가 같다면, 사이클이 발생한것이다.
  • 그래프에 포함되어 있는 모든 간선에 대하여 위 과정을 반복한다.

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    #루트 노드를 찾을때까지 따라들어가며 재귀호출 (루트노드는 자기자신이 부모노드이므로)
    if parent[x] != x: #x가 루트노드가 아니라면
        parent[x] =  find_parent(parent, parent[x])
    return parent[x]

#두 원소가 속한 집합을 합치기 
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a<b: #두 노드중 큰 노드의 부모를 바꿔준다.
        parent[b] = a
    else:
        parent[a] = b

v,e = map(int, input().split())
parent = [0] * (v+1) #부모테이블

#초기상태 - 부모를 자기자신으로 초기화
for i in range(1,v+1):
    parent[i] = i
 
cycle = False #사이블 발생여부

for i in range(e):
    a,b = map(int, input().split())
    #사이클이 발생한 경우 종료
    if find_parent(parent,a) == find_parent(parent, b):
        cycle = True
        break
    else:
        union_parent(parent, a, b)

if cycle:
    print('사이클이 발생했습니다.')
else:
    print('사이클이 발생하지 않았습니다.')

---

신장트리란?

• 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분그래프
  • 모든노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다

최소신장트리

• 최소한의 비용으로 구성되는 신장트리를 찾아야 할때
• 예를들어 N개의 도시가 존재하는 상황에서 두 도시사이에 도로를 놓아 전체 도시가 서로 연결 될 수 있게 도로를 설치하는 경우 ( 두도시 a,b를 선택했을때, a에서 b로 가는 경로가 반드시 존재하도록 도로를 설치해야함)
• 1,2,3노드가 잇을때, 1,2와 2,3을 연결하면 1,3을 연결하지 않아도 모든노드가 연결되어있다.

크루스칼 알고리즘

• 간선데이터를 비용에 따라 오름차순 정렬한다. (비용이 적은 간선부터 확인)
• 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
  • 사이클이 발생하지 않는경우, 최소신장트리에 포함시킨다. (By Union-Find)
  • 사이클이 발생하는경우, 최소신장 트리에 포함시키지 않는다. 
• 모든 간선에 대하여 2번과정을 반복한다.

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

def union_parent(parent, a, b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a<b:
        parent[b] = a
    else:
        parent[a] = b

v,e = map(int, input().split())
parent = [0] * (v+1)

#간선을 담을 리스트, 최종비용을 담을 변수
edges = []
result = 0

for i in range(1, v+1):
    parent[i] = i

for _ in range(e):
    a,b,cost = map(int, input().split())
    edges.append((cost,a,b))

edges.sort()

for edge in edges:
    cost, a, b = edge
    # a,b노드의 루트가 다른경우 = 서로다른 집합인경우 = 사이클이 없다
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        result += cost

print(result)

• 크루스칼 알고리즘의 성능분석
  • 간선의 개수가 E개일때, O(ElogE)의 시간복잡도를 갖는다.
  • 크루스칼 알고리즘에서 가장많은 시간을 요구하는곳이 간선을 정렬하는 부분인데, 표준 라이브러리를 사용해 E개의 데이터를 정렬할때 걸리는 시간복잡도가 O(ElogE)이기때문

---

위상정렬

• 사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는것을 의미함
• ex) 선수과목을 고려한 학습순서 설정 (자료구조 -> 알고리즘 -> 고급알고리즘)

진입차수와 진출차수

• 진입차수 : 특정한 노드로 들어오는 간선의 개수
• 진출차수 : 특정한 노드에서 나가는 개수

위상정렬 알고리즘 (큐 이용)

• 진입차수가 0인 모든 노드를 큐에 넣는다.
• 큐가 빌때까지 다음의 과정을 반복한다.
  • 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
  • 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
• 결과적으로 각 노드가 큐에 들어온 순서가 위상정렬을 수행한 결과와 같다!!

위상정렬의 특징

• 위상정렬은 DAG에서만 수행할 수 있다 (순환하지 않는 방향그래프)
• 여러답이 존재할 수 있다. ( 한 단계에서 큐에 들어가는 원소가 2개 이상인경우)
• 모든 원소를 방문하기 전에 큐가 비면 사이클이 존재한다고 판단할 수 있다.
• 스택을 활용한 DFS로도 위상정렬을 수행할 수 있다.

from collections import deque

#노드의 개수와 간선의 개수 입력
v,e = map(int, input().split())
# 모든 노드에 대한 진입차수를 0으로 초기화 ('나'로 들어오는 간선의 개수)
indegree = [0] * (v+1)

#각 노드에 연결된 간선정보를 담기위한 연결리스트 초기화
graph = [[] for _ in range(v+1)]

# 방향 그래프의 모든 간선정보 입력받기
for _ in range(e):
    a,b = map(int, input().split())
    graph[a].append(b) # 정점 a에서 b로 이동 
    indegree[b] +=1 #진입차수 증가

# 위상정렬 함수
def topology_sort():
    result = [] # 알고리즘 수행결과를 담을 리스트
    q = deque() #큐 기능을 위한 라이브러리 사용
    # 처음 시작할때는 진입차수가 0인 모든 노드를 큐에 삽입
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)
    # 큐가 빌때까지
    while q:
        # 큐에서 꺼내고
        now = q.popleft()
        result.append(now)
        
        # 꺼낸 노드로부터 연결된 노드들을 순회하며 해당 노드들의 진입차수에서 1을 빼고 0이된 노드들이 잇다면 큐에 담는다.
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
    
    #위상정렬의 수행결과 출력
    for i in result:
        print(i)

topology_sort()

• 위상정렬의 성능분석
  • 차례로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거해야 하므로 시간복잡도는 O(V+E)임