Prim 또는 Kruskal 실행 방법 01 가중 그래프를 만듭니다. 그리드 프리셋(rows 4, cols 5 — 노드 20개, 단위 간선 31개), 무작위 연결 그래프, 또는 Complete K₆를 시도하세요. 02 Prim을 고르고 Source를 설정 하거나, 소스가 필요 없는 Kruskal로 전환합니다. 03 표를 읽습니다. 총 가중치, 선택 간선, 구성 요소, 숲 여부 순서로 나오고, 아래에 선택된 간선별 가중치 행이 있습니다. 04 다른 알고리즘으로 교차 확인합니다 — 같은 그래프라면 총 가중치가 일치해야 합니다. 05 실행을 단계별로 진행합니다. Play / Prev / Next로 Prim은 커지는 경계를, Kruskal은 채택·거부 간선을 강조합니다.
예시 패널이 표시하는 값:
그래프 · 알고리즘
판독값
그리드 4 × 5, 1-1에서 Prim
총 가중치 19 ; 선택 간선 19 / 31 ; 구성 요소 1 ; 숲 여부 No
그리드 4 × 5, Kruskal
총 가중치 19 ; 선택 간선 19 / 31
무작위 연결(n 6, p 0.3, seed 20260730, 최대 가중치 9), A에서 Prim
총 가중치 16 ; 선택 A–B(3), A–C(4), C–E(2), A–D(6), D–F(1) ; 선택 간선 5 / 7
같은 그래프, Kruskal
총 가중치 16 ; 같은 다섯 간선을 가중치 순서로: D–F(1), C–E(2), A–B(3), A–C(4), A–D(6)
Complete K₆, Prim
총 가중치 5 ; 선택 간선 5 / 15 ; 간선 A–B(1), A–F(1), A–E(1), A–D(1), A–C(1)
그리드의 MST는 20개 노드에 단위 간선 19개 — 이론적 최소 — 이며 두 알고리즘 모두 도달합니다. 무작위 그래프에서는 간선 하나로 답을 손으로 확인할 수 있습니다. D–F 의 가중치가 1 로 그래프에서 가장 가벼우므로 모든 MST가 반드시 포함하며, 두 실행 모두 포함합니다.
두 목록이 다른 이유 Prim과 Kruskal은 간선을 다른 순서로 고르고, 동점일 때 서로 다른 유효한 트리를 선택할 수 있습니다. Kruskal은 모든 간선을 전역으로 정렬하므로 표가 어디서든 가장 가벼운 간선에서 시작합니다. Prim은 커지는 트리 하나의 경계만 보므로 표가 루트를 먼저 떠나는 것에서 시작합니다. 무작위 그래프에서 둘은 같은 집합 을 만듭니다 — 그곳의 최소 신장 트리는 유일합니다 — 하지만 K₆ 목록(모든 가중치 1)은 여러 완전 트리 중 하나일 뿐입니다. 가중치가 반복될 때는 간선 목록이 아니라 총 가중치와 간선 수를 비교하세요.
한계
연결되지 않은 그래프는 숲을 줍니다. 숲 여부 행이 Yes가 되고 구성 요소 수는 1보다 큽니다. 답은 최소 신장 숲, 곧 구성 요소마다 트리 하나이며 단일 트리가 아닙니다.
무향 간선만. Prim은 유향 그래프를 무향으로 취급하고 경고로 알립니다. Kruskal의 구성 요소 병합도 무향 개념입니다. 둘 다 유향 최소 수형도를 풀지 않습니다. 하지 않는 일. 루트에서의 최단 경로 계산, 대체 신장 트리 세기, 파일에서 간선 목록 가져오기를 하지 않습니다 — 루트 거리에는 최단 경로 , 구조적 계산에는 지표와 중심성 을 쓰거나 행렬을 그래프 워크벤치 에 붙여넣거나 행렬 도구 로 보내세요.
동점 처리 함정 Complete K₆에서는 모든 간선이 1 이라 모든 신장 트리가 5 입니다. Prim은 우연히 A를 중심으로 한 별 모양으로 답합니다: A–B, A–F, A–E, A–D, A–C . 이 목록은 하나의 최소 트리로 읽어야 하며 그 최소 트리로 읽으면 안 됩니다. 같은 주의가 동일 가중치 그리드에도 적용됩니다. 그리드 답 19 는 안정적이지만 어떤 19개 단위 간선이 나타나는지는 Prim과 Kruskal에서 다를 수 있으며 둘 다 여전히 정확합니다.
유용한 곳 가장 저렴한 배선 주장 확인 무작위 그래프에서 가장 무거운 두 간선 **E–F(8)**과 **B–D(7)**은 모두 제외되고 **A–D(6)**이 채택됩니다. 제안된 네트워크도 같은 방식으로 확인하세요. E–F(8)에 비용을 지불하면서 더 싼 D–F(1)을 빼둔다면 최소가 아닙니다.
컷 성질 가르치기 그리드는 컷 추론을 눈에 보이게 합니다. 모든 단위 간선은 가중치 1의 어떤 컷을 가로지르고, 두 알고리즘은 사이클을 하나도 만들지 않고 31개 중 19개를 채택합니다. 무작위 연결 그래프로 바꿔 둘 다 실행하면, 단계 재생이 Kruskal이 E–F(8)을 건너뛰는 모습(양 끝이 이미 연결됨)을 보여 줍니다.
개인정보 그래프 편집과 두 MST 실행은 브라우저에서 로컬로 실행됩니다. 아무것도 업로드되지 않습니다.
참고문헌
Wikipedia, Prim's algorithm , en.wikipedia.org (访问日期:2026-10-07)— 루트에서의 경계 성장.
Wikipedia, Kruskal's algorithm , en.wikipedia.org (访问日期:2026-10-07)— union-find를 사용한 가중치 순서.
Wikipedia, Minimum spanning tree , en.wikipedia.org (访问日期:2026-10-07)— 컷과 사이클 성질, 서로 다른 가중치에서의 유일성.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms , 4판, MIT Press, 2022, mitpress.mit.edu (访问日期:2026-10-07)— MST 알고리즘과 컷 성질.
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
Updated 2026-10-07