数据结构之图的邻接矩阵
·
目录
在图论与数据结构的学习中，邻接矩阵是最基础也最直观的图存储方式之一。它通过二维数组（矩阵）来表达顶点间的连接关系，适用于多种图算法的实现。本文将基于一份泛型邻接矩阵类，从原理、代码解析到实战应用，带你全面掌握这一数据结构。
一、邻接矩阵的核心原理
邻接矩阵的本质是用二维数组记录顶点间的边权，其设计思路可拆解为三个关键部分：
- 顶点存储：用
vector<V> _vertexs保存所有顶点，同时通过map<V, int> _indexMap建立 “顶点值→数组下标” 的映射，快速定位顶点在矩阵中的位置。 - 边的存储：用
vector<vector<W>> _matrix表示边的权重。_matrix[i][j]的含义为：- 若
i == j：通常为0（顶点到自身的权重，本文用Max_W统一初始化）； - 若顶点
i与j间有边：值为边的权重W； - 若顶点
i与j间无边：值为预设的最大权重Max_W（如INT_MAX，打印时用*表示）。
- 若
- 方向支持：通过模板参数
Direaction控制图的类型 ——true表示有向图（边单向），false表示无向图（边双向对称）。
二、通用邻接矩阵类解析
以下是支持泛型、可切换有向 / 无向图的邻接矩阵类实现，关键功能已标注说明：
#pragma once
#include<iostream>
#include<vector>
#include<map>
#include<climits>
using namespace std;
// 模板参数说明：
// V：顶点数据类型；W：边权重数据类型；Max_W：无边时的默认权重；Direaction：是否为有向图（true=有向，false=无向）
template<class V, class W, W Max_W = INT_MAX, bool Direaction = true>
class Gragh
{
public:
// 构造函数：初始化顶点和邻接矩阵
Gragh(const V* a, int n)
{
_vertexs.reserve(n); // 预分配空间，优化vector扩容开销
for (int i = 0; i < n; i++)
{
_vertexs.push_back(a[i]); // 存储顶点
_indexMap[a[i]] = i; // 建立顶点到下标的映射
}
// 初始化邻接矩阵：n行n列，默认值为Max_W（表示无边）
_matrix.resize(n);
for (int i = 0; i < n; i++)
{
_matrix[i].resize(n, Max_W);
}
}
// 功能1：根据顶点值获取其下标（含越界提示）
size_t GetvertexsIndex(const V& v)
{
auto it = _indexMap.find(v);
if (it != _indexMap.end())
{
return it->second; // 找到顶点，返回其下标
}
else
{
cout << "顶点 " << v << " 不存在！" << endl;
return -1; // 未找到顶点，返回-1（后续需校验）
}
}
// 功能2：添加边（自动适配有向/无向图）
void AddEdge(const V& start, const V& end, const W& w)
{
// 1. 获取起点和终点的下标
size_t src = GetvertexsIndex(start);
size_t drc = GetvertexsIndex(end);
// 2. 校验下标有效性（避免数组越界）
if (src == -1 || drc == -1) return;
// 3. 赋值边权重：有向图仅赋值src→drc，无向图双向赋值
_matrix[src][drc] = w;
if (Direaction == false) // 无向图时，反向边也需赋值
{
_matrix[drc][src] = w;
}
}
// 功能3：打印邻接矩阵（优化格式，提升可读性）
void Print()
{
// 打印顶点列表（带下标）
for (int i = 0; i < _vertexs.size(); i++)
cout << '[' << i << ']' << _vertexs[i] << " ";
cout << endl;
// 打印矩阵表头（列下标）
printf("\n%-3c", '\\'); // 左上角标识，区分行与列
for (int i = 0; i < _matrix.size(); i++)
printf("%-3d", i); // 列下标右对齐，占3字符
cout << endl;
// 打印矩阵内容（行下标 + 权重）
for (int i = 0; i < _matrix.size(); i++)
{
printf("%-3d", i); // 打印行下标
for (int j = 0; j < _matrix[i].size(); j++)
{
if (_matrix[i][j] == Max_W)
printf("%-3c", '*'); // 无边时打印*，替代Max_W
else
printf("%-3d", _matrix[i][j]); // 有边时打印权重
}
cout << endl;
}
}
private:
vector<V> _vertexs; // 存储所有顶点的集合
map<V, int> _indexMap; // 顶点值→数组下标的映射（快速查找）
vector<vector<W>> _matrix;// 邻接矩阵：存储边的权重
};
三、实战：有向图与无向图的创建
案例 1：有向图（默认行为，Direaction=true）
以 “程序模块依赖图” 为例，假设存在模块 A、B、C，依赖关系为：
A → B（权重 2，表示 A 依赖 B）；B → C（权重 3，表示 B 依赖 C）；C → A（权重 1，表示 C 依赖 A）。
#include "Gragh.hpp"
int main()
{
// 1. 定义顶点数组
string modules[] = { "A", "B", "C" };
int n = sizeof(modules) / sizeof(modules[0]);
// 2. 创建有向图对象（默认Direaction=true）
Gragh<string, int, INT_MAX> g(modules, n);
// 3. 添加有向边
g.AddEdge("A", "B", 2);
g.AddEdge("B", "C", 3);
g.AddEdge("C", "A", 1);
// 4. 打印邻接矩阵
g.Print();
return 0;
}
输出结果：
[0]A [1]B [2]C
\ 0 1 2
0 * 2 *
1 * * 3
2 1 * *
可见有向图的邻接矩阵不对称，仅 _matrix[src][drc] 有值，符合 “边单向” 的特性。
案例 2：无向图（显式指定 Direaction=false）
以 “社交关系图” 为例，假设用户 Alice、Bob、Charlie 的好友关系为：
Alice ↔ Bob（权重 5，表示亲密度）；Bob ↔ Charlie（权重 3，表示亲密度）；Alice ↔ Charlie（权重 2，表示亲密度）。
int main()
{
string users[] = { "Alice", "Bob", "Charlie" };
int n = sizeof(users) / sizeof(users[0]);
// 创建无向图对象（显式指定Direaction=false）
Gragh<string, int, INT_MAX, false> g(users, n);
// 添加无向边
g.AddEdge("Alice", "Bob", 5);
g.AddEdge("Bob", "Charlie", 3);
g.AddEdge("Alice", "Charlie", 2);
g.Print();
return 0;
}
输出结果：
[0]Alice [1]Bob [2]Charlie
\ 0 1 2
0 * 5 2
1 5 * 3
2 2 3 *
无向图的邻接矩阵沿对角线对称（_matrix[i][j] = _matrix[j][i]），符合 “边双向” 的特性。
四、邻接矩阵的优缺点与适用场景
优点
- 查询高效：判断两顶点是否有边、获取边权重的时间复杂度为
O(1)； - 实现简单：基于二维数组，逻辑直观，编码门槛低；
- 泛型支持：支持任意顶点类型（如
string、int）和权重类型（如int、double），通用性强。
缺点
- 空间复杂度高：对于
n个顶点的图，空间复杂度为O(n²)，稀疏图（边少）会造成大量空间浪费； - 顶点增删低效：添加或删除顶点时，需重新调整二维数组大小，时间复杂度为
O(n²)。
适用场景
- 稠密图：边数接近
n²的图（如完全图），空间浪费少； - 频繁查询边：需频繁判断顶点连接关系的场景（如最短路径算法 Floyd-Warshall）；
- 小规模图：顶点数量较少（如
n < 1000），空间开销可接受。
五、对比邻接矩阵 vs 邻接表
在图论中，选择合适的存储方式直接影响算法的时间和空间效率。本文将从原理、实现、复杂度、适用场景等维度，深度对比邻接矩阵和邻接表两种经典存储方案。
核心原理对比
| 维度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 存储结构 | 二维数组（矩阵），matrix[i][j] 表示顶点 i 到 j 的边权。 | 数组 + 链表（或向量），每个顶点对应一个链表，存储其邻接顶点及边权。 |
| 空间本质 | 基于 “顶点对” 的全局存储，空间复杂度固定为 O(n²)（n 为顶点数）。 | 基于 “边” 的局部存储，空间复杂度为 O(n + m)（m 为边数）。 |
| 方向支持 | 天然支持有向图（矩阵不对称）和无向图（矩阵对称）。 | 天然支持有向图（链表仅存出边）和无向图（每条边存两次，双向链表）。 |
代码实现对比
邻接表实现（泛型版）
template<class V, class W, bool Direaction = true>
class AdjList {
struct Edge {
int dest; // 邻接顶点下标
W weight; // 边权
Edge(int d, W w) : dest(d), weight(w) {}
};
public:
AdjList(const V* a, int n) {
_vertexs.reserve(n);
for (int i = 0; i < n; i++) {
_vertexs.push_back(a[i]);
_indexMap[a[i]] = i;
}
_adjList.resize(n);
}
void AddEdge(const V& start, const V& end, const W& w) {
size_t src = GetIndex(start);
size_t drc = GetIndex(end);
if (src == -1 || drc == -1) return;
_adjList[src].emplace_back(drc, w);
if (!Direaction) _adjList[drc].emplace_back(src, w);
}
private:
vector<V> _vertexs;
map<V, int> _indexMap;
vector<vector<Edge>> _adjList;
};
复杂度与性能对比
| 操作 | 邻接矩阵时间复杂度 | 邻接表时间复杂度 | 备注 |
|---|---|---|---|
| 初始化 | O(n²) | O(n) | 邻接矩阵需初始化所有顶点对 |
| 添加边 | O(1) | O(1) | 均为常数时间 |
| 删除边 | O(1) | O(m) | 邻接表需遍历链表找边 |
| 查询边（i,j） | O(1) | O(m) | 邻接表需遍历 i 的邻接链表 |
| 遍历所有边 | O(n²) | O(n + m) | 邻接矩阵需遍历整个矩阵 |
| 空间复杂度 | O(n²) | O(n + m) | 邻接表对稀疏图更友好 |
适用场景对比
| 场景类型 | 推荐方案 | 原因分析 |
|---|---|---|
| 稠密图 | 邻接矩阵 | 边数接近 n²，邻接表的链表开销不明显，矩阵的 O(1) 查询更高效。 |
| 稀疏图 | 邻接表 | 边数 m << n²，邻接矩阵会造成大量空间浪费，邻接表的 O(n + m) 空间更优。 |
| 频繁查询边 | 邻接矩阵 | 判断两顶点是否相连仅需 O(1) 时间，适合 Floyd 最短路径等算法。 |
| 频繁遍历邻接顶点 | 邻接表 | 遍历一个顶点的所有邻接顶点，邻接表仅需 O(degree(i)) 时间（degree(i) 为顶点 i 的度）。 |
| 动态增删顶点 | 邻接表 | 邻接矩阵增删顶点需重构 n² 规模的矩阵，邻接表仅需修改对应链表。 |
总结
- 邻接矩阵的核心优势是查询高效、实现简单，适合稠密图、频繁查询边、小规模图的场景；
- 邻接表的核心优势是空间高效、遍历邻接顶点高效，适合稀疏图、频繁遍历邻接顶点、动态增删顶点的场景。
五、总结
邻接矩阵是图的 “入门级” 存储方式，其直观的实现和高效的查询能力，使其成为理解图论算法的重要基础。本文通过一份泛型邻接矩阵类，详细讲解了其原理、代码细节与实战应用，并明确了其适用场景与局限性。
在实际开发中，需根据图的稀疏程度选择存储方式 —— 稠密图用邻接矩阵，稀疏图则推荐邻接表（空间更高效）。掌握邻接矩阵后，你可以进一步学习图的遍历（DFS、BFS）、最短路径（Dijkstra、Floyd）等算法，逐步深入图论的世界。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
25
0- 0
已为社区贡献3条内容
所有评论(0)