C++邻接矩阵详解（图的邻接矩阵表示法从零入门）

邻接矩阵的优缺点

优点：

• 实现简单，易于理解；
• 判断两个顶点是否相邻的时间复杂度为 O(1)。

缺点：

• 空间复杂度高，为 O(n²)，即使图很稀疏（边很少）也会浪费大量内存；
• 遍历所有邻接点需要 O(n) 时间，效率不如邻接表。

C++ 实现邻接矩阵

下面我们用 C++ 编写一个简单的程序，演示如何使用邻接矩阵表示一个无向无权图。

#include <iostream>#include <vector>using namespace std;class Graph {private:    int numVertices;    vector<vector<int>> adjMatrix;public:    // 构造函数    Graph(int vertices) {        numVertices = vertices;        // 初始化邻接矩阵，全部设为0        adjMatrix = vector<vector<int>>(numVertices, vector<int>(numVertices, 0));    }    // 添加边（无向图）    void addEdge(int i, int j) {        if (i >= 0 && i < numVertices && j >= 0 && j < numVertices) {            adjMatrix[i][j] = 1;            adjMatrix[j][i] = 1; // 无向图是对称的        }    }    // 打印邻接矩阵    void printMatrix() {        cout << "邻接矩阵如下：\n";        for (int i = 0; i < numVertices; i++) {            for (int j = 0; j < numVertices; j++) {                cout << adjMatrix[i][j] << " ";            }            cout << endl;        }    }};// 主函数测试int main() {    Graph g(4); // 创建一个包含4个顶点的图    // 添加边    g.addEdge(0, 1);    g.addEdge(0, 2);    g.addEdge(1, 2);    g.addEdge(2, 3);    // 打印邻接矩阵    g.printMatrix();    return 0;}

代码说明

- 我们使用 vector<vector<int>> 来动态创建二维邻接矩阵，避免固定大小数组的限制；

- addEdge 函数用于添加一条无向边，因此同时设置 adjMatrix[i][j] 和 adjMatrix[j][i] 为 1；

- 如果是有向图，只需设置 adjMatrix[i][j] = 1 即可；如果是有权图，则把 1 替换为具体的权重值（如 5、10 等）。

总结

通过本教程，你已经掌握了 C++邻接矩阵 的基本概念和实现方法。虽然邻接矩阵在处理稀疏图时效率不高，但其简洁性和快速查询特性使其在某些场景（如 Floyd 算法、小规模图）中依然非常实用。建议初学者先熟练掌握邻接矩阵，再进阶学习邻接矩阵实现教程中的优化技巧以及邻接表等其他表示方法。

记住，扎实的 C++图论基础 是解决算法竞赛和实际工程问题的关键一步！