그래프(union-find, 크루스칼)
서로소 집합.
- 공통원소가 없는 두 집합.
이용하는 함수 두 가지.
- union - find 함수
- find 함수(root 노드를 찾는 함수)
동작과정
- union 연산을 확인해, 서로 연결된 두 노드 A, B를 확인.
-1. A와 B의 루트 노드 A', B'를 각각 찾기.
-2. A' 를 B'의 부모노드로 설정.(부모노드의 경우 수가 더 작은 거를 부모노드로 설정.) - 모든 연산을 처리 할때 까지 1번 반복.
가장 필요한 변수는. 부모노드를 나타내는 리스트가 필요.
. 루트 노드를 찾기 위해선 재귀적으로 부모를 거슬러 올라감.
def find_parent(parent, x):
if parent[x] != x:
find_parent(parent, parent[x])
return x
def union(parent, a, b):
root_a = find_parent(parent, a)
root_b = find_parent(parent, b)
if root_a < root_b:
parent[b] = root_a
else:
parent[a] = root_b
node, edge_num = map(int, input().split())
parent = [0] * (node + 1)
for i in range(len(parent)):
parent[i] = i
for i in range(edge_num):
A, B = map(int, input().split())
union(parent, A, B)
find 함수 : 현재 노드의 루트 노드를 찾아냄.
parent 리스트 : 자기 바로 위의 부모 노드를 가지고 있음.
경로 압축 기법.
find 함수에서 재귀를 이용하는 것이 시간 복잡도를 많이 잡아 먹는다.
이를 보완 하기 위해 부모 노드를 나타내는 parent 리스트를 업데이트하는 방식이다.
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return x
사이클 판별.
- 각 간선을 확인하며 두 노드의 루트 노드를 확인
-1. 루트 노드가 서로 다르면 union 연산 수행
-2. 서로 같다면 사이클이 발생. - 1번 과정을 반복.
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return x
def union(parent, a, b):
root_a = find_parent(parent, a)
root_b = find_parent(parent, b)
if root_a < root_b:
parent[b] = root_a
else:
parent[a] = root_b
node, edge_num = map(int, input().split())
parent = [0] * (node + 1)
for i in range(len(parent)):
parent[i] = i
# 다른 부분은 동일 하지만
# 아래 부분만 다르다.
# 부모 노드가 같은 경우엔 브레이크 하고 바로 나간다.
-------------------------------------------------------------------------------------------------
cycle = False
for i in range(edge_num):
A, B = map(int, input().split())
if find_parent(parent, A) == find_parent(parent, B):
cycle = True
break
else:
union(parent, A, B)
-------------------------------------------------------------------------------------------------
신장트리
신장트리란?
하나의 그래프가 모든 노드를 포함하며 사이클이 존재하지 않는 부분.
크루스칼
최소한의 비용으로 신장트리를 찾는 것.
가장 중요한 부분은 모든 간선에 대해 정렬을 수행해야 하는 것.
동작과정
- 간선 데이터를 비용에 따라 오름차순으로 정렬.
- 간선을 확인 하며 사이클을 발생시키는지 확인
-1. 사이클 X , 최소 신장 트리에 포함
-2. 사이클 O , 최소 신장 트리에 포함시키지 않는다. - 모든 간선에 대해 2번 반복.
언제나 성립하는 것으로 신장트리에 포함되는 간선의 수는 '노드의 개수 -1'이다.(당연한 소리쥬.)
ex) 노드 7개를 간선으로 연결하려면 6개의 간선이 필요하니까.
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return x
def union(parent, a, b):
root_a = find_parent(parent, a)
root_b = find_parent(parent, b)
if root_a < root_b:
parent[b] = root_a
else:
parent[a] = root_b
node, edge_num = map(int, input().split())
parent = [0] * (node + 1)
for i in range(len(parent)):
parent[i] = i
edges = []
results = 0
for i in range(edge_num):
A, B, cost = map(int, input().split())
edges.append((cost, A, B))
# 정렬을 수행.
# 루트 노드들이 다른 것의 경우 사이클이 발생하지 않는다.
# 그러한 노드들 만을 모아 결과를 출력
-------------------------------------------------------------------------------------------------
edges.sort()
for item in edges:
cost, a, b = item
if find_parent(parent, a) != find_parent(parent, b):
results += cost
union(parent, a, b)
print(results)
-------------------------------------------------------------------------------------------------
위상 정렬
일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘.(방향성을 거스르지 않도록 나열)
방향성을 가지기에 노드는 진입 차수를 가진다.
진입차수란?
특정한 노드로 들어오는 간선의 개수를 의미한다.
그래서 진입차수를 나타낼 리스트가 필요.
이를 indegree 라 부르자.
동작 과정
- 진입차수가 0인 노드를 큐에 넣는다.
- 큐가 빌 때 까지 다음의 과정을 반복한다.
-1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거.
-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재.(한번 그려서 해결 해 보도록 하자. 쿸쿠)
진입차수가 0이 안 되면 큐에 들어가지 못하는데 사이클이 존재할 경우 0이 되지 않기 떄문임.
from _collections import deque
node, edge_num = map(int, input().split())
#진입차수의 초기화가 필요하다
indegree = [0] * (node + 1)
graph = [[] for i in range(node + 1)]
for _ in range(node):
a, b = map(int, input().split())
graph[a].append(b)
indegree[b] += 1
def topology_sort():
#정렬된 값들을 담을 리스트
result = []
q = deque()
#진입차수가 0인 것을 큐에 담기.
for idx, item in enumerate(indegree):
if not item:
q.append(idx)
while q:
now = q.popleft()
result.append()
for data in graph[now]:
indegree[data] -= 1
if not indegree[data]:
q.append(data)
for i in result:
print(i, end=" ")
topology_sort()
Author And Source
이 문제에 관하여(그래프(union-find, 크루스칼)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/그래프union-find-크루스칼저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)