图论这块内容真要铺开讲写一本厚书都不过分。但我翻来覆去观察身边初学者发现大多数人卡住的点根本不在那些花哨的高级算法反而在最前面的“存储结构”就没吃透。邻接矩阵写起来最无脑但一个 10 万顶点的图你敢开二维数组吗邻接表省空间可链表指针一多代码和调试就失控这种体验我太熟悉了。这篇文章就把图论存储这条线彻底捋清楚图的定义、邻接矩阵和邻接表的核心原理、C 完整实现、复杂度对比、实际选型建议以及我实操中踩过的各种坑。适合刚接触图论想打牢基础的同学也适合面试前快速复习的人直接拿来参考。1. 图的基本概念与存储需求1.1 图的定义与常见分类图Graph在数据结构里说的是由顶点的有穷非空集合和顶点之间边的集合组成的一种结构通常表示为 G(V, E)。其中 V 是顶点集合E 是边的集合。注意这里有个细节线性表可以允许空表树可以允许空树但图结构里顶点集合 V 不能为空边集合 E 可以为空。图上常见的分类有这么几种我平时跟人交流时发现不少初学者容易搞混这里我按自己的理解重新梳理一下无向图边没有方向比如两个人认识这种关系是相互的。如果顶点 A 到 B 有一条边那么 B 到 A 也算连通。有向图边有方向A 指向 B 和 B 指向 A 是两条完全不同的弧。比如网站的链接跳转关系A 页面能跳转到 B不代表 B 能跳回 A。带权图网不管是无向还是有向边上可以附带权值比如地图上两个城市之间的距离、通信网络里的传输延迟等。此外还有几个常用术语得记住无向图中顶点 v 的度degree是和它相关联的边的条数有向图中度分成入度和出度入度是以该顶点为终点的弧的数目出度是以该顶点为起点的弧的数目。这些概念直接影响后续存储结构的设计比如我要算一个顶点的度不同的存储方式实现成本完全不同。1.2 图的存储到底要解决什么问题很多人学图论上来就背概念背完邻接矩阵的定义就兴冲冲去写代码写着写着发现问题不少顶点信息存哪边信息怎么表示无向图和有向图的存储差在哪带权图又该怎么办这些问题归根结底就是图的存储结构要回答的三个核心问题第一顶点集合怎么存。顶点本身有编号、有数据比如城市名、人物 ID这部分比较简单一维数组就能搞定。第二顶点之间的关系边怎么表示。这是存储结构的核心难点因为边是二元关系一个顶点可能和很多顶点相连也可能和某些顶点不相连如何用有限的存储空间和可接受的时间成本把这个二元关系完整记录下来就是设计存储结构的核心命题。第三必须支撑常见图运算的高效实现。比如判断任意两个顶点之间有没有边、遍历某个顶点的所有邻接点、计算某个顶点的度、求图的连通分量等。如果存储结构设计得好这些操作要么简单直接要么效率可控如果结构不合适那后续任何算法都要付出惨痛的时间代价。拿最朴素的思路来想用二维数组 a[i][j] 的值等于 1 表示 i 和 j 有边为 0 表示没有边。这恰恰就是邻接矩阵的最原始形态。而如果你用链表把每个顶点的邻居串起来这又慢慢演化成了邻接表。所以说这两种存储方式不是凭空发明的而是从“顶点之间关系怎么表示”这个问题自然推导出来的。1.3 为什么不能只用线性表或树结构替代我以前带新人时总有人问图不也可以用数组存吗不也可以用链表存吗单独拿数组或者链表当然能存一部分图的信息但问题的关键在于图是多对多的关系不像线性表是一对一也不像树是一对多。线性表里每个元素只有一个直接前驱和一个直接后继树里每个节点只有一个父节点但图里一个顶点可能和成千上万个顶点都有连接。如果你强行用线性表去存图那表里每个节点都得挂上一大串邻接信息遍历的时候要么反复扫描整张表要么设计极其复杂的索引结构时间和空间两头不讨好。树结构也不行树是分层级的图是网状的树存不了环更存不了任意两顶点之间的多条通路。所以图必须有自己的专用存储结构邻接矩阵和邻接表正是最经典、最基础的两套方案。这段话我特意放在前面说是想先把“为什么需要专门研究图的存储结构”这个问题解决掉不然直接上代码读者很容易陷入“我背了代码但不知道为什么这样写”的状态。2. 邻接矩阵最直观的存储方案2.1 邻接矩阵的核心思想邻接矩阵Adjacency Matrix的思路特别朴素既然顶点之间是二元关系那我就用二维数组来存这个关系。假设图有 n 个顶点就把顶点编号为 0 到 n-1然后开一个 n×n 的二维数组 matrix矩阵中第 i 行第 j 列的元素用来表示顶点 i 到顶点 j 的关系。对于不带权的图通常用 1 表示有边0 表示无边对于带权图用具体的权值表示边权用无穷大INF表示不可达用 0 表示顶点自身到自身。无向图因为边是对称的所以它的邻接矩阵一定是一个对称矩阵。也就是说 matrix[i][j] 和 matrix[j][i] 的值相等。这一特性在代码实现和空间优化上都有文章可做后面我会专门展开。用生活化的例子来类比你可以把邻接矩阵想象成班级同学之间的“同桌记录表”表格的行和列都写着全班同学的名字交叉点的空格填上“认识”或“不认识”。想看任意两个人是否认识直接查表就行O(1) 时间。但缺点是哪怕全班只有 10 对同桌关系这张表也得开 50×50 或者更大全班 50 人的话就是 2500 个格子大量格子都是空的非常浪费。2.2 C 完整实现下面这段代码是我在实际刷题时常用的邻接矩阵模板我用 C 实现包含了无向图和有向图的建图逻辑以及几个最常用的查询操作。#include iostream #include vector #include climits using namespace std; const int INF INT_MAX; class GraphMatrix { private: int n; // 顶点数 vectorvectorint matrix; // 邻接矩阵 bool directed; // 是否有向 public: // 构造函数n 为顶点数directed 表示是否有向图 GraphMatrix(int n, bool directed false) : n(n), directed(directed) { matrix.resize(n, vectorint(n, INF)); // 初始化为无穷大 for (int i 0; i n; i) { matrix[i][i] 0; // 自身到自身距离为 0 } } // 添加一条边weight 为权值默认无权图时传 1 void addEdge(int u, int v, int weight 1) { matrix[u][v] weight; if (!directed) { matrix[v][u] weight; // 无向图需要对称存储 } } // 判断两个顶点之间是否有边 bool hasEdge(int u, int v) { return matrix[u][v] ! INF u ! v; } // 获取边的权值若不可达返回 INF int getWeight(int u, int v) { return matrix[u][v]; } // 获取某个顶点的度无向图 int getDegree(int u) { int degree 0; for (int v 0; v n; v) { if (matrix[u][v] ! INF v ! u) { degree; } } return degree; } // 打印整个矩阵方便调试 void print() { for (int i 0; i n; i) { for (int j 0; j n; j) { if (matrix[i][j] INF) { cout INF ; } else { cout matrix[i][j] ; } } cout endl; } } };这里我用 INF 而非 0 来初始化矩阵是有讲究的。使用 0 的话无法区分“i 到 j 没有边”和“i 到 j 的权值就是 0”。如果我们只处理无权图用 0 和 1 没问题但一旦涉及带权图0 可能会导致后续最短路径算法出现逻辑错误。所以一开始就统一用 INF 初始化习惯养好了后面能少踩很多坑。另外代码里的 getDegree 是计算无向图顶点的度直接遍历整行统计不等于 INF 且不是自身的格子数量。这个操作的时间复杂度是 O(n)也就是必须把一行全部扫完才行这一点在对比邻接表时会有明显差异。2.3 邻接矩阵的空间与时间代价邻接矩阵的空间复杂度是 O(n²)n 是顶点数。这一点是它的最大瓶颈。假设我们用 int 存矩阵元素每个 int 占 4 字节那么 1000 个顶点的矩阵就是 1000×1000×4 4MB看起来还能接受但如果顶点数到 10000那就是 10000×10000×4 400MB一般的刷题环境直接就内存溢出了再到 100000 个顶点那更是完全不可能。时间代价方面几个典型操作的复杂度我整理成了表方便和后面邻接表做对比操作邻接矩阵时间复杂度说明判断两顶点是否有边O(1)直接查 matrix[u][v]获取某顶点的所有邻接点O(n)必须扫一整行计算顶点的度O(n)无向图扫一行有向图出度扫一行、入度扫一列遍历整个图DFS/BFSO(n²)每个顶点都要扫一行添加/删除一条边O(1)直接修改矩阵元素最亮眼的优势就是判断任意两个顶点之间是否有边一次数组下标访问就出结果这个在很多算法里是极大的优势。最致命的短板则是遍历邻接点时必须扫一整行哪怕这个顶点只有一个邻居你也要从头检查 n 个格子。2.4 邻接矩阵的实际应用场景那邻接矩阵到底适合什么场景呢我根据自己的项目经验和刷题经验总结了这么几类稠密图。如果一个图的边数量非常接近 n²也就是大部分顶点之间都有边相连那么邻接矩阵的空间浪费就不存在了矩阵里基本没有 INF。此时用邻接矩阵反而比邻接表更简单直接。频繁查询边是否存在。比如需要反复判断顶点 u 和 v 之间有没有关系的算法邻接矩阵一次数组下标访问搞定的特性极其加分。Floyd-Warshall 多源最短路径算法。这个算法本身就需要一个二维矩阵来保存所有顶点对之间的最短距离直接用邻接矩阵非常自然改写起来也省事。它可以看成“数据结构服务于特定算法”的典型案例。顶点数小但边数多的场景。比如 n ≤ 1000 甚至 n ≤ 2000 的题开一个二维矩阵没啥压力邻接矩阵的简单和直观就成了最大优点。我在刷一些竞赛题目时如果确认数据量小会优先选邻接矩阵因为代码写起来快不容易出错。3. 邻接表节省空间的实用方案3.1 邻接表的核心思想邻接表Adjacency List的思路是不要用 n×n 的矩阵存所有的顶点对关系而是只存存在的边。具体做法是给每个顶点都配备一个链表链表中存储的是和这个顶点相邻的其他顶点编号以及对应的边权。还是用那个“班级同桌记录表”来类比邻接矩阵是全班每个人的关系都写在表格里邻接表则更像是每个人发一张小卡片卡片上只写你自己认识的人。你社交广你的卡片长一点你认识的人少卡片就短。全班所有人的卡片加起来长度约等于实际的朋友关系数量。对于无向图来说因为 A 认识 B 也意味着 B 认识 A所以一条边会在两个顶点的链表中各出现一次。对于有向图则只需要在弧尾顶点的链表中存储弧头顶点即可。比如 A 指向 B只需要在 A 的链表中记录 B。邻接表的本质是“数组嵌套链表”也有人用 vector 数组来实现这在 C 里特别方便。我更推荐用 vector因为链表手动管理节点太容易出错vector 自动扩容省心得多。但底层原理你要明白它模拟的仍然是每个顶点后挂一条链的结构。3.2 C 完整实现这里我给出两种实现方式。第一种是竞赛和算法题中最常用的 vector 实现代码非常简短第二种是手动链表实现帮助你理解底层原理。先看 vector 版本#include iostream #include vector #include algorithm using namespace std; struct Edge { int to; // 弧头顶点编号 int weight; // 边权 Edge(int to 0, int weight 1) : to(to), weight(weight) {} }; class GraphList { private: int n; vectorvectorEdge adj; bool directed; public: GraphList(int n, bool directed false) : n(n), directed(directed) { adj.resize(n); } void addEdge(int u, int v, int weight 1) { adj[u].push_back(Edge(v, weight)); if (!directed) { adj[v].push_back(Edge(u, weight)); } } // 判断 u 到 v 是否有边 bool hasEdge(int u, int v) { for (const Edge e : adj[u]) { if (e.to v) { return true; } } return false; } // 获取 u 的所有邻接点 vectorint getNeighbors(int u) { vectorint neighbors; for (const Edge e : adj[u]) { neighbors.push_back(e.to); } return neighbors; } // 无向图中获取顶点的度 int getDegree(int u) { return (int)adj[u].size(); } };再来看手动链表的版本。说实话我现在实际写代码几乎不用这种写法但面试或考试里偶尔会考到“用链表实现邻接表”这种题所以理解原理还是有必要的。关键点是每个顶点维护一个头节点然后每条边对应一个边节点边节点里存邻接顶点编号、权值以及指向下一个边节点的指针。#include iostream using namespace std; struct EdgeNode { // 边表节点 int to; int weight; EdgeNode* next; EdgeNode(int to, int weight) : to(to), weight(weight), next(nullptr) {} }; struct VertexNode { // 顶点表节点 int data; EdgeNode* firstEdge; VertexNode() : data(0), firstEdge(nullptr) {} }; class GraphListManual { private: int n; VertexNode* vertices; bool directed; public: GraphListManual(int n, bool directed false) : n(n), directed(directed) { vertices new VertexNode[n]; this-directed directed; } void addEdge(int u, int v, int weight 1) { // 头插法把新边节点插入到 u 的链表头部 EdgeNode* newEdge new EdgeNode(v, weight); newEdge-next vertices[u].firstEdge; vertices[u].firstEdge newEdge; if (!directed) { // 无向图还需要在 v 的链表中反向插入 EdgeNode* newEdgeReverse new EdgeNode(u, weight); newEdgeReverse-next vertices[v].firstEdge; vertices[v].firstEdge newEdgeReverse; } } void printGraph() { for (int i 0; i n; i) { cout 顶点 i : ; EdgeNode* cur vertices[i].firstEdge; while (cur) { cout - cur-to ( cur-weight ) ; cur cur-next; } cout endl; } } };这里用的头插法有一个明显的效果链表中邻接点的顺序和插入顺序是反的。如果你希望保持输入顺序那就得改成尾插法或者干脆用 vector 的 push_back每次直接追加到尾部。实际刷题时我更推荐 vector 加尾插因为大部分时候邻接点的遍历顺序对结果没有影响不需要额外处理链表指针。3.3 邻接表的空间与时间代价邻接表的核心优势体现在空间上。对于有向图邻接表需要存储 E 条边对于无向图因为每条边存两次所以是 2E。再加上 n 个顶点的数组开销总的空间复杂度是 O(n E)。在稀疏图里 E 远小于 n²这个优势非常明显。举一个直观的数字如果图有 1 万个顶点、2 万条边无向图邻接表的边节点大约是 4 万个配合 1 万个数组元素撑死几十万字节。而邻接矩阵要开 1 亿个 int光这个就 400MB直接爆内存。这就是为什么实际工程和大规模图计算中都采用邻接表或者基于邻接表思想发展出来的 CSRCompressed Sparse Row等更紧凑的格式。操作邻接表时间复杂度邻接矩阵时间复杂度说明判断两顶点是否有边O(degree(u))O(1)邻接表需遍历链表获取所有邻接点O(degree(u))O(n)邻接表直接遍历链表计算顶点的度O(1)O(n)邻接表 size 直接返回遍历整个图O(n E)O(n²)邻接表只访问存在的边添加一条边O(1)头插法O(1)两者都快上表是核心操作的时间对比。关键在于遍历整个图用邻接表只需要对每条边访问一次时间复杂度 O(n E)而邻接矩阵不管有没有边每个顶点都要扫一行所以是 O(n²)。在稀疏图上E 远小于 n²邻接表整体的遍历效率是碾压级的。不过邻接表也有一个明显短板想判断两个顶点之间是否存在边必须沿着链表中顶点 u 的邻接点一个个找最坏情况下要找 O(degree(u)) 次。如果这个图是一个极端图某个中心顶点的度非常大那判断多次之后性能就会下降。3.4 从邻接矩阵到邻接表的转换工程里有时候数据源给的是邻接矩阵但你的算法用邻接表更合适这时候需要做个转换。转换逻辑很简单遍历矩阵的每个元素只要不是 0、不是 INF、不是自环就往邻接表里添加一条边。class GraphConverter { public: // 从邻接矩阵构造邻接表注意 matrix 中的 INF 表示不可达 static vectorvectorpairint,int matrixToList( const vectorvectorint matrix) { int n matrix.size(); vectorvectorpairint,int adj(n); for (int i 0; i n; i) { for (int j 0; j n; j) { if (matrix[i][j] ! INF i ! j) { adj[i].push_back({j, matrix[i][j]}); } } } return adj; } // 从邻接表构造邻接矩阵 static vectorvectorint listToMatrix( const vectorvectorpairint,int adj) { int n adj.size(); vectorvectorint matrix(n, vectorint(n, INF)); for (int i 0; i n; i) { matrix[i][i] 0; for (const auto [j, w] : adj[i]) { matrix[i][j] w; } } return matrix; } };转换有一个需要小心的地方无向图从矩阵转成邻接表时矩阵本身就是对称的所以每一条边会被扫描两次最终在邻接表里每个顶点的链表中也会同时出现。这个结果没毛病因为无向图邻接表本来就应该存双向边。但如果你后续处理时有“边去重”的需求就得特别注意了。4. 两种存储结构的全面对比与选型4.1 空间维度稀疏还是稠密这是第一道分水岭我经常跟人说选邻接矩阵还是邻接表第一个问题先问自己图是稀疏图还是稠密图如果边数 E 接近 n² 的数量级也就是每个顶点平均跟绝大多数其他顶点相连矩阵里基本都是有效数据那么用邻接矩阵不浪费。反之如果 E 只有 n 的数量级甚至更少那矩阵里绝大多数格子都是 INF纯粹浪费内存。工程上有个经验阈值可以参考当 E 明显小于 n²/4 时即矩阵中有超过 75% 的空位优先考虑邻接表。当然这个数值不是绝对的还要看具体需求。空间的实际测算我帮大家算一下。假设顶点数 n 5000采用 int 存储邻接矩阵要开 5000×5000 2500 万个 int约 100MB。如果这时的边数 E 20000无向图邻接表只需要存储 40000 个边节点外加 5000 个数组元素每个边节点两个 int 加一个指针的话大约 12 字节算下来 40000×12 ≈ 480KB算上数组开销也不到 1MB。差距是一百倍以上。4.2 时间维度不同操作各有胜负前面已经列出了两张复杂度表这里我做个综合性的结论如果你要做的操作是全图遍历DFS、BFS邻接表更占优势因为只访问存在的边O(n E) 优于 O(n²)。如果你需要频繁判断两个点之间是否有边邻接矩阵更省时间O(1) 完胜 O(degree(u))。如果你需要频繁获取某个顶点的所有邻接点邻接表占优因为它的遍历代价和该顶点的实际度成正比而邻接矩阵无论如何都要扫完整行。这也就解释了为什么不同算法对存储结构的偏好不一样。比如 Floyed 算法天然就需要二维矩阵存中间结果邻接矩阵是自然而然的选择。而 Dijkstra 算法的堆优化版本是典型的“频繁取邻居、不频繁判断边是否存在”的场景所以用邻接表配合优先队列是标配。还有一种情况是顶点数很大但每次只操作局部子图这时候邻接表更合适因为你不必把所有顶点对的边关系都加载到内存里拿到某个顶点的链表就等于拿到了它周边的完整信息。4.3 实际刷题和工程中的选型建议我总结经验后一般按下面的规则来选场景推荐结构原因顶点数 ≤ 300边数多稠密图邻接矩阵实现简单Floyd 等算法直接适用顶点数大边数少稀疏图邻接表省内存遍历效率高需要频繁判断两点是否连通邻接矩阵O(1) 查询需要频繁获取邻居做 DFS/BFS邻接表只扫描实际存在的边带权图且顶点数 ≤ 1000两者皆可看具体算法需求顶点数超过 10000邻接表矩阵内存多半扛不住这些规则不是绝对的但根据我的经验照着选基本不会出大问题。另外如果是面试手撕代码通常顶点规模不会太大两种都能过。但面试官喜欢追问“那你觉得哪种更好”这时候能清晰说出上述对比印象分能上去不少。4.4 一个实际例子看选型差异假设我们要解决一个社交网络好友推荐问题网络中有 10 万个用户用户之间的好友关系大约 20 万条。这种场景有三个特征顶点数大、边数少、大部分操作是“给某个用户推荐其好友的好友”。如果选邻接矩阵光存这个矩阵就需要 100000×100000 个 int换算下来是 40GB 内存直接把虚拟机干挂。选邻接表就很舒服20 万条边在无向图中对应 40 万个边节点内存占用几十 MB完全在可控范围。而且推荐算法做的事情本质上就是获取某个用户的好友列表再遍历每个好友的好友列表这个操作在邻接表中非常自然。这个例子很适合用来理解为什么真实工程里几乎没有用邻接矩阵处理大规模稀疏图的。5. 实现中的常见问题与排查技巧5.1 无向图邻接矩阵的对称性问题无向图邻接矩阵必须是关于主对角线对称的。如果你建图时只设置了 matrix[u][v] 却漏了 matrix[v][u]后面所有依赖对称性的算法全部会出错。我建议在 addEdge 里强制处理对称写入而不是寄希望于调用方记得两边都设置。我自己早期写代码吃过这个亏后来把对称写入封装到 addEdge 内部再也没出过这种低级 bug。5.2 邻接表头插法与尾插法的顺序影响使用链表的邻接表头插法会导致邻接点的顺序是输入顺序的逆序如果后续算法对邻居的遍历顺序有要求比如字典序最小优先用头插法就可能出问题。解决办法有两个要么改用尾插法要么插入后统一对链表排序。vector 实现下顺序天然保持不存在这个问题这也是我日常更推荐 vector 的原因之一。5.3 INF 和 init 值的选择带权图中INF 通常选 INT_MAX 或 0x3f3f3f3f。0x3f3f3f3f 在竞赛圈是常见选择因为 0x3f3f3f3f 0x3f3f3f3f 不会溢出 int大约是 21 亿的两倍刚好接近 42 亿临界值而 INT_MAX 正数必然溢出这会在算法中出现诡异的负数结果。相比之下 0x3f3f3f3f 能提供更大的容错空间。这次在代码里我用了 INT_MAX概念上没问题但实际竞赛代码我更建议直接用 0x3f3f3f3f。5.4 自环和多重边自环指的是顶点到自身的边。邻接矩阵中如果你用 0 表示无边自环其实会导致无法区分“自身距 0”和“存在权值为 0 的自环”。一般我统一规定对角线位置为 0建图时如果 addEdge(u, u) 不去覆盖它这样最省心。多重边则是两点之间有重复的边邻接矩阵处理多重边比较麻烦因为一个位置只能存一个值后面的会覆盖前面的。邻接表就无所谓多 push 一次就行。处理多重边时邻接表可能导致 hasEdge 遇到重复边时逻辑复杂。比如统计路径数量时重复边代表不同的路径那就必须在遍历时把重复边当成多条边处理而不能去重后算一条。5.5 内存越界和动态扩容用 vector 的邻接表几乎不会越界但只要涉及手动链表插边的时候如果忘了 new 节点或者指针操作不对越界问题防不胜防。我的建议是日常竞赛和工程代码优先用 vector只有在面试官明确要求手写链表时才去写手动链表版本。手动链表版写完一定要检查每个节点是否申请了内存释放时也要走一遍链表逐个 delete否则内存泄漏很严重。5.6 我调试图代码时的一点小经验我调试图结构的代码时经常先写一个 print 函数把图“画”出来。邻接矩阵直接打印矩阵方便观察对称性和权值邻接表就按“顶点: 邻居列表”的形式打印出来。肉眼检查一遍很多问题瞬间能定位比单步调试效率高得多。特别是无向图打印出来后发现两个方向不对称那一定是 addEdge 漏写了反向边。6. 后续内容预告与个人经验分享邻接矩阵和邻接表建立好之后紧接着就是遍历、最短路径、最小生成树这些经典算法它们全部构建在这两种存储结构之上。我在实际学习中体会到认真吃透图存储这一层后面学的 DFS、BFS、Dijkstra 会顺畅非常多因为很多困惑都来自“这个操作在这个存储结构下到底是 O(1) 还是 O(n)”这个问题没想明白。我个人更推荐日常代码优先用邻接表配 vector 实现原因有三内存可控、代码简洁、遍历高效。但面试时最好两种都熟练尤其要能把复杂度对比说得清清楚楚。图存储是整个图论的基石这一关迈过去后面就是一片坦途。先把这两个结构写熟再去做题你会发现很多题目读完之后思路自然就浮出来了。