최소 신장 연결망
무방향 연결 후보와 비용으로 전체 연결의 최소 비용 간선 또는 분리된 최소 숲을 찾으세요.
예시값이 입력되어 있습니다. 바로 확인하거나 값을 바꿔 보세요.
입력은 브라우저에서 처리합니다. 새로고침하면 예시값으로 돌아갑니다.
사용 방법과 예시
Kruskal: 비용 오름차순으로 서로 다른 연결 성분을 잇는 간선만 선택합니다.
기본 4노드 연결망은 간선 행 1,2,3을 선택해 총 비용 6, 연결 성분 1개입니다.
2~50노드·최대 200간선, 정수 비용 0~1,000,000입니다. 자기 루프는 거부하며 평행 간선은 허용합니다. 실제 시설 설계 적합성은 평가하지 않습니다. 부동소수점 결과는 최대 유효숫자 12자리로 표시합니다.
자주 묻는 질문
연결 후보가 끊어져 있으면 실패하나요?
계산은 각 성분의 최소 숲을 반환하고 성분 수를 표시합니다. 성분 수가 1보다 크면 전체 연결망이 아닙니다.
최소 신장 연결망과 최단 경로는 같은가요?
아니요. 모든 노드를 잇는 총 간선 비용을 줄입니다. 특정 출발·도착 사이 거리를 최소화하는 문제와 다릅니다.
계산 기준과 참고 자료
- SciPy: minimum spanning trees and forests
Kruskal 알고리즘과 최소 신장 트리·숲.