0. 글의 목적

알고리즘을 잊은 미래의 나를 이해시키기 위함

1. 사이클 판별

핵심: 사이클이 존재한다? --> 부모 노드가 같은 노드끼리 합집합 연산을 할 때 발생한다.
사용이유: 주어진 무방향 그래프의 사이클 존재여부를 판단하기 위함

1.1 합집합 연산

핵심: 두 노드를 합친다.

원리: 두 노드를 합치고 부모 노드를 통일한다.

코드:

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

1.2 부모 찾기 연산

핵심: 해당 노드의 부모 노드를 하나씩 거슬러 올라가며 찾는다.

원리: recursion 사용

코드:

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

1.3 사이클 판별

원리: 두 노드를 합치기 전에 부모노드를 확인한다. 부모노드가 같다면 사이클이 발생한다.

코드:

if find_parent(parent, a)==find_parent(parent, b):
	print('사이클이 발생합니다.')

2. 신장 트리

개념: 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

2.1 최소 신장 트리

개념: 최소한의 비용으로 구성되는 신장 트리

최소 신장 트리 구하는 법: 크루스칼 알고리즘

원리:
(1) 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
(2) 간선을 하나씩 확인하면서 현재의 간선이 사이클을 발생시키는지 확인한다.
(2)-1 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
(2)-2 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
(3) 모든 간선에 대하여 2번의 과정을 반복한다.

코드:

# edges: [ (cost, a, b), .... ] (간선비용, a노드, b노드)로 구성된 리스트
# result: 최소 간선 비용을 저장할 변수
result=0 
edges.sort()
for edge in edges:
	cost, a, b = edge
    if find_parent(a)!=find_parent(b):
    	union_parent(a,b)
        result+=cost
print(result)

시간복잡도: O(NlogN), 간선을 정렬하는데 시간이 가장 오래걸림

3. 위상 정렬

개념: 사이클이 없는 방향 그래프의 모든 노드를 방향성에 맞게 순서대로 나열하는 방법

특징:
(1) 사이클이 없는 방향 그래프에서만 수행가능
(2) 여러가지 답이 존재할 수 있다. 한 단계에서 큐에 들어가는 원소가 2개 이상인 경우가 있다면 여러가지 답이 존재한다.
(3) 모든 노드를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다. 사이클에 포함된 원소는 전부 진입 간선이 1이상 이므로 큐에 들어갈 수 없기 때문이다.
(4) 스택을 활용한 DFS를 이용하여 위상 정렬을 수행할 수 있다.

원리:
(1) 진입차수가 0인 노드를 큐에 넣는다.
(2) 큐가 빌 때까지 다음의 과정을 반복한다.
(2)-1 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
(2)-2 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
(3) 큐에 들어온 순서가 위상 정렬의 결과이다.

코드:

# indegree[]: 각 노드의 진입차수를 담고 있는 리스트
def topology_sort():
	result=[] # 위상 정렬 수행결과를 담을 리스트
    q=deque() # 큐를 효율적으로 사용하기 위해 deque를 사용
    # 진입차수가 0인 노드를 큐에 넣는다.
    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=' ')