邻接矩阵用二维数组存储图的边关系，适合顶点少且频繁查询边的场景。1. 使用vector<vector<int>>实现n×n矩阵；2. 无向图需双向设置matrixu和matrixv；3. 添加边时检查顶点合法性；4. 空间复杂度O(n²)，适用于稠密图；5. 可扩展为带权图。
在C++中实现图的邻接矩阵，核心是用二维数组存储顶点之间的连接关系。适用于顶点数量不多且需要频繁查询边存在性的场景。
邻接矩阵的基本结构
邻接矩阵使用一个二维数组 matrix[n][n] 表示图，其中 n 是顶点数。若顶点 i 到 j 有边，则 matrix[i][j] 为 1（或边权），否则为 0。对于无向图，矩阵是对称的。
常见实现方式是封装在一个类中，包含顶点数、二维数组（可用 vector>）和相关操作函数。
代码实现示例
以下是一个简单的无向图邻接矩阵实现：
立即学习“C++免费学习笔记（深入）”；
乾坤圈新媒体矩阵管家
17
新媒体账号、门店矩阵智能管理系统
17
查看详情
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
int vertexNum;
vector<vector<int>> adjMatrix;
public:
// 构造函数，初始化矩阵
Graph(int n) : vertexNum(n) {
adjMatrix.resize(n, vector<int>(n, 0));
}
// 添加边
void addEdge(int u, int v) {
if (u >= 0 && u < vertexNum && v >= 0 && v < vertexNum) {
adjMatrix[u][v] = 1;
adjMatrix[v][u] = 1; // 无向图双向设置
}
}
// 删除边
void removeEdge(int u, int v) {
if (u >= 0 && u < vertexNum && v >= 0 && v < vertexNum) {
adjMatrix[u][v] = 0;
adjMatrix[v][u] = 0;
}
}
// 判断是否有边
bool hasEdge(int u, int v) {
if (u >= 0 && u < vertexNum && v >= 0 && v < vertexNum)
return adjMatrix[u][v] == 1;
return false;
}
// 打印矩阵
void printMatrix() {
for (int i = 0; i < vertexNum; ++i) {
for (int j = 0; j < vertexNum; ++j) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}
};
使用与注意事项
使用时先创建图对象，再调用方法添加边并操作：
- 初始化图时指定顶点数量，避免越界
- 添加边前做合法性检查，防止访问非法内存
- 空间复杂度为 O(n²)，适合稠密图，稀疏图建议用邻接表
- 可扩展支持带权图，将 matrix 存储权重而非 0/1
基本上就这些。邻接矩阵实现简单，查边效率高，但占用空间大，根据实际需求选择即可。
相关标签：
edge c++ ios stream 封装 int 对象
本站资料仅供学习交流使用请勿商业运营，严禁从事违法，侵权等任何非法活动，否则后果自负！
THE END
暂无评论内容