最小生成树同构判断系统

一个基于 C++ 的图算法课程项目,实现在无向带权图中找出所有不同构的最小生成树。

项目背景

在图论中，一个无向带权图可能存在多棵权重相同但结构不同的最小生成树。 本项目通过非递归遍历+剪枝优化的方式，枚举所有最小生成树，并通过图同构判断去除结构上等价的解。

核心功能

• 图的建模与读入(支持邻接矩阵)
• 最小生成树枚举(基于 Kruskal/Prim)
• 图同构判断算法
• 非递归实现+剪枝优化

技术栈

• 语言:C++ (Modern C++)
• 工程:Visual Studio
• 工程结构:头文件 + 多源文件分离

项目结构

• CreatAndIosmorphism.h - 核心类与接口定义
• CreatMST.cpp - 最小生成树生成
• Iosmorphism.cpp - 图同构判断
• test2.cpp - 主程序入口

输入输出

输入:in.txt(图的邻接矩阵表示) 输出:out.txt(所有不同构的最小生成树)

编译运行

使用 Visual Studio 打开 test2.vcxproj 即可编译运行。

算法要点

1. MST 枚举:基于 Kruskal/Prim 算法,枚举所有最小生成树
2. 同构判断:通过节点度序列、邻接关系判断两棵生成树是否同构
3. 剪枝优化:在搜索过程中提前剪去与已有同构的分支
4. **