企业官网建设流程全解析

图论这块内容真要铺开讲，写一本厚书都不过分。但我翻来覆去观察身边初学者，发现大多数人卡住的点根本不在那些花哨的高级算法，反而在最前面的“存储结构”就没吃透。邻接矩阵写起来最无脑，但一个 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; // 顶点数 vector<vector<int>> matrix; // 邻接矩阵 bool directed; // 是否有向 public: // 构造函数，n 为顶点数，directed 表示是否有向图 GraphMatrix(int n, bool directed = false) : n(n), directed(directed) { matrix.resize(n, vector<int>(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 个顶点，那更是完全不可能。

时间代价方面，几个典型操作的复杂度我整理成了表，方便和后面邻接表做对比：

最亮眼的优势就是判断任意两个顶点之间是否有边：一次数组下标访问就出结果，这个在很多算法里是极大的优势。最致命的短板则是遍历邻接点时必须扫一整行，哪怕这个顶点只有一个邻居，你也要从头检查 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; vector<vector<Edge>> 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 的所有邻接点 vector<int> getNeighbors(int u) { vector<int> 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，直接爆内存。这就是为什么实际工程和大规模图计算中都采用邻接表，或者基于邻接表思想发展出来的 CSR（Compressed Sparse Row）等更紧凑的格式。

上表是核心操作的时间对比。关键在于遍历整个图：用邻接表只需要对每条边访问一次，时间复杂度 O(n + E)；而邻接矩阵不管有没有边，每个顶点都要扫一行，所以是 O(n²)。在稀疏图上，E 远小于 n²，邻接表整体的遍历效率是碾压级的。

不过邻接表也有一个明显短板：想判断两个顶点之间是否存在边，必须沿着链表中顶点 u 的邻接点一个个找，最坏情况下要找 O(degree(u)) 次。如果这个图是一个极端图，某个中心顶点的度非常大，那判断多次之后性能就会下降。

3.4 从邻接矩阵到邻接表的转换

工程里有时候数据源给的是邻接矩阵，但你的算法用邻接表更合适，这时候需要做个转换。转换逻辑很简单：遍历矩阵的每个元素，只要不是 0、不是 INF、不是自环，就往邻接表里添加一条边。

class GraphConverter { public: // 从邻接矩阵构造邻接表，注意 matrix 中的 INF 表示不可达 static vector<vector<pair<int,int>>> matrixToList( const vector<vector<int>>& matrix) { int n = matrix.size(); vector<vector<pair<int,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 vector<vector<int>> listToMatrix( const vector<vector<pair<int,int>>>& adj) { int n = adj.size(); vector<vector<int>> matrix(n, vector<int>(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 实际刷题和工程中的选型建议

我总结经验后一般按下面的规则来选：

这些规则不是绝对的，但根据我的经验，照着选基本不会出大问题。另外，如果是面试手撕代码，通常顶点规模不会太大，两种都能过。但面试官喜欢追问“那你觉得哪种更好”，这时候能清晰说出上述对比，印象分能上去不少。

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 实现，原因有三：内存可控、代码简洁、遍历高效。但面试时最好两种都熟练，尤其要能把复杂度对比说得清清楚楚。图存储是整个图论的基石，这一关迈过去，后面就是一片坦途。先把这两个结构写熟，再去做题，你会发现很多题目读完之后思路自然就浮出来了。