C++静态图结构详解（从零开始掌握图的邻接矩阵实现）

什么是静态图结构？

静态图结构是指图的顶点数量和边的关系在程序运行前就已经确定，不会动态增删节点或边。这种结构非常适合使用数组（尤其是二维数组）来存储，也就是我们常说的 邻接矩阵。

邻接矩阵是一个 n × n 的二维数组（n 是顶点数），其中 matrix[i][j] 表示从顶点 i 到顶点 j 是否存在边。如果是无权图，通常用 1 表示有边，0 表示无边；如果是带权图，则直接存储权重值。

为什么选择邻接矩阵？

• 实现简单，逻辑清晰，适合初学者理解
• 查询两个顶点之间是否有边的时间复杂度为 O(1)
• 适用于顶点数量较少且稠密的图

当然，邻接矩阵也有缺点：空间复杂度为 O(n²)，当图很稀疏（边很少）时会浪费大量内存。但对于学习 C++静态图结构 来说，它是最佳起点。

C++ 实现邻接矩阵静态图

下面我们用 C++ 编写一个完整的静态图类，支持无向无权图的构建与基本操作。

#include <iostream>#include <vector>using namespace std;class StaticGraph {private:    int vertexCount;                    // 顶点数量    vector<vector<bool>> adjMatrix;    // 邻接矩阵，使用 bool 节省空间public:    // 构造函数：初始化图    StaticGraph(int n) : vertexCount(n) {        // 初始化 n x n 的邻接矩阵，全部设为 false（无边）        adjMatrix = vector<vector<bool>>(n, vector<bool>(n, false));    }    // 添加无向边    void addEdge(int u, int v) {        if (u < 0 || u >= vertexCount || v < 0 || v >= vertexCount) {            cout << "错误：顶点编号超出范围！" << endl;            return;        }        adjMatrix[u][v] = true;        adjMatrix[v][u] = true;  // 无向图，对称    }    // 判断是否存在边    bool hasEdge(int u, int v) {        if (u < 0 || u >= vertexCount || v < 0 || v >= vertexCount)            return false;        return adjMatrix[u][v];    }    // 打印邻接矩阵    void printGraph() {        cout << "邻接矩阵表示：\n";        for (int i = 0; i < vertexCount; ++i) {            for (int j = 0; j < vertexCount; ++j) {                cout << adjMatrix[i][j] << " ";            }            cout << endl;        }    }};// 主函数测试int main() {    int n = 4;  // 4 个顶点：0, 1, 2, 3    StaticGraph graph(n);    // 添加边：0-1, 0-2, 1-3    graph.addEdge(0, 1);    graph.addEdge(0, 2);    graph.addEdge(1, 3);    // 打印图    graph.printGraph();    // 查询边    cout << "\n顶点 0 和 1 之间是否有边？"          << (graph.hasEdge(0, 1) ? "有" : "无") << endl;    return 0;}

代码解析

上面的代码展示了如何用 C++ 实现一个简单的 静态图结构：

• 使用 vector<vector<bool>> 代替原始二维数组，更安全且自动管理内存
• 构造函数接收顶点数 n，并初始化一个 n×n 的全 false 矩阵
• addEdge 方法添加无向边（双向设置为 true）
• hasEdge 快速判断两点是否相连
• printGraph 用于可视化邻接矩阵

运行结果将输出如下邻接矩阵（1 表示有边）：

0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 0 

扩展思考：带权图怎么办？

如果你需要实现 带权图，只需将 vector<vector<bool>> 改为 vector<vector<int>> 或 vector<vector<double>>，并用一个特殊值（如 -1 或 INT_MAX）表示“无边”即可。这也是 C++图数据结构 中常见的变体。

总结

通过本文，你已经掌握了如何用 C++ 实现基于邻接矩阵的 静态图结构。这种实现方式简单、高效，特别适合顶点数量固定的小型图。无论你是准备面试，还是学习图论算法（如 DFS、BFS、Dijkstra），这都是坚实的基础。

记住我们的四个核心 SEO关键词：

• C++静态图结构
• 图的邻接矩阵实现
• C++图数据结构
• 静态图存储方法

动手试试吧！修改代码，尝试添加更多功能，比如计算每个顶点的度、判断图是否连通等。编程的乐趣，就在实践中！