참고자료 : 이것이 코딩 테스트다 (나동빈 저)

1. 다양한 그래프 알고리즘

\	그래프	트리
방향성	방향 그래프 혹은 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	루트 노드가 없음	루트 노드가 존재
노드간 관계성	부모와 자식 관계 없음	부모와 자식 관계
모델의 종류	네트워크 모델	계층 모델

서로소 집합 (Disjoint Sets)

서로소 집합 자료구조 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
합집합과 찾기 연산으로 구성된다. => union-find 자료구조
서로소 집합 자료구조를 구현할 때는 트리 자료구조 이용

합집합 연산 -> 서로 연결된 두 노드 A, B 확인
1. A와 B의 루트 노드 A’, B’를 찾음
2. A’를 B’의 부모 노드로 설정
모든 합집합 연산을 처리할 때까지 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)

print('각 원소가 속한 집합: ', end = ' ')
for i in range(1, v+1):
    print(find_parent(parent, i), end=' ')

# 1 1 1 1 5 5

문제점 : find 함수의 시간복잡도는 O(V)

경로 압축 기법을 적용하여 개선한 소스코드

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)

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)

print('각 원소가 속한 집합: ', end = ' ')
for i in range(1, v+1):
    print(find_parent(parent, i), end=' ')

서로소 집합 알고리즘의 시간 복잡도

노드의 개수 V개, 최대 V-1개의 union 연산, M개의 find 연산
O(V+M(1+log_(2-M/V)V))

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

각 간선은 확인하며 두 노드의 루트 노드를 확인한다.
1. 루트 노드가 다르면 두 노드에 대해 union 연산
2. 같으면 사이클 발생
모든 간선에 대해 1번 반복

이 알고리즘은 간선에 방향성이 없는 무방향 그래프에서만 적용 가능하다.

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)

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('사이클 발생')

신장 트리 (spanning tree)

신장 트리 : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
모든 노드가 포함되고 사이클이 존재하지 않음 -> 트리의 성립 조건

크루스칼 알고리즘

대표적인 최소 신장 트리 알고리즘
최소 신장 트리 알고리즘 : 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리 알고리즘
가장 적은 비용으로 모든 노드 연결
그리디 알고리즘으로 분류

간선 데이터를 비용에 따라 오름차순 정렬
간선을 하나씩 확인하며 현재 간선이 사이클을 발생시키는지 확인
1. 발생하지 않으면 최소 신장 트리에 포함
2. 발생하면 포함시키지 않음
모든 간선에 대해 2번 반복

최종적인 신장 트리에 포함되는 간선의 개수는 노드의 개수 - 1 과 같다.
시간 복잡도 : 간선의 개수가 E개일 때, O(ElogE)

크루스칼 알고리즘 코드

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

print(result)

위상정렬

순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘
위상정렬이란, 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
진입차수 : 특정한 노드로 들어오는 간선의 개수

진입차수가 0인 노드를 큐에 넣음
큐가 빌 때까지 다음 과정 반복
1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
2. 새롭게 진입차수가 0이 된 노드를 큐에 넣음

모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것
다만 기본적으로 위상 정렬 문제에서는 사이클이 발생하지 않는다고 명시하는 경우가 더 많음
시간 복잡도 : O(V+E)

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_sort()

saetbyeol

📚 <이것이 코딩 테스트다> - 그래프 이론

1. 다양한 그래프 알고리즘

서로소 집합 (Disjoint Sets)

기본적인 서로소 집합 알고리즘 소스코드

경로 압축 기법을 적용하여 개선한 소스코드

서로소 집합 알고리즘의 시간 복잡도

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

신장 트리 (spanning tree)

크루스칼 알고리즘

크루스칼 알고리즘 코드

위상정렬