기타 그래프 이론 정리

이코테 기타 그래프 이론 참고

서로소 집합 자료구조

기본 아이디어

주요 연산
1) Union : 두개의 서로소 집합을 하나의 집합으로 합침
2) Find : 부모 노드 찾기

코드

"""
1) 기본적인 구현 방식
-> 찾기 함수가 비효율적으로 동작 가능 : O(V)

ex. union(4, 5) -> union(3, 4) -> union(2, 3) -> union(1, 2)
cur_node: 1 2 3 4 5
parent :  1 1 2 3 4

find(5): 5 -> 4 -> 3 -> 2 -> 1
"""


def find_parentX(p, x):
    # 자기 자신을 찾을 때까지 거슬러 올라가기
    if p[x] != x:
        return find_parentX(p, p[x])
    return x


"""
2) find_parent 최적화 -> 경로 압축
- parent 테이블 값이 root 노드로 기입

cur_node: 1 2 3 4 5
parent :  1 1 1 1 1
"""


def find_parent(p, x):
    # 루트 노드로 설정
    if p[x] != x:
        p[x] = find_parent(p, p[x])
    return p[x]


# 두 노드가 속한 집합 합치기 -> 노드 1, 2는 동일한 부모를 가지게 됨
def union_parent(p, n1, n2):
    p1 = find_parent(p, n1)
    p2 = find_parent(p, n2)
    if p1 < p2:  # 번호가 더 작은 쪽을 부모로 설정하기
        p[n2] = p1
    else:
        p[n1] = p2


v, e = map(int, input().split())
parent = [i for i in range(v + 1)]  # 자기자신을 부모로 초기화

# 주어진 간선 정보에 대해 union 연산 수행
for _ in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

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

무방향 그래프 사이클 판별

기본 아이디어

간선 정보 확인 -> 두 노드의 루트 노드 확인하기
1) r(a) != r(b) -> union
2) r(a) == r(b) -> 사이클 발생 !!

코드

"""
** 사이클 여부 판별 알고리즘

간선 정보 1, 2에 대해 :
- 부모1 == 부모2 -> 같은 집합에 속함, 즉 사이클 존재
- 부모1 != 부모2 -> 합치기
"""


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


# 합치기 
def union_parent(p, x1, x2):
	x1 = find_parent(p, x1)
    x2 = find_parent(p, x2)
    
    if x1 < x2:  # 번호가 더 작은 쪽을 부모로 설정하기
        p[x2] = x1
    else:
        p[x1] = x2


v, e = map(int, input().split())
parent = [i for i in range(v + 1)]  # 자기자신을 부모로 초기화

# 주어진 간선 정보에 대해 연결 지으면서 사이클 여부 판별
is_cycle = False
for _ in range(e):
    a, b = map(int, input().split())

    p1 = find_parent(parent, a)
    p2 = find_parent(parent, b)
    if p1 == p2:  # 같은 집합에 속함
        is_cycle = True
        break
    else:  # 사이클 발생하지 않으면 Union 수행
        union_parent(parent, p1, p2)

print("사이클 발생") if is_cycle else print("사이클 없음")

크루스칼 알고리즘

✔️ 신장 트리 : 모든 노드를 포함하면서, 사이클이 존재하지 않는 부분 그래프

✔️ 최소 신장 트리 만들기 : Kruskal 알고리즘

• 신장 트리 중에서 최소 비용으로 만들 수 있는 신장트리 찾기
• 그리디 기반

기본 아이디어

1) 모든 간선에 대해 비용 기준으로 오름차순 정렬
2) 간선 정보 하나씩 돌면서, 사이클이 발생하는지 확인
   - 발생하지 않으면 신장 트리에 포함시키기

코드

"""
** 최소한의 비용으로 구성되는 신장 트리(= MST, Minimum Spanning Tree) -> 그리디

- 간선 데이터를 비용에 따라 오름차순 정렬
- 간선을 확인하며 사이클이 발생하지 않는 경우, MST에 포함
"""


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


# 합치기
def union_parent(p, x1, x2):
	x1 = find_parent(p, x1)
    x2 = find_parent(p, x2)
    
    if x1 < x2:  # 번호가 더 작은 쪽을 부모로 설정하기
        p[x2] = x1
    else:
        p[x1] = x2


v, e = map(int, input().split())
parent = [i for i in range(v + 1)]  # 자기자신을 부모로 초기화

# 간선 정보 입력, 비용에 따라 오름차순 정렬
edges = []
for _ in range(e):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))

edges.sort()

# kruskal 수행
total_cost = 0
for c, a, b in edges:
    p1 = find_parent(parent, a)
    p2 = find_parent(parent, b)

    if p1 != p2:  # 사이클이 없는 경우, MST 포함
        union_parent(parent, p1, p2)
        total_cost += c

print(total_cost)

위상정렬

기본 아이디어

순서가 정해져 있는 일련의 작업을(방향 그래프) 차례대로 수행해야 할 때 사용하는 알고리즘

- 핵심: 진입 차수가 0인 노드를 큐에 넣기

코드

from collections import deque

# input
v, e = map(int, input().split())
indegree = [0] * (v + 1)
graph = [[] for _ in range(v + 1)]
for _ in range(e):
    a, b = map(int, input().split())
    indegree[b] += 1
    graph[a].append(b)

res = []

# topological sort
queue = deque([])  # 진입 차수 == 0인 노드만 가진 큐
for i in range(1, v + 1):
    if indegree[i] == 0:
        queue.append(i)

while queue:
    cur = queue.popleft()
    res.append(cur)

    for nxt in graph[cur]:
        indegree[nxt] -= 1
        if indegree[nxt] == 0:
            queue.append(nxt)

print(*res)

왜 진입 차수가 0인 애들만 큐에 넣을까? 생각해보면 꽤 직관적이다.
현 시점에서 가장 먼저 갈 수 있는 노드라는 점이 보장되기 때문이다.