Kruskal算法最小生成树构建与可视化系统

资 源 简 介

本项目实现图论中经典的最小生成树Kruskal算法，通过编写M-函数格式的程序[Wt, Pp] = mintreek(n, W)来解决加权连通图的最小生成树问题。系统核心功能包括：首先对输入的带权邻接矩阵W进行解析，提取所有边的端点信息及对应权值，并自动过滤权值为inf的不可达边；接着按照边权值从小到大的顺序进行贪心策略排序；随后通过并在集逻辑判断每条边是否与已选边构成环路，逐步选择出连接所有n个顶点的n-1条最短边。除了计算核心结果，程序还集成了图形展示功能，能够根据顶点连接关系自动绘制网络图，并使用红

详 情 说 明

基于Kruskal算法的最小生成树构建与可视化系统

项目介绍

本项目是一个用于解决图论中最小生成树（Minimum Spanning Tree, MST）问题的工具，采用经典的Kruskal算法实现。系统能够接收用户定义的带权邻接矩阵，自动计算出连接所有顶点且总边权和最小的树状结构，并以图形化的方式直观展示原始网络与生成的最小生成树。

功能特性

• 贪心算法实现：严格遵循Kruskal算法逻辑，通过边权值排序和并查集判断，确保获取全局最优解。
• 数据自动预处理：自动解析邻接矩阵，过滤自环（权值为0）及不可逾越的路径（权值为inf），仅提取有效边信息。
• 防环逻辑检测：内置并查集搜索机制，在选边过程中实时判断是否形成回路，保证结果符合树的定义。
• 自动化可视化：自动计算顶点的几何分布（圆形布局），并对原始网络与生成树进行分层渲染，方便对比观察。
• 详细结果输出：在命令行窗口实时打印总权值，并列出所有选中边的起点、终点、权值及原始排序序号。

系统要求

• 运行环境：MATLAB R2016a 或更高版本。
• 依赖工具箱：无需特殊工具箱，核心功能基于标准MATLAB内置函数实现。

实现逻辑说明

系统主要由主控逻辑和核心算法函数两部分组成，其执行过程严格遵循以下步骤：

1. 参数配置阶段：设定顶点总数（n），并定义带权邻接矩阵。矩阵中的数值代表边的权重，inf表示顶点间无直接路径连接。
2. 边集提取与排序：程序遍历邻接矩阵的上三角部分以避免重复提取边。提取出的每条边包含起点、终点及权值，随后系统根据权值对所有边进行升序排列。
3. 核心计算逻辑（Kruskal算法）：

* 初始化：为每个顶点创建一个独立的集合，初始状态下每个顶点的父节点指向其自身。 * 循环迭代：按权值从小到大遍历排序后的边。 * 根节点查找：对于每条边，通过递归查找判断两个端点是否属于同一个根节点。 * 集合合并：若两端点分属不同集合（即不构成环），则将该边选入最小生成树，并合并两顶点的集合。 * 终止条件：当选中的边数达到（顶点数-1）时，计算停止，以提高算法执行效率。

1. 绘图展示阶段：

* 使用三角函数计算n个顶点在圆周上的坐标，确保布局整齐。 * 首先绘制所有原始边，以灰色虚线和浅色文字标注。 * 随后在对应位置覆盖绘制最小生成树的边，采用红色实线加粗处理。 * 最后绘制节点圆圈并标注节点编号。

关键函数与技术细节分析

• 并查集实现：在算法函数内部定义了嵌套的查找函数，利用父节点数组实时维护顶点的连通性状态。这保证了在 $O(E log E)$ 的复杂度下高效完成任务。
• 排序策略：利用排序函数返回的索引值对边矩阵进行重组，不仅实现了权值排序，还保留了边在原始逻辑中的顺序标记。
• 可视化布局：采用圆形布局算法（基于 linspace 和 cos/sin），无论顶点数量如何变化，系统都能自动生成均衡的几何分布，避免了手动设置坐标的繁琐。
• 绘图分层：通过 hold on 指令，程序分三次进行绘制（底层背景边、核心生成树边、顶层节点），确保了图形的对比度和清晰度。

使用方法

1. 在环境编辑器中打开程序文件。
2. 根据实际需求修改主控逻辑中的变量 n（顶点数）和 W（带权邻接矩阵）。
3. 点击“运行”按钮。
4. 在控制台查看生成的总权值和边明细矩阵，同时观察自动跳出的可视化图形窗口。