C++图同构算法详解（从零开始掌握图结构比较与匹配）

什么是图同构？

两个无向图 G₁ = (V₁, E₁) 和 G₂ = (V₂, E₂) 被称为同构，如果存在一个双射函数 f: V₁ → V₂，使得对于任意两个顶点 u, v ∈ V₁，(u, v) 是 G₁ 中的一条边，当且仅当 (f(u), f(v)) 是 G₂ 中的一条边。

简单来说：只要能通过重新命名顶点，让两个图变得一模一样，它们就是同构的。

为什么图同构重要？

图同构在化学分子结构识别、社交网络分析、编译器优化、模式识别等领域有广泛应用。掌握 C++图同构算法 是深入理解图论与算法设计的重要一步。

基础判断条件（快速排除）

在尝试复杂匹配前，我们可以先用一些简单条件快速判断两个图不可能同构：

• 顶点数量不同
• 边数量不同
• 度序列（每个顶点的度数排序后）不同

这些条件虽然不能证明同构，但能高效排除大量非同构图对。

暴力回溯法实现（适合小图）

对于顶点数较少的图（如 n ≤ 8），我们可以使用暴力回溯尝试所有可能的顶点映射，并验证边是否一致。这是学习 图结构比较 的最佳入门方法。

下面是一个完整的 C++ 实现：

#include <iostream>#include <vector>#include <algorithm>using namespace std;// 判断在当前映射下，两个图是否一致bool checkIsomorphic(const vector<vector<int>>& g1,                     const vector<vector<int>>& g2,                     const vector<int>& mapping) {    int n = g1.size();    for (int i = 0; i < n; ++i) {        for (int j = 0; j < n; ++j) {            // 检查边 (i,j) 在 g1 中是否存在，是否与 g2 中 (mapping[i], mapping[j]) 一致            if (g1[i][j] != g2[mapping[i]][mapping[j]])                return false;        }    }    return true;}// 回溯尝试所有顶点排列bool backtrack(vector<int>& perm, vector<bool>& used,               const vector<vector<int>>& g1,               const vector<vector<int>>& g2,               int idx) {    int n = g1.size();    if (idx == n) {        return checkIsomorphic(g1, g2, perm);    }    for (int i = 0; i < n; ++i) {        if (!used[i]) {            used[i] = true;            perm[idx] = i;            if (backtrack(perm, used, g1, g2, idx + 1))                return true;            used[i] = false;        }    }    return false;}// 主函数：判断两个图是否同构bool areIsomorphic(const vector<vector<int>>& g1,                   const vector<vector<int>>& g2) {    if (g1.size() != g2.size()) return false;    int n = g1.size();    vector<int> perm(n);    vector<bool> used(n, false);    return backtrack(perm, used, g1, g2, 0);}// 辅助函数：打印邻接矩阵void printGraph(const vector<vector<int>>& g) {    for (const auto& row : g) {        for (int val : row) cout << val << " ";        cout << endl;    }}int main() {    // 示例图1：三角形    vector<vector<int>> graph2 = {        {0, 1, 1},        {1, 0, 1},        {1, 1, 0}    };    // 示例图2：顶点重排后的三角形    vector<vector<int>> graph2 = {        {0, 1, 1},        {1, 0, 1},        {1, 1, 0}    };    cout << "图1:\n";    printGraph(graph2);    cout << "\n图2:\n";    printGraph(graph2);    if (areIsomorphic(graph2, graph2)) {        cout << "\n✅ 两个图是同构的！\n";    } else {        cout << "\n❌ 两个图不是同构的。\n";    }    return 0;}

代码说明

• g1 和 g2 使用邻接矩阵表示图。
• backtrack 函数生成所有可能的顶点映射（即排列）。
• checkIsomorphic 验证当前映射是否保持边关系。
• 主函数先检查顶点数是否相等，再启动回溯。

这个实现虽然时间复杂度高（O(n! × n²)），但对于学习 C++图匹配 原理非常直观。

进阶方向

实际应用中，图可能很大，暴力法不可行。更高效的算法包括：

• VF2 算法（常用于子图同构）
• NAUTY 算法（基于图自同构群）
• 基于 WL test（Weisfeiler-Lehman）的近似方法

但无论使用哪种高级方法，理解本文的暴力回溯思想是掌握 图论算法实现 的基石。

总结

本文介绍了图同构的基本概念，并用 C++ 实现了一个清晰易懂的暴力回溯算法。通过这个教程，你已经掌握了如何进行 图结构比较 的核心逻辑。

记住：虽然暴力法只适用于小图，但它帮助你建立直觉。未来你可以在此基础上学习更高效的 C++图同构算法，应用于实际项目中。

关键词回顾：C++图同构算法、图论算法实现、图结构比较、C++图匹配。