图的存储方式详解（邻接矩阵 + 邻接表）| 算法入门必看
在算法学习中，图是仅次于树的核心数据结构，广泛应用于路径规划、网络拓扑、社交关系等场景。而图的存储是后续图论算法（DFS、BFS、最短路等）的基础——选择合适的存储方式，能直接影响算法的时间和空间效率。
本文将详细讲解图的两种最常用存储方式：邻接矩阵和邻接表，从原理、代码实现（C++）、优劣对比到适用场景，层层拆解，新手也能轻松理解、直接复用。
先明确图的基本概念：图（Graph）由顶点（Vertex）和边（Edge）组成，分为无向图（边无方向，如朋友关系）和有向图（边有方向，如网页跳转、依赖关系）；边还可带权值（如道路距离、网络带宽），称为带权图。
一、邻接矩阵（Adjacency Matrix）
1. 核心原理
邻接矩阵是用二维数组来表示图的存储结构，数组的行和列都对应图中的顶点，数组元素的值表示两个顶点之间是否存在边（或边的权值）。
假设图中有 n 个顶点（编号从 0 到 n-1），定义二维数组 graph[n][n]，则：
对于无向图：若顶点 i 和顶点 j 之间有边，则 graph[i][j] = graph[j][i] = 1（无权值）；若无边，则为 0；顶点自身（i=j）通常设为 0（无自环时）。
对于有向图：若存在从顶点 i 到顶点 j 的边，则 graph[i][j] = 1（无权值）；反之，graph[j][i] = 0；自身设为 0。
对于带权图：将数组元素的值改为边的权值，无边时设为一个极大值（如 INT_MAX），自身设为 0。
2. 可视化示例（直观理解）
以无向无权图为例，假设有 4 个顶点（0、1、2、3），边为 (0,1)、(0,2)、(1,3)、(2,3)，其邻接矩阵如下：
顶点 | 0 | 1 | 2 | 3 |
0 | 0 | 1 | 1 | 0 |
1 | 1 | 0 | 0 | 1 |
2 | 1 | 0 | 0 | 1 |
3 | 0 | 1 | 1 | 0 |
观察可知：无向图的邻接矩阵是对称矩阵，这是其显著特征。
3. C++ 代码实现（通用版）
以下代码涵盖无向无权、无向带权、有向无权、有向带权四种场景，可直接复制使用，注释清晰，新手可快速上手。
#include <iostream> #include <vector> #include <climits> // 用于INT_MAX（带权图无边时的默认值） using namespace std; // 图的邻接矩阵实现（支持无向/有向、无权/带权） c