신장트리와 Prim·Kruskal

여러 건물을 모두 연결하는 케이블 비용을 줄일 때 특정 출발점의 이동거리만 줄이면 안 됩니다. 가중치 그래프와 트리를 바탕으로 최소 신장트리 MST의 목표를 이해합니다.

목표는 모든 정점을 연결하는 간선 합

연결된 무방향 그래프의 신장트리는 모든 정점을 포함하는 부분그래프인 트리입니다. MST는 이 트리들의 간선 가중치 합이 최소인 것입니다. 음수 가중치도 허용하며 같은 최소 비용을 갖는 서로 다른 최적 트리가 여러 개 있을 수 있습니다. 비연결 그래프는 전체 신장트리가 없고 성분별 최소 신장숲을 구할 수 있습니다.

삼각형 AB=2,BC=2,AC=3에서 MST는 AB,BC로 합 4입니다. 하지만 A→C 최단경로는 직접 AC로 비용 3입니다. MST에서 A→C 길이가 4라는 사실은 MST가 틀렸다는 뜻이 아닙니다. 목적 함수가 다릅니다.

Prim은 한 연결된 트리를 키운다

AB=1,AC=4,BC=2,BD=5,CD=3인 그래프에서 A로 시작합니다. 현재 트리와 바깥 정점을 잇는 간선 중 최소를 골라 AB=1, 다음 BC=2, 다음 CD=3을 더해 합 6입니다. 트리 안의 두 정점을 잇는 간선은 새 정점을 추가하지 않고 사이클을 만들기 때문에 후보에서 제외합니다. D까지 도달하는 길이가 아니라 추가 간선 하나의 무게로 비교한다는 점이 Dijkstra와 다릅니다.

Kruskal은 여러 연결 성분을 합친다

모든 간선을 무게순으로 정렬하여 1(AB),2(BC),3(CD),4(AC),5(BD) 순으로 검사합니다. 서로 다른 성분을 잇는 간선이면 선택하고 같은 성분이면 사이클을 만들므로 거절합니다. 앞의 세 간선에서 정점 4개가 연결되어 3개 간선의 트리가 됩니다.

def kruskal(vertices, edges):
    parent = {v: v for v in vertices}
    def find(v):
        while parent[v] != v:
            parent[v] = parent[parent[v]]
            v = parent[v]
        return v
    chosen = []
    for weight, a, b in sorted(edges):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            chosen.append((weight,a,b))
    return chosen

edges = [(1,'A','B'),(4,'A','C'),(2,'B','C'),(5,'B','D'),(3,'C','D')]
chosen = kruskal('ABCD', edges)
print(chosen)                 # [(1,'A','B'), (2,'B','C'), (3,'C','D')]
print(sum(w for w,_,_ in chosen))  # 6

입력은 무방향 그래프이며 간선의 두 끝점은 vertices에 있어야 합니다. 코드는 연결이 끊기면 숲을 반환합니다. 트리를 요구한다면 선택 간선이 |V|−1개인지 확인해야 합니다. Python 표준 정렬과 사전만 쓰며, 위 작은 예제는 동점 이름도 문자열로 비교합니다.

왜 최소 간선을 골라도 되는가

트리를 두 부분으로 가르는 절단을 생각합니다. 그 절단을 잇는 최소 무게 간선 e는 어떤 MST에 포함시킬 수 있습니다. 기존 MST에 e가 없다면 e를 추가해 생긴 사이클에서 같은 절단을 넘는 다른 간선 f를 빼면 됩니다. w(e)≤w(f)라 총비용은 늘지 않고 연결도 유지됩니다. 이 교환 논증이 두 알고리즘의 선택을 뒷받침합니다. '매번 싸게 고르면 된다'라는 직관만으로 모든 최적화에 탐욕법이 성립하는 것은 아닙니다.

스스로 풀어보기

문제 1. 위 그래프에서 AC를 포함하는 신장트리는 최적일 수 없다는 것을 보이세요.

힌트: 트리에서 AC를 제거하면 두 성분으로 나뉩니다. A에서 B를 거쳐 C로 가는 경로가 그 경계를 어떻게 지나는지 봅니다.

풀이: AC=4를 포함하는 임의의 신장트리 T를 잡습니다. AC를 제거하면 A가 속한 성분과 C가 속한 성분 두 개가 생깁니다. 원래 그래프의 경로 A-B-C는 A에서 C로 가므로 AB 또는 BC 중 하나가 반드시 두 성분 사이를 가로지릅니다. 그 간선은 T에서 AC를 뺀 숲 안에 있을 수 없습니다. 숲에 그 간선을 더하면 모든 정점이 다시 연결되고 간선 수는 그대로여서 새 신장트리입니다. AB=1과 BC=2 모두 AC=4보다 작으므로 비용이 엄격히 내려갑니다. 따라서 AC를 포함한 어떤 T도 MST일 수 없습니다. 이 논증은 AC+BD+CD처럼 AB와 BC를 모두 빼둔 경우에도 적용됩니다.

문제 2. 정점 5개 입력에서 Kruskal이 3개 간선을 선택했다면 전체 MST를 얻었다고 할 수 있나요?

풀이: 트리는 4개 간선이 필요하므로 아닙니다. 위 코드가 만든 비순환 결과는 5−3=2개 성분의 숲입니다. 원래 그래프가 비연결인지 입력 누락인지 확인합니다.

추적 중에는 비용과 함께 연결 성분을 적으세요. 빈도에 맞춰 트리를 설계하는 선택 심화 허프만에서 다른 탐욕 선택을 살펴봅니다.