[알고리즘] ✨ 그래프 이론: 크루스칼 알고리즘 (Kruskal Algorithm), 위상 정렬(Topology Sort)

본 포스팅은 이것이 취업을 위한 코딩테스트다 - 나동빈 책을 통해 공부한 내용을 토대로 작성하였습니다.

크루스칼 알고리즘 (Kruskal Algorithm)

크루스칼 알고리즘은 대표적인 '최소 신장 트리(MST, Minimum Spanning Tree)' 알고리즘 중 하나이다

✋ 신장 트리

• 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

신장트리가 왜 필요할까? 우리는 다양한 문제 상황에서 가능한 한 최소한의 비용으로 신장트리를 찾아야 할 때가 있다.

ex) N개의 도시가 있을 때 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우, 최소한의 비용으로 모든 도시를 '연결'하고자 할 때!

✨ 크루스칼 알고리즘

• 크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다.
• 그리디 알고리즘으로 분류됨
• 최종적으로 신장 트리에 포함되는 간선의 개수: 노드개수 - 1

✨ 구현

가장 거리가 짧은 간선부터 차례대로 집합에 추가

1️⃣ 모든 간선을 비용에 따라 오름차순 정렬

2️⃣ 가장 거리가 짧은 간선부터 하나씩 확인하여 현재의 간선이 사이클을 발생시키는지 확인

1) 사이클 X → 최소 신장 트리에 포함시킴

2) 사이클 O → 최소 신장 트리에 포함 x

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

✨ 소스코드

    # 특정 원소가 속한 집합 찾기
    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

    # 노드의 개수와 간선(union)의 개수 입력받기
    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)

위상 정렬(Topology Sort)

✋ 위상 정렬

위상 정렬이란 지금까지의 정렬은 '수'를 정렬해오던 것이었다면 위상 정렬은 '그래프'를 정렬하는 것이다. 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'

😃 결국 작업의 순서가 정해져 있을 때 작업을 정확하게 정렬해주는 알고리즘

✨ 위상 정렬의 조건

DAG(Directed Acyclic Graph) 방향성 비순환 그래프이어야 한다. (방향성은 있으면서 사이클은 없는 그래프)

✨ 위상정렬 알고리즘

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

✨ 소스코드

from collections import deque

# Vertex, Edge 입력 받기
v, e = map(int, input().split())
# 모든 노드에 대한 indegree 0으로 초기화
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)  # A -> B 로 이동 가능
    indegree[b] += 1  # 진입 차수 올려주기


def topology_sort():
    result = []
    q = deque()
    
    # 처음 시작할 때 진입차수가 0인 노드 큐에 삽입
    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)

    # 큐가 빌 때까지 반복
    while q:
        # 큐에서 원소 꺼내기
        now = q.popleft()
        result.append(now)
        # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
        for i in graph[now]:
            indegree[i] -= 1
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
                q.append(i)

    for i in result:
        print(i, end=' ')

topology_sort()

✨ 시간 복잡도

시간 복잡도는 O(V+E)이다. 위상 정렬을 수행할 때는 차례대로 모든 노드를 확인하면서,
해당 노드에서 출발하는 간선을 차례대로 제거

결과적으로 노드와 간선을 모두 확인하기 때문 O(V+E)의 시간 소요