최소 연결망 비용 계산기: 최소신장트리
최소 연결망 비용 계산기 사용법
- 입력 항목은 무향 간선: 노드1 노드2 비용·노드 수입니다.
- 노드 쌍과 연결 비용을 무향 간선으로 입력합니다. 모든 노드를 연결하는 데 필요한 간선의 총비용을 최소화합니다.
- 계산하기를 누르면 연결 비용 합·상태 결과를 확인할 수 있습니다. 아래 고정 예시와 비교할 때는 입력 조건도 같아야 합니다.
| 입력 항목 | 예시 값 | 입력 안내 |
|---|---|---|
| 무향 간선: 노드1 노드2 비용 | 1 2 4 1 3 2 2 3 1 2 4 3 3 4 8 | 한 행씩 줄바꿈, 열은 공백 또는 쉼표로 구분합니다. 표 안에서는 천 단위 쉼표를 쓰지 마세요. |
| 노드 수 | 4 | 2~100 정수 · 천 단위 쉼표 사용 가능 |
| 결과 항목 | 예시 결과 |
|---|---|
| 연결 비용 합 | 6 |
| 상태 | 최소신장트리 |
| 노드1 | 노드2 | 비용 |
|---|---|---|
| 2 | 3 | 1 |
| 1 | 3 | 2 |
| 2 | 4 | 3 |
위 표는 고정된 예시입니다. 직접 입력한 값의 결과는 입력란 아래에 표시됩니다. 실제 이용 시에는 아래 계산 방법과 적용 조건을 함께 확인하세요.
계산 방법
입력 자료를 다음 방식으로 계산합니다. 최소신장트리
알아두세요
Kruskal 알고리즘으로 모든 노드를 최소비용으로 연결합니다. 방향이 없는 간선이며 중복 후보 간선은 허용합니다. 입력 범위 안의 모형 계산이며 실제 자료의 가정 충족 여부를 자동 판정하지 않습니다.
자주 묻는 질문
최소 연결망과 출발점 기준 최단 경로는 같은가요?
최소 연결망은 전체 간선 비용의 합이 목적입니다. 개별 출발점에서 각 지점까지의 거리를 최소화하지 않으며 연결이 끊긴 입력은 여러 연결망으로 나뉩니다.
계산 방식 참고: SciPy 최적화 방법 목록 — 관련 계산 원리 참고
입력·결과 안내 점검: · 생활 계산기