# 最小生成树计算器（Kruskal / Prim）

对无向加权图（1–30 条边，每行：节点1、节点2、权重）求最小生成树，双算法可选：Kruskal 按权重排序后用并查集逐边判定，记录每条边被接受/成环拒绝的完整过程；Prim 从起始节点出发每步取离开当前成分的最便宜边并展示成分生长。自环自动跳过；图不连通按业务拒绝并给出连通分量数；两种算法结果总权重必须一致（内部校验）。经典例：A-B 4、A-C 2、B-C 5、B-D 10、C-E 3、D-E 4、D-F 11、E-F 8 → MST 权重 21（A—C、C—E、A—B、D—E、E—F），B—C 成环被拒。

> 标准页面: https://elysiatools.com/zh/tools/minimum-spanning-tree

- **分类:** Math & Numbers

- **关键词:** 最小生成树, mst, 克鲁斯卡尔, 普里姆, 并查集, 贪心算法, 图, 网络设计, 生成树, 离散数学

## 概述

最小生成树计算器是一款用于无向加权图的在线分析工具，支持经典的 Kruskal 与 Prim 算法。输入节点与权重列表后，工具可逐步展示 Kruskal 算法基于并查集的选边与成环拒绝过程，或 Prim 算法从指定起始节点向外扩展连通分量的生长轨迹，并自动完成权重汇总与连通性校验。

## 输入项

- **边（每行：节点1、节点2、权重）** (textarea): One undirected edge per line: two node names (1–8 letters/digits) and a weight (negatives allowed).
- **算法** (select)
- **起始节点（仅 Prim，可选）** (text): e.g. D
- **小数位数** (number)

## 适用场景

- 学习或教授离散数学、数据结构与图论算法，需要对照 Kruskal 或 Prim 的单步推导与成环判定过程时。
- 设计低成本通信网络、布线管道或道路拓扑，需要找出覆盖所有节点且总权重最小的连通子图时。
- 验证手工计算的最小生成树总权重及边集是否正确，并排查图中是否存在不连通的分量。

## 工作原理

- 在文本框中按行输入无向边数据，每行格式为“节点1 节点2 权重”，节点支持1至8位字母或数字，权重支持负数与小数。
- 选择计算算法：Kruskal（按权重升序排序并结合并查集判定成环）或 Prim（可选择起始节点以展示成分生长过程）。
- 设置输出结果保留的小数位数，工具自动过滤自环边并校验图的连通性。
- 生成详细的执行日志、最终入选的最小生成树边集列表，以及总权重的交叉校验结果。

## 使用案例

- 高校计算机专业学生验证图论作业中的 Kruskal 排序选边与 Prim 割集扩展步骤。
- 网络规划工程师快速评估局部局域网交换机或光纤布线的最小物理连接成本。
- 算法竞赛选手用于生成样例对照数据，调试基于并查集或优先队列的最小生成树代码。

## 常见问题

### 如果输入的图不是连通图，工具会如何处理？

若图不连通，工具会中断生成树计算并提示错误，同时输出当前图包含的连通分量数量。

### Kruskal 和 Prim 算法计算出的总权重会不一样吗？

对于同一个连通图，两种算法虽然选边顺序可能不同，但最终得到的最小生成树总权重必须完全一致，工具内部会自动进行交叉比对。

### 输入的边中包含自环（如 A A 5）会被计算吗？

自环边对连通不同节点无贡献，工具在解析输入数据时会自动忽略所有自环边。

### 边的权重可以为负数或小数吗？

支持输入负数和带小数点的权重值，同时可通过参数自定义输出结果的小数显示位数。

### Prim 算法中的“起始节点”是必填项吗？

起始节点为选填项。若未填写，工具将默认选用输入数据中首先出现的节点作为起点开始生长。

## 相关工具

- [密度计算器 (ρ = m/V)](https://elysiatools.com/zh/tools/density-calculator): 由三个量中的两个求第三个，附比重与浮沉判断
- [泵 NPSH（净正吸入压头）计算与汽蚀校核](https://elysiatools.com/zh/tools/pump-npsh-calculator): 计算泵的可用净正吸入压头 NPSH_a = (p_surface - p_vapor)/(ρ·g) + H_static - h_friction（单位 m）。液面压力与蒸汽压均为绝对压力；H_static 为正表示灌注（液面高于泵），为负表示吸上（液面低于泵）。再与泵曲线给出的 NPSH_r 比较，给出裕量 margin = NPSH_a - NPSH_r 与比值 ratio = NPSH_a/NPSH_r，并判定为 safe（安全）、marginal（临界，裕量 < 0.5 m）或 cavitation likely（易发生汽蚀）。若 NPSH_r = 0，则仅输出 NPSH_a。压力支持 Pa/kPa/bar/atm/psi，长度支持 m/ft，密度支持 kg/m³/g/cm³/lb/ft³。
- [英文单词转数字](https://elysiatools.com/zh/tools/words-to-number): 把英文数字词转成阿拉伯数字。支持千/百万/十亿量级、"and"、通过 "point" 表达的小数以及连字符，并就地替换数字片段。
- [自适应 12 点隐藏水印](https://elysiatools.com/zh/tools/adaptive-12-point-hidden-watermark): 为单张图片或 ZIP 中每张支持图片，在全部、随机或指定的边缘点位添加低对比度文字水印，并按局部背景自动选择深色或浅色文字。
- [钠排泄分数 FENa 计算器（鉴别急性肾损伤）](https://elysiatools.com/zh/tools/fractional-excretion-sodium): 钠排泄分数 FENa = (尿钠×血清肌酐)/(血清钠×尿肌酐)×100%。少尿型 AKI 鉴别：<1% 提示肾前性氮质血症（容量不足、心衰、肝肾综合征等钠潴留状态）；≥1% 提示肾性损伤（常为 ATN，肾小管无法重吸收钠）；>4% 偶见于梗阻后。利尿剂会干扰结果（改用 FEUrea<35%）；造影剂/脓毒症相关 ATN 可表现为低 FENa；慢性 CKD 和糖尿可使 FENa 升高。需结合临床。不构成医疗建议。
- [Twitter / X 长推文拆分器](https://elysiatools.com/zh/tools/twitter-thread-splitter): 粘贴长文本，自动按 280 字符限制拆分成带编号的 X 线程。支持按词/句/段边界切分、自动加 1/N 编号、正确加权中日韩和全角字符、URL 按 23 字符计数，并为每条推文显示 X 风格预览卡和字数计量条。
- [空气处理机组冷/热量计算器（AHU 盘管）](https://elysiatools.com/zh/tools/ahu-capacity-calculator): 由进出风状态与干空气质量流量 ṁ_da 计算空气处理机组（AHU）盘管容量：总容量 Qt=ṁ_da·(h1−h2)，显热 Qs=ṁ_da·cp_ma·(T1−T2)（cp_ma≈1.006+1.86·W），潜热 Ql=Qt−Qs，显热比 SHR=Qs/Qt。每个状态由干球温度 T 与一种湿度输入（相对湿度 φ 或含湿量 W）描述；W 由 Magnus 饱和蒸汽压公式推算，焓 h=1.006·T+W·(2501+1.86·T)。结果带正负号，可用于冷却或加热盘管。
- [浮力计算器 (阿基米德，F = ρ·V·g)](https://elysiatools.com/zh/tools/buoyancy-calculator): 由浮力、流体密度、体积中的任意两个求第三个，并按物体密度判定漂浮/悬浮/下沉

## 示例

- [Web Python 图像处理示例](https://elysiatools.com/zh/samples/web-image-processing-python): Web Python 图像处理示例，使用 PIL/Pillow 包括读取、保存、缩放和格式转换
- [SVG示例](https://elysiatools.com/zh/samples/svg-samples): 可缩放矢量图形（SVG）示例，展示各种SVG功能和技术
- [Android Java 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-java): Android Java 图像处理示例，包括图像读取保存、缩放和格式转换
- [Android Kotlin 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-kotlin): Android Kotlin 图像处理示例，包括图像读取保存、缩放和格式转换