目录
一、邻接矩阵的核心原理
二、通用邻接矩阵类解析
三、实战：有向图与无向图的创建
案例 1：有向图
案例 2：无向图
四、邻接矩阵的优缺点与适用场景
优点
缺点
适用场景
五、对比邻接矩阵 vs 邻接表
核心原理对比
代码实现对比
邻接表实现（泛型版）
复杂度与性能对比
适用场景对比
总结
五、总结
在图论与数据结构的学习中，邻接矩阵是最基础也最直观的图存储方式之一。它通过二维数组（矩阵）来表达顶点间的连接关系，适用于多种图算法的实现。本文将基于一份泛型邻接矩阵类，从原理、代码解析到实战应用，带你全面掌握这一数据结构。
一、邻接矩阵的核心原理邻接矩阵的本质是用二维数组记录顶点间的边权，其设计思路可拆解为三个关键部分：
顶点存储：用 vector
若 i == j：通常为 0（顶点到自身的权重，本文用 Max_W 统一初始化）；若顶点 i 与 j 间有边：值为边的权重 W；若顶点 i 与 j 间无边：值为预设的最大权重 Max_W（如 INT_MAX，打印时用 * 表示）。方向支持：通过模板参数 Direaction 控制图的类型 ——true 表示有向图（边单向），false 表示无向图（边双向对称）。二、通用邻接矩阵类解析以下是支持泛型、可切换有向 / 无向图的邻接矩阵类实现，关键功能已标注说明：
#pragma once
#include
#include
#include
#include
using namespace std;
// 模板参数说明：
// V：顶点数据类型；W：边权重数据类型；Max_W：无边时的默认权重；Direaction：是否为有向图（true=有向，false=无向）
template
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 _vertexs; // 存储所有顶点的集合
map _indexMap; // 顶点值→数组下标的映射（快速查找）
vector> _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 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 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 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 _vertexs;
map _indexMap;
vector> _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）等算法，逐步深入图论的世界。