图同构判定算法 C++ 实现：邻接矩阵全排列法 O(n²×n!) 复杂度分析

在计算机科学和数学领域，图同构问题一直是一个既基础又具有挑战性的课题。想象一下，你面前有两张社交网络的关系图，它们的节点标签不同但连接方式惊人地相似——如何判断这两张图在结构上是否完全相同？这就是图同构问题要解决的核心。对于学习算法设计与分析的学生而言，理解并实现图同构判定算法不仅能加深对图论的理解，更是锻炼算法思维和编程能力的绝佳机会。

本文将聚焦于基于邻接矩阵全排列的暴力判定方法，通过完整的C++实现、复杂度推导和实测数据分析，带你深入理解这一经典算法的内在机理。虽然这种方法在时间复杂度上并不高效（O(n²×n!)），但对于小规模图（n≤10）的判定仍然实用，更重要的是，它为我们理解更高级的同构算法奠定了坚实基础。

1. 图同构问题基础

1.1 同构的数学定义

两个图G=(V,E)和H=(W,F)被称为同构的，当且仅当存在一个双射f:V→W，使得对于V中的任意两个顶点u和v，(u,v)∈E当且仅当(f(u),f(v))∈F。换句话说，同构的图具有完全相同的连接结构，只是顶点的"名称"可能不同。

关键判定条件：

• 顶点数相同（|V|=|W|）
• 边数相同（|E|=|F|）
• 度数序列相同（按度数排序后的顶点度数列表必须一致）

1.2 邻接矩阵表示法

邻接矩阵是表示图结构的常用方式。对于一个有n个顶点的图，其邻接矩阵是一个n×n的方阵，其中第i行第j列的元素表示顶点i与顶点j之间是否存在边。

// 示例：6个顶点的图的邻接矩阵表示 vector<vector<int>> adj_matrix = { {0, 1, 0, 0, 0, 0}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 0, 0}, {0, 0, 1, 0, 1, 1}, {0, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 0, 0} };

2. 全排列判定算法实现

2.1 算法核心思想

暴力法的基本思路是：尝试图G1顶点所有可能的排列方式，检查是否存在一种排列使得其邻接矩阵与图G2完全相同。如果找到这样的排列，则两图同构；否则不同构。

算法步骤：

1. 检查顶点数和边数是否相同（快速排除明显不同构的情况）
2. 检查度数序列是否匹配
3. 生成图G1顶点的所有排列
4. 对每种排列，检查对应的邻接矩阵是否与图G2相同

2.2 C++完整实现

#include <iostream> #include <vector> #include <algorithm> using namespace std; bool checkIsomorphism(const vector<vector<int>>& g1, const vector<vector<int>>& g2, const vector<int>& permutation) { int n = g1.size(); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (g1[permutation[i]][permutation[j]] != g2[i][j]) { return false; } } } return true; } bool areIsomorphic(vector<vector<int>> g1, vector<vector<int>> g2) { // 检查顶点数 if (g1.size() != g2.size()) return false; int n = g1.size(); vector<int> perm(n); for (int i = 0; i < n; ++i) perm[i] = i; // 检查每种排列 do { if (checkIsomorphism(g1, g2, perm)) { return true; } } while (next_permutation(perm.begin(), perm.end())); return false; }

2.3 优化技巧

虽然暴力法本质上是穷举，但我们可以通过一些优化减少不必要的计算：

1. 度序列过滤：在生成排列前，先确保两个图的度序列相同
2. 对称性剪枝：跳过会产生相同邻接矩阵的等价排列
3. 早期终止：一旦找到匹配的排列立即返回结果

// 优化后的版本，添加度序列检查 bool areIsomorphicOptimized(vector<vector<int>> g1, vector<vector<int>> g2) { if (g1.size() != g2.size()) return false; int n = g1.size(); vector<int> deg1(n, 0), deg2(n, 0); // 计算度序列 for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { deg1[i] += g1[i][j]; deg2[i] += g2[i][j]; } } // 度序列排序后比较 sort(deg1.begin(), deg1.end()); sort(deg2.begin(), deg2.end()); if (deg1 != deg2) return false; // 原始排列检查 vector<int> perm(n); for (int i = 0; i < n; ++i) perm[i] = i; do { if (checkIsomorphism(g1, g2, perm)) { return true; } } while (next_permutation(perm.begin(), perm.end())); return false; }

3. 复杂度分析

3.1 时间复杂度推导

全排列法的复杂度主要来自排列生成和矩阵比较：

1. 排列生成：n个顶点有n!种排列方式
2. 矩阵比较：每种排列需要比较n²个矩阵元素

因此，最坏情况时间复杂度为O(n²×n!)。但实际运行时间可能远小于这个上界，因为：

• 度序列不匹配时立即返回
• 可能在尝试部分排列后就找到解

复杂度对比表：

3.2 空间复杂度分析

空间消耗主要来自：

• 存储两个图的邻接矩阵：O(n²)
• 排列过程中的临时存储：O(n)

因此总空间复杂度为O(n²)，对于现代计算机而言，处理n≤10的图内存消耗可以忽略不计。

4. 实测性能与优化建议

4.1 不同规模图的运行时间

我们在标准测试环境下（Intel i7-10750H，16GB RAM）测量了算法处理不同规模图的时间：

测试数据：随机生成的100组同构和非同构图，取平均值

4.2 优化方向

虽然全排列法对小规模图有效，但对于n>10的图，性能急剧下降。实际应用中可考虑以下优化路径：

1. 启发式搜索：基于顶点度数和局部结构特征优先尝试更可能的排列
2. 分区策略：根据顶点特性将图分成若干部分，分别比较
3. 并行计算：利用多线程同时检查不同排列
4. 混合方法：结合全排列与更高级算法（如Nauty）的优点

// 示例：并行版本（使用C++17的并行算法） #include <execution> bool areIsomorphicParallel(vector<vector<int>> g1, vector<vector<int>> g2) { if (g1.size() != g2.size()) return false; int n = g1.size(); vector<int> perm(n); for (int i = 0; i < n; ++i) perm[i] = i; // 并行检查排列 bool found = false; do { if (checkIsomorphism(g1, g2, perm)) { found = true; break; } } while (next_permutation(execution::par, perm.begin(), perm.end())); return found; }

5. 应用场景与扩展思考

5.1 实际应用价值

尽管时间复杂度较高，全排列法在以下场景仍有其价值：

• 教学演示：直观展示同构判定的基本思想
• 小规模确定性系统：如化学分子结构比较
• 算法验证：作为更复杂算法的基准测试

5.2 算法局限性

全排列法的主要限制在于其阶乘级的时间复杂度。对于n=15的图，15! ≈ 1.3×10¹²，即使每秒能处理100万次排列检查，也需要约15天才能完成。这促使我们研究更高效的算法，如：

• Nauty算法：基于群论和启发式的高效算法
• 特征多项式法：利用矩阵特征值作为同构不变量
• 基于深度学习的近似方法：新兴研究方向

5.3 进一步学习建议

对于希望深入图同构问题的读者，建议从以下方向扩展：

1. 学习Nauty算法的基本原理和实现
2. 研究图的自同构群与同构判定的关系
3. 探索近似算法在大型图同构中的应用
4. 了解图同构问题在复杂性理论中的地位（是否属于P问题仍未知）