MATLAB最小生成树优化的连通支配集算法实现

资 源 简 介

本项目基于MATLAB实现了最小连通支配集(MCDS)的高效求解算法。通过构建最小生成树(MST)作为基础骨架，结合贪心策略筛选关键节点，确保网络连通性的同时最小化支配集规模。适用于无线传感器网络等拓扑优化场景。

详 情 说 明

基于最小生成树优化的最小连通支配集算法实现

项目介绍

本项目实现了一种基于最小生成树（MST）的最小连通支配集（MCDS）优化算法。算法首先通过 Prim 或 Kruskal 算法构建图的最小生成树，随后在 MST 基础上应用贪心策略或启发式规则筛选关键节点，形成满足连通性要求且规模尽可能小的支配集。该算法适用于无线传感器网络、通信网络拓扑优化等场景，能够有效降低支配集节点数量，同时保证网络的连通性。

功能特性

• 最小生成树构建：支持 Prim 算法和 Kruskal 算法，可根据输入图的边权重要求选择适当的 MST 构造方法。
• 连通支配集优化：在 MST 基础上，采用贪心策略逐步剔除冗余节点，或在保证连通性的前提下选择度数高、覆盖范围大的关键节点，以缩减支配集规模。
• 结果验证与可视化：提供支配集连通性验证功能，并可输出优化后的网络连通图，直观展示 MCDS 节点及其连接关系。
• 性能指标输出：计算并输出支配集大小、算法运行时间、连通度验证结果等关键性能指标，便于评估算法效率。

使用方法

1. 准备输入数据：

输入图为邻接矩阵或边列表形式（可包含权重），存储为 MAT 文件或文本格式。例如，邻接矩阵应为一个 N×N 的矩阵（N 为节点数），边列表每行表示一条边的两个端点及可选权重。

1. 设置算法参数：

可选择 MST 算法类型（Prim 或 Kruskal），并可设定支配集优化过程的阈值参数（如最小度数约束等）。

1. 运行主程序：

执行主程序文件，算法将自动完成 MST 构建、支配集优化及结果验证。最终输出最小连通支配集的节点列表，并可选择生成连通图可视化结果。

1. 查看输出结果：

结果包括： - 最小连通支配集节点列表 - 优化后的网络连通图（可选图形显示） - 性能指标报告（支配集规模、计算时间、连通性验证）

系统要求

• 操作系统：Windows / Linux / macOS
• 软件环境：MATLAB R2018b 或更高版本
• 依赖工具包：MATLAB 基本绘图工具（用于可视化），无需额外工具箱

文件说明

主程序文件集中实现了算法的核心流程：包括图的加载与预处理、最小生成树的构造（允许用户选择 Prim 或 Kruskal 方法）、基于 MST 的连通支配集贪心优化、支配集连通性验证，以及最终结果的可视化输出与性能指标计算。该文件作为算法执行的入口，协调各功能模块按序完成 MCDS 求解任务。