서로소 집합

• Disjoint Sets : 공통 원소가 없는 두 집합
• 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
• 두 종류의 연산 지원
  • Union : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  • Find : 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산
• 1. Union 연산을 확인해 서로 연결된 두 노드 A, B 확인
  • A와 B의 루트 노드를 각각 찾는다.
  • A의 루트 노드를 B의 부모 노드로 설정한다.
• 2. 모든 Union 연산을 처리할 때까지 1번 반복
• 처음에는 루트 노드가 자기자신이다.

• 더 큰 루트 노드가 작은 루트 노드를 루트노드로 갖는 것이 관행이다.

• 연산이 끝나면 연결성을 통해 집합의 형태를 확인할 수 있게된다.

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
    
for i in range(e):
	a, b = map(int, input().split())
    union_parent(parent, a, b)

• (find_parent) 루트 노드를 찾을 때 부모 테이블을 확인하면서 거슬러 올라가야하는 문제가 있다.

• 편향된 연산을 하는 경우 비효율적인 연산이 발생한다. (find_parent)

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

• 경로 압축 방법으로 최적화한다.

• find 함수를 재귀적으로 호출한 뒤 부모 테이블 값을 바로 갱신한다.
  • find 함수 호출 뒤 해당 노드의 루트 노드가 바로 부모노드가된다.

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

• 무방향 그래프내에서 사이클 판별할 때 사용할 수 있다.
  • 방향 그래프는 DFS를 이용해 판별
• 1. 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인
  • 루트 노드가 서로 다르면 Union
  • 루트 노드가 서로 다르면 Cycle 발생한 것
• 2. 그래프에 포함되어있는 모든 간선에 대해 1번 반복

신장 트리

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

최소 신장 트리

• 최소한의 비용으로 구성되는 신장 트리를 찾을 때
• 두 도시 사이 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우

크루스칼 알고리즘

• 대표적인 최소 신장 트리 알고리즘
• 그리디 알고리즘으로 분류
• 1. 간선 데이터를 비용에 따라 오름차순 정렬
• 2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
  • 사이클 발생하지 않을 시 최소 신장 트리 포함
  • 사이클 발생 시 최소 신장트리에 포함 시키지 않는다.
• 3. 모든 간선에 대해 2번 반복
• 최소 신장 트리에 포함되어있는 간선의 비용만 더하면 그 값이 최종 비용에 해당한다.

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

def union_praent(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())

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
    # 사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent, a) != find_parent(parent, b):
    	union_parent(parent, a, b)
        result += cost

• O(ElogE)
  • 간선을 정렬하는 부분에서 가장 많은 시간이 수행된다.
  • E개 데이터 정렬하기 위한 시간 복잡도다.

위상 정렬

• 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
  • 선수과목 고려한 학습 순서 설정 등

• 자료구조 -> 알고리즘 -> 고급알고리즘
• 진입 차수(Indegree) : 특정 노드로 들어오는 간선 개수
• 진출 차수(Outdegree) : 특정 노드에서 나가는 간선 개수

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

• 위상 정렬을 하려면, 사이클이 없는 방향그래프 (DAG) 이어야한다.
  • Direct Acyclic Graph
• 위상 정렬에는 여러가지 답이 존재할 수 있다.
  • 큐에 새롭게 들어가는 원소가 2개 이상인 경우
• 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재한다고 판단할 수 있다.
• 스택을 활용한 DFS를 이용해도 위상 정렬 수행할 수 있다.

from collections import deque

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

graph = [[] for i in range(v+1)]

for _ in range(e):
	a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1
    
def topology_sort():
	result = []
    q = deque()
    
    for i in range(1, v+1):
    	if indegree[i] == 0:
        	q.append(i)
            
	while q:
    	now = q.popleft()
        result.append(now) # 큐에서 원소를 꺼낼때마다 결과에 저장
        
        for i in graph[now]:
        	indegree[i] -= 1
            if indegree[i] == 0:
            	q.append(i)
		
	for i in result:
    	print(i, end=' ')

topology_srot()

• O(V+E)
  • 차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거