크루스칼 알고리즘

froajnzd·2024년 2월 17일

algorithm

목록 보기

11/11

크루스칼 알고리즘 (Kruskal Algorithm)
최소 비용 신장 부분 트리(MST)를 찾는 알고리즘이다
=>가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘
예로, 여러 개의 도시가 있을 때 각 도시를 도로로 연결하고자 하면서 비용을 최소한으로 할 때 적용

최소 비용 신장 트리를 찾기 위해 한 가장 비용이 적은 간선에서 출발하여 사이클(cycle)이 생기지 않도록 그 다음으로 작은 간선을 찾아 이어주는 과정을 반복해 구한다.

Kruskal Algorithm의 특징
그리디 알고리즘의 일종이다
즉, 그래프 간선들을 가중치의 오름차순으로 정렬해 놓은 뒤, 사이클을 형성하지 않는 선에서 정렬된 순서대로 간선을 선택한다.

시간복잡도
변의 개수를 $E$ , 꼭지점의 개수를 $V$ 라 했을 때 $O(ElogV)$

용어 정리
노드 = 정점 = 도시
간선 = 거리 = 비용

트리(Tree) : 사이클이 존재하지 않는 Graph

신장 트리(Spanning Tree) : (1) 모든 정점을 포함하고, (2) 정점 간 서로 연결이 되는 Tree
- 정점의 갯수가 n개일 때, 간선이 n-1개

최소 신장 트리(Minimum Spanning Tree) : 가중치의 합이 최소가 되는 Spanning Tree

📕 Kruskal Algorithm을 사용해야하는 문제의 조건

간선에 가중치가 있는 그래프

📝 Kruskal Algorithm을 사용하는 문제의 예

여러 개의 네트워크 지점들이 있는데, 모든 지점들을 유선으로 연결하되 연결선의 총 길이가 최소가 되야 하는 문제
도시들을 모두 연결하되, 연결하는 도로의 길이 합이 최소가 되야 하는 문제

🎁 구현 방법

동작 방식
1. 그래프의 각 꼭짓점이 각각 하나의 나무(자료구조의 tree)가 되도록 하는 숲 F을 만든다.
2. 모든 변을 원소로 갖는 집합 S를 만든다.
3. S가 비어있지 않는 동안
1. 가장 작은 가중치의 변을 S에서 하나 빼낸다.
2. 그 변이 어떤 두 개의 나무를 연결한다면 두 나무를 연결하여 하나의 나무로 만든다.
3. 그렇지 않다면(사이클이 형성된다면) 그 변은 버린다.

알고리즘이 종료됐을 때 숲 $F$ 는 하나의 최소 비용 신장 부분 그래프만을 가지게 된다.

Cycle 판단 방법
Union&Find 자료구조를 사용하여 cycle 여부를 판단한다

Union&Find
Disjoint Set(서로소 집합)을 표현하는 자료구조
서로 다른 두 집합을 병합하는 Union 연산, 집합 원소가 어떤 집합에 속해있는지 찾는 Find 연산을 지원한다

[TODO] 나중에 이 자료구조에 대해서도 글을 써야겠다.

parent 배열을 만들어 parent 값이 같다면, 같은 트리에 있다고 판단한다

parent 배열은 각 정점의 root node(부모)를 표현한 배열
초기에는 자기 자신이 루트 노드가 되게 초기화 되어 있는 상태 (parent[i] = i)

두 노드가 하나의 트리로 합쳐진다면 Union연산으로 합친다.(parent를 같게 만든다)

의사 코드

 1  function Kruskal(G)
 2    for each vertex v in G do
 3      Define an elementary cluster C(v) ← {v}.
 4    Initialize a priority queue Q to contain all edges in G, using the weights as keys.
 5    Define a tree T ← Ø       //T will ultimately contain the edges of the MST
 6     // n is total number of vertices
 7    while T has fewer than n-1 edge

🏃‍ 예시 문제 1

<BAEKJOON: 실버 4> 상근이의 여행

해답

크루스칼 알고리즘을 사용하지는 않지만 MST의 기본 개념을 사용하였다
답은 DFS를 이용하여 풀이함.

import sys
input = sys.stdin.readline

def dfs(origin, ride):
    for dest in airplane[origin]:
        if not visited[dest]:
            visited[dest] = True
            ride = dfs(dest, ride+1)
    return ride

T = int(input())
for _ in range(T):
    N, M = map(int, input().strip().split())
    airplane = [[] for i in range(N+1)]
    visited = [False] * (N+1)
    for i in range(M):
        a, b = map(int, input().strip().split())
        airplane[a].append(b)
        airplane[b].append(a)
    # 방문하지 않은 국가(0)라면 방문해야함
    # 이미 방문한 국가라면 비행기 종류를 늘리지 않아도 됨
    # dfs로 가보지 않은 국가만 간다
    visited[1] = True
    print(dfs(1, 0))

🏃‍ 예시 문제 2

<BAEKJOON: 골드 4> 전력난

해답

크루스칼 어렵다... union-find도 먼저 이해해야해서 더 어려웠던 듯 하다.
여기서 알게되었던 점은 road(경로)를 다 탐색해봐도 된다는 점.

import sys
import heapq
input = sys.stdin.readline


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

def unionParent(parent, a, b):
    a = findParent(parent, a)
    b = findParent(parent, b)
    if a > b:
        parent[a] = b
    else:
        parent[b] = a


while True:
    m, n = map(int, input().strip().split())
    if m + n == 0:
        break
    road = []
    allCost = 0
    for _ in range(n):
        x, y, z = map(int, input().strip().split())
        allCost += z
        heapq.heappush(road, (z, x, y))

    parent = []
    for i in range(m):
        parent.append(i) # 처음에는 자기자신을 부모로 하고있음

    # kruskal: heapq로 전력이 작은 것부터 pop해서 MST가 만들어진다면 끝
    # allCost에서 MST가 된 부분 Tree의 전력 합을 빼면 답이 됨
    sum = 0
    while road:
        cost, x, y = heapq.heappop(road)

        # 같은 tree가 아니면 union하고 내 mst에 추가하기
        if findParent(parent, x) != findParent(parent, y):
            unionParent(parent, x, y)
            sum += cost

    print(allCost - sum)