초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
마을 여섯 곳을 도로로 이어 어느 마을에서든 다른 모든 마을로 갈 수 있게 하려 합니다. 도로를 놓을 수 있는 구간마다 공사비가 다를 때, 합을 가장 작게 하려면 어느 구간을 골라야 할까요?
아직 고른 도로가 없습니다.
간선 위 숫자를 눌러 도로를 골라 봅시다.
고른 간선에 사이클이 있으면 그중 하나를 빼도 모두 이어져 있습니다. 그러니 가장 싼 답에는 사이클이 없습니다. 사이클 없이 모든 정점을 잇는 간선 묶음을 스패닝 트리(spanning tree)라 합니다. 정점이 V개면 간선은 늘 V − 1개입니다. 따로 떨어진 무리 V개에서 시작해, 사이클을 만들지 않는 간선을 하나 놓을 때마다 두 무리가 하나로 합쳐지기 때문입니다. 그중 가중치 합이 가장 작은 것이 최소 스패닝 트리(minimum spanning tree, MST)입니다.
그리디로 고를 수 있습니다.
이것이 크루스칼 알고리즘(Kruskal’s algorithm)입니다.
간선을 가중치가 작은 순으로 줄 세웠습니다.
줄에서 하이라이트된 칸이 지금 보는 간선입니다.
간선이 사이클을 만드는지는 두 끝이 이미 이어져 있는지와 같습니다. 이것은 유니온 파인드로 두 정점이 같은 무리인지 보면 바로 압니다. 그래서 간선을 줄 세우는 데 가장 오래 걸려 O(E log E)입니다. 아래 코드는 간선을 미리 가중치 순으로 적어 두고, find로 두 끝의 대표를 찾아 다르면 고르고 합칩니다.
출력 없음재생하며 chosen에 간선이 쌓이는 모습을 봅시다.
크루스칼 알고리즘이 앞서 고른 간선은 모두 있지만 이번에 고른 e는 없는 최소 스패닝 트리 T가 있다고 합시다. T에 e를 더하면 사이클이 생깁니다. 앞서 고른 간선과 e만으로는 사이클이 없으니, 이 사이클에는 앞서 고른 간선이 아닌 간선 f가 있습니다. f와 앞서 고른 간선은 모두 T에 있으니 사이클을 만들지 않습니다. 그러니 f가 e보다 쌌다면 크루스칼 알고리즘이 e보다 먼저 f를 골랐을 것이고, f는 e보다 싸지 않습니다. T에서 f를 빼고 e를 넣으면 다시 스패닝 트리이고 합은 늘지 않습니다. 그리디 글의 회의실 배정처럼 이 바꿔치기를 되풀이하면, 크루스칼 알고리즘이 고른 간선이 최소 스패닝 트리입니다.
시작 정점 하나에서 출발해, 지금 트리와 바깥을 잇는 가장 싼 간선을 하나씩 더해 가는 프림 알고리즘(Prim’s algorithm)도 있습니다. 다익스트라 알고리즘과 모양이 닮았습니다.
이번 파트에서는 이어진 것들을 그래프로 담고, 정점을 빠짐없이 둘러보고, 조건을 지키는 순서와 가장 짧은 길, 가장 싸게 잇는 간선을 찾았습니다. 지금까지는 프로그램 하나가 컴퓨터를 혼자 쓴다고 보았습니다. 하지만 실제 컴퓨터에서는 브라우저와 메신저, 음악 앱이 CPU 하나를 함께 씁니다. 그래서 다음 파트에서는 CPU 하나를 여러 프로그램이 나눠 쓰게 하는 운영체제를 다룹니다. 첫 글은 인터럽트입니다.
정점 A부터 E까지 다섯 개와 아래 간선 일곱 개로 이루어진 무방향 그래프가 있습니다. 가중치 합이 가장 작은 스패닝 트리는 모두 몇 가지일까요? 숫자로 답하세요.
가중치 1: A–B, B–C, A–C 가중치 2: C–D, C–E, D–E, B–D