가중치가 있는 연결 그래프에서 최소 신장 트리를 구하려 합니다. Kruskal과 Prim은 다음 간선을 어떻게 고르며 그래프의 표현과 밀도에 따라 무엇이 유리한가요?

Kruskal은 전체 간선을 가중치 오름차순으로 보면서 현재 서로 다른 연결 성분을 잇는 간선을 선택하고, Prim은 하나의 시작 정점에서 출발해 현재 트리와 바깥을 잇는 가장 싼 간선을 반복 선택합니다. 둘 다 단순히 지금 보이는 최소 간선을 무조건 고르는 것이 아니라 사이클을 만들지 않거나 현재 절단을 안전하게 잇는 조건을 지킵니다. 간선 목록·정점 수·그래프 밀도에 따라 구현을 선택하겠습니다.

최적성·동점·연결성을 확인합니다

Kruskal은 간선을 정렬한 뒤 Union-Find로 양 끝 정점이 같은 성분인지 확인합니다. 다르면 선택하고 두 성분을 합치며, 같으면 사이클을 만들므로 건너뜁니다. Prim은 선택된 정점 집합과 아직 선택되지 않은 집합 사이의 경계를 우선순위 큐에 넣고 최소 후보를 꺼냅니다. 이미 트리에 들어온 정점을 가리키는 오래된 후보는 건너뛰거나 key를 갱신합니다. 이 차이를 성분 병합(component merging)과 경계 확장(frontier expansion)으로 정리할 수 있습니다.

Kruskal은 간선 정렬 비용이 중심이고, 희소 그래프의 간선 목록에서 구현이 단순합니다. Prim은 인접 리스트와 힙으로 구현하면 경계 간선을 중심으로 처리하고, 정점 수가 작고 행렬이 조밀하면 매번 모든 후보를 선형 탐색하는 단순 구현도 경쟁력이 있습니다. 그래프가 연결되지 않았으면 하나의 MST가 아니라 각 성분의 최소 신장 숲이 나오므로, 입력을 허용할지 오류로 처리할지 정합니다.

최적성의 기준과 동점을 확인합니다

어떤 컷을 가로지르는 최소 간선은 그 컷을 잇는 어떤 MST에 포함될 수 있다는 cut property가 두 알고리즘의 안전한 선택 근거입니다. 같은 가중치 간선이 많으면 서로 다른 간선 집합이지만 총비용이 같은 MST가 여러 개 존재할 수 있습니다. 따라서 테스트에서 간선 목록 하나를 고정 정답으로 삼지 않고 연결성·간선 수 V-1·사이클 부재·총비용을 기준으로 비교하겠습니다.

입력 표현을 바꿔 같은 그래프를 만들고 두 알고리즘 결과의 총비용을 작은 완전 탐색 결과와 비교하겠습니다. 간선이 계속 추가되면 매번 처음부터 계산하지 않고 동적 MST 구조나 변경량에 따른 재계산을 검토하지만, 단순 Union-Find는 이미 선택한 MST에서 임의 삭제를 처리하지 못합니다. 메모리·정렬 비용·우선순위 큐 갱신 비용까지 포함해 선택하겠습니다.

Kruskal의 Union-Find는 선택 간선의 연결 성분만 요약하고 실제 트리 경로를 저장하지 않습니다. Prim의 우선순위 큐에는 같은 정점의 오래된 후보가 남으므로 현재 key와 다르면 건너뛰는 lazy deletion이나 갱신 규칙이 필요합니다. Kruskal이 서로 다른 성분을 합치는 간선 V-1개를 선택했다면 모든 정점이 연결된 것이므로 종료할 수 있습니다.

음수·0 가중치도 사이클 판단은 가능하지만 비용의 의미와 정렬 방향은 문제 계약에 맞춰야 합니다. 동점 간선으로 트리 모양이 달라도 총비용과 연결성은 같을 수 있습니다. 작은 그래프의 완전 탐색 기준과 비교해 간선 수·사이클·총비용을 확인하고, 간선 추가·삭제의 재계산 비용도 별도로 측정합니다.

Prim에서 우선순위 큐에 같은 정점의 후보가 여러 개 남는 lazy deletion은 정확성을 위해 현재 최선 비용과 선택 여부를 확인해야 합니다. Kruskal에서는 정렬된 간선이 같은 비용일 때 입력 순서가 결과 모양을 결정할 수 있지만 총비용은 같을 수 있습니다. 대규모 희소 그래프에서는 간선 정렬과 Union-Find 비용을, 조밀 그래프에서는 행렬 스캔과 캐시 비용을 따로 측정하겠습니다. 간선이 온라인으로 추가되면 기존 MST가 자동으로 최적 상태를 유지하지 않으므로 새 간선이 만드는 사이클의 최대 간선과 비교하는 갱신 전략을 별도로 검토하겠습니다.

간선 가중치가 모두 서로 다르면 MST는 유일하지만 동점이 있다고 반드시 여러 MST가 생기는 것은 아닙니다. 따라서 재현 가능한 간선 목록이 필요하면 비용 뒤에 안정적인 간선 ID를 비교하겠습니다. 선택할 때의 동점 정책과 최적성 검사는 분리합니다. 음수 간선도 MST에서 허용되며 Dijkstra의 비음수 조건을 여기에 잘못 적용하지 않겠습니다.