[알고리즘] 9. 기타 그래프 이론

Index

1. 서로소 집합 자료구조

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

3. 최소 신장 트리(크루스칼 알고리즘)

4. 위상 정렬

5. 추천 문제

6. 참고자료

---

1. 서로소 집합 자료구조

Disjoint Sets

- 공통 원소가 없는 두 집합

 

서로소 집합 자료구조(= Union Find)

- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

- 두 종류의 연산을 지원

- - Union: 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산

- - Find: 특정한 원소가 속한 집합이 어떤 집합인지

- 연결성을 통해 집합의 형태를 확인

 

(동작 과정)

1) Union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인

  - A와 B의 루크 노드 A', B'를 각각 찾기

  - A'를 B'의 부모 노드로 설정

2) 모든 합집합(Union) 연산을 처리할 때까지 1번의 과정을 반복

 

(연결성)

- 기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근 불가(부모 테이블을 계속 확인하며 거슬러 올라가야함)

 

(기본 구현)

def find_parent(parent, x):
  if parent[x] != x:
    retuurn find_parent(parent, parent[x])
  else:
    return x
    
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
    
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, a, b)

 

(개선하여 구현)

- Union 연산이 편향되게 이루어지는 경우 Find 함수가 비효율적으로 동작(최악: O(V)

- Find 함수 최적화하기 위한 방법으로 Path Compression을 이용(Find 함수를 재귀적으로 호출한 뒤 부모 테이블 값을 바로 갱신)

- 모든 Union 함수를 처리한 후 각 원소에 대하여 Find 함수를 수행하면 시간 복잡도가 개선

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

 

2. 서로소 집합을 위한 사이클 판별법

사이클 판별

- 무방향 그래프 내에서의 사이클 반별시 서로소 집합을 사용 가능

- 방향 그래프에서 사이클 여부는 DFS를 이용하여 판별

 

(서로소 집합으로 사이클 판별 알고리즘)

1) 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인

- 루트 노드가 서로 다르다면 두 노드에 대하여 Union 연산을 수행

- 루트 노드가 서로 같다면 Cycle이 발생한 것

2) 그래프에 포함되어 있는 모든 간선에 대하여 1번을 반복

def find_parent(parent, x)
    
def union(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, a, b)
    
if cycle:
  print("Cycle")
else:
  print("No Cycle")

 

3.  최소 신장 트리(크루스칼  알고리즘)

신장 트리

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

- 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건

 

최소 신장 트리

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

 

크루스칼 알고리즘

- 그리디 알고리즘으로 분류되는 최소 신장 트리

- 간선의 개수가 E개일 때, O(ElogE)

 

(동작 과정)

1) 간선 데이터를 비용에 따라 오름차순으로 정렬

2) 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인

- 사이클이 발생하지 않는 경우 최소 신장 트리에 포함

- 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음

3) 모든 간선에 대하여 2번 반복

 

def find_parent(parent, x)
    
def union(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
  if find_parent(parent, 1) != find_parent(parent, b):
    union(parent, a, b)
    result += cost

print(cost)

 

4.  위상 정렬

위상 정렬

- 사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

- 여러가지 답이 존재 할 수 있음

- 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재

- DFS를 이용하여 위상 정렬 수행 가능

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

 

집입 차수 / 진출 차수

- 집입 차수(Indegree): 특정한 노드로 들어오는 간선의 개수

- 진출 차수(Outdegree): 특정한 노드에서 나가는 간선의 개수

 

(큐를 이용한 동작 과정)

1) 진입 차수가 0인 모든 노드를 큐에 넣음

2) 큐가 빌 때까지 다음 과정을 반복

- 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거

- 새롭게 진입차수가 0이 된 노드를 큐에 넣음

=> 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 동일

 

from collections import deque

v, e = map(int, input().split())
indegree =

 

5. 추천 문제

크루스칼 알고리즘

- 섬 연결하기(https://school.programmers.co.kr/learn/courses/30/lessons/42861)

- 네크워크 연결(https://www.acmicpc.net/problem/1922)

 

위상 정렬

- 순위(https://school.programmers.co.kr/learn/courses/30/lessons/49191)

- 동굴 탐험(https://school.programmers.co.kr/learn/courses/30/lessons/67260)

- 줄 세우기(https://www.acmicpc.net/problem/2252)

- 최종 순위(https://www.acmicpc.net/problem/3665)

- 문제집(https://www.acmicpc.net/problem/1766)

---

참고 자료

[Youtube: 동빈나의 이코데 2021(기타 그래프 이론)] https://www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=9