企业官网建设流程全解析

图算法（Graph Algorithms）这个领域，我当初刚接触的时候也觉得很唬人——满屏的顶点、边、邻接矩阵，乍看像数学课本，再看像离散数学的噩梦。但你真把它拆开就会发现，图算法本质上就是一套“高效处理关系”的思维工具：朋友圈的推荐、地图的导航、任务调度的顺序，背后全是图在支撑。这篇系列的第一篇，咱们不贪多，先把“图本身”和“两大最基础遍历手段”彻底吃透。这篇内容适合刚开始学数据结构、或者刷题时总在图论题上卡壳的开发者，也希望帮大家把“看到图题就慌”变成“遇到图题心里有数”。

之所以叫“（1）”，是因为图算法是个特别大的谱系——存储结构是地基，遍历是手脚，后面还有最短路径、最小生成树、拓扑排序、网络流这些进阶套路等着慢慢啃。第一篇文章我会配合实际代码和完整的思路拆解，把“怎么存图”“怎么走图”这两个最底层的问题讲到透。后面几篇咱们再去碰那些更吃建模能力的算法。

1. 图算法的核心思路拆解

1.1 为什么真实世界的“关系”最后都变成图

先帮大家建立一个直觉：图不是什么高深新概念，它就是“一堆点 + 点之间的连线”。生活中几乎一切涉及“对象之间有关系”的场景，都能抽象成图。

• 社交网络：人是顶点，关注/好友关系是边。
• 地图导航：路口是顶点，道路是边。
• 程序依赖：模块是顶点，依赖关系是有向边。
• 电商推荐：用户和商品是两类顶点，购买/点击是边，这就是经典的二分图模型。

所以学图算法第一步要建立的就是建模思维：拿到一个问题，先问自己三个问题——谁是顶点？谁和谁之间有边？边是单向还是双向？这三个问题搞清楚了，剩下的就是套用经典的图算法来求解。

1.2 为什么第一篇要死磕存储与遍历

图算法这个谱系看起来眼花缭乱，但几乎所有高级算法都建在“能快速存取图结构”和“能按规则访问顶点”这两个基本功之上。最短路径算法要不断松弛边，本质上依赖你能够快速找到某个顶点的所有邻居；拓扑排序依赖你遍历每个顶点的入度变化；连通性检测更直接，就是遍历的变体。

如果图存得烂，或者遍历排序出问题，后面每个所谓的高级算法都会跑偏。比如链式前向星存图的顺序一旦写错，Dijkstra和SPFA可能会得到完全错误的结果，而且错误非常隐蔽。我这几年调图算法的Bug，至少一半都出在最基础的存储和遍历上，所以真心建议一步一个脚印打牢。

1.3 这篇适合谁，需要哪些前置基础

这篇不需要高深的数学底子，但希望你有两样东西：一是能把简单的递归和队列代码写顺（理解DFS和BFS的前提），二是知道循环、数组、链表的基础用法。如果你只学过语言基础、还没碰过数据结构，也能看懂，我会在关键位置补充解释。要是你已经刷过几道链表和二叉树题，那这篇对你来说就是“降维阅读”，很快就能上手。

2. 图的存储方式：先摆平“数据放哪”的问题

图的结构必须落到具体的编程语言里才能被算法处理。常见存储手段无非三种：邻接矩阵、邻接表、链式前向星。初学者常听到的“前两种”我已经用得非常多了，链式前向星在竞赛和面试里也经常出现，所以三种我都会讲。

2.1 邻接矩阵：直观但“吃内存大户”

邻接矩阵就是用一个二维数组g[i][j]来记录顶点i和顶点j之间是否有边。有向图、无向图、带权图都能表示，无非是把“有没有边”换成“边的权重是多少”。

// 邻接矩阵：n个顶点，g[i][j] = 1 表示 i -> j 有边 int g[1005][1005]; void addEdge(int u, int v) { g[u][v] = 1; // 有向图 g[v][u] = 1; // 如果是无向图，再补这一行 }

这个方式的优点就是好写好理解，判断任意两点是否相连只需O(1)时间。但缺点也很致命：空间复杂度是O(n^2)。一个 1 万顶点的图，就是 1 亿个格子，就算每个格子用int存，也要 400MB 内存，瞬间爆炸。

所以我的个人经验是：邻接矩阵通常只活在 n <= 1000、且图比较稠密（边数接近 n^2）的场景。稠密图适合用它，因为邻接表在稠密图下反而内存开销大且访问慢。如果拿它处理稀疏图（边数远小于 n^2），那纯粹是拿钱烧水。

2.2 邻接表：最推荐入门掌握的存储结构

邻接表的思路非常简单：对每个顶点，维护一个“邻居列表”。C++ 里最常见的就是vector<int> adj[n + 1]，每个顶点后面的 vector 存它连出去的点。

#include <vector> using namespace std; const int MAXN = 100005; vector<int> adj[MAXN]; void addEdge(int u, int v) { adj[u].push_back(v); // 有向图 // adj[v].push_back(u); // 无向图补上这一行 } // 遍历顶点 u 的所有邻居 for (int v : adj[u]) { // 处理 u -> v 这条边 }

如果是带权图，就把vector<int>换成vector<pair<int, int>>，存“目标点 + 边权”对。这一步我在实际写最短路算法时几乎是默认操作。

邻接表的空间复杂度是O(n + m)，比邻接矩阵省得多，而且找邻居的时间跟邻居数量成正比。对于绝大多数刷题和工程场景，邻接表都是第一选择。如果你拿不准该用什么，默认邻接表基本不会犯错。

2.3 链式前向星：竞赛圈常用的“省内存高手”

链式前向星本质上是用数组模拟链表，把每条边串起来。它不依赖 vector，也不依赖任何标准库容器，纯粹靠head[]、to[]、next[]、edgeCnt这几个数组干活。

const int MAXN = 1000005; const int MAXM = 2000005; int head[MAXN], to[MAXM], nxt[MAXM], edgeCnt = 0; void init() { memset(head, -1, sizeof(head)); edgeCnt = 0; } void addEdge(int u, int v) { to[edgeCnt] = v; nxt[edgeCnt] = head[u]; head[u] = edgeCnt++; } // 遍历顶点 u 的所有邻居 for (int e = head[u]; e != -1; e = nxt[e]) { int v = to[e]; // v 就是 u 的一个邻居 }

为什么需要这个结构？两个原因：一是vector本身有动态扩容开销，在千万级别边的极限场景下能感受到差异；二是在某些嵌入式或老式环境里，vector不可用或内存受限，链式前向星是纯 C 数组实现，通用性极强。

新手第一次看链式前向星通常会被nxt绕晕。我的理解技巧是：想象每个顶点 head 上都挂着一串“边节点”，addEdge 就是往链表头部插入一个新节点，nxt 记录插入前的头部位置。插入顺序是倒着来的，遍历顺序自然也是反的——但这通常不影响正确性。

2.4 存储选型实战参考

拿一道常见题“判断一个无向图是否连通”来说，如果 n 是 1e5，m 是 2e5，用邻接矩阵就得 1e10 个格子（直接内存爆炸），而邻接表只需要约 3e5 级别的基础存储。结论很明确：稀疏大图必须用邻接表或链式前向星。

我在实际刷题时还会再细分：如果是工程代码或 LeetCode 场景，优先邻接表，因为可读性好、不容易写错；如果是打竞赛、数据量 1e6 以上，再切链式前向星。先求正确，再求效率，不要一上来就用花活。

3. 图的两大遍历基石：DFS 与 BFS

存储摆平了，接下来要解决的是“怎么把图完整地走一遍”。这就是深度优先搜索（DFS）和广度优先搜索（BFS）。这两个算法不只是图的基础，也是几乎所有后续图算法的骨架：连通块判断是遍历，二分图判定是遍历，拓扑排序依赖遍历，最短路里也有 BFS 的影子。

3.1 DFS：一条路走到黑，撞墙才回头

DFS 的核心思想是：从起点出发，选择一个邻居继续往下走，走到没有新邻居可走时，回溯到上一个顶点继续选别的路。这是“递归”精神的完美体现。

bool visited[MAXN]; void dfs(int u) { visited[u] = true; // 这里可以处理业务逻辑：统计连通块大小、记录路径等等 for (int v : adj[u]) { if (!visited[v]) { dfs(v); } } }

这个代码看起来简单得过分，但“为什么 mark visited 要放在递归前”值得细想。如果先递归再标记，那么在环状图里会无限循环。visited 数组的本质就是“记录哪些顶点已经走过头了”，避免重复劳动，也避免死循环。

DFS 的递归实现非常符合直觉，但缺点在“层数太深”时会爆递归栈。后面常见问题部分我会专门讲解决方案（手写栈模拟递归）。

3.2 BFS：层层推进，像水波一样扩散

BFS 的核心思想是：从起点出发，先访问所有距离为 1 的顶点，再访问所有距离为 2 的顶点……按层推进，而不是像 DFS 那样一条路钻到底。

#include <queue> bool visited[MAXN]; int dist[MAXN]; // 起点到各点的最短距离（在无权图上） void bfs(int start) { queue<int> q; q.push(start); visited[start] = true; dist[start] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; dist[v] = dist[u] + 1; q.push(v); } } } }

BFS 之所以能求“无权图最短路径”，秘密就在入队顺序上：队列保证先入队的先出队，而每一层都比下一层先入队，所以第一次访问到某个点时，那个点一定是从起点可达到的最短距离。这个性质在 Dijkstra 算法里也有延续，其实就是把“队列里的一定是最短路优先”推广成了“优先队列里的一定是当前最短的”。

3.3 复杂度分析与选择建议

两种遍历的时间复杂度都是O(n + m)，因为每个顶点最多访问一次、每条边最多检查一次。空间上，DFS 最坏递归深度为 O(n)，BFS 队列最多也是 O(n)，差别不大。

那什么时候选 DFS、什么时候选 BFS？我自己的判断标准是：

• 要“找一条可行路径”或者“穷举所有可能”，优先 DFS，因为递归代码写起来直观，且可以配合回溯枚举路径。
• 要“找最短路径”（无权图），优先 BFS。
• 要“按层次处理”，比如输出离起点由近到远的节点顺序，也用 BFS。
• 当图上存在环、要检测是否死循环时，两个都可以，但要格外注意 visited 的时机。

3.4 从遍历延伸出三个高频变体

遍历本身只是基础手段，但它派生出的三个变体非常实用：

连通块统计——一次循环遍历所有顶点，遇到没访问过的就启动一次 DFS/BFS，计数器加一。这就将“找所有连通区域”给解决了。

二分图判定——给顶点染色（两种颜色），要求相邻顶点颜色不同。从起点 DFS，如果发现邻居已访问且颜色与自己相同，就不是二分图。这个思路在找增广路算法里也有应用。

环的检测——在有向图里，如果 DFS 时遇到了“灰色顶点”（当前递归路径上仍在处理中的顶点），说明发现了环。这个技巧在处理依赖关系检测时非常关键。

所以千万别觉得遍历简单就跳过。很多看起来难啃的算法题，本质就是在遍历框架上加一点额外信息维护。

4. 常见问题与排查技巧实录

4.1 死循环：没有正确标记访问状态

症状：程序跑起来就“卡死”，或递归栈溢出。 原因：图里存在环，而你没有在合理的时机标记 visited，或者标记的条件写反了。还有一种常见情况是无向图里回边一直互相访问。

排查方法：先在纸上画一个只有 3 个顶点的环，手动模拟一下你的代码。尤其是无向图的 addEdge，要双向添加，但 visited 也要双向判重。用“先标记再搜邻居”的顺序，基本能避免多数死循环。

4.2 递归过深：栈溢出

症状：n 达到 10 万级别时递归 DFS 直接崩溃。 原因：系统调用栈默认深度有限。

一个最直接的解决办法是把递归栈改成显式栈（用 stack 模拟）。其实这并没有改变遍历顺序，只是把系统的栈换成了堆上空间。

void dfs_iterative(int start) { stack<int> st; st.push(start); while (!st.empty()) { int u = st.top(); st.pop(); if (visited[u]) continue; visited[u] = true; for (int v : adj[u]) { if (!visited[v]) st.push(v); } } }

注意这里先用 visited[u] 做一次检查，因为同一个顶点可能被多次入栈。虽然看起来有点浪费，但实现简单、不容易出错。

4.3 数据量大超时：频繁的 vector 拷贝

有个特别常见的性能坑，就是遍历vector<pair<int,int>>时把 pair 整个拷贝出来。在 C++ 17 之前最好写const auto &e，否则每次循环都复制，数据量一大影响就很明显。

for (const auto &[v, w] : adj[u]) { // 处理 u->v，边权 w }

另一个坑是邻接矩阵在 n=5000 时直接开 5000*5000 的 int 数组可能没问题，但到 n=10000 就会内存紧张。所有“一个疏忽导致内存问题”的现场，基本都是没有提前估算空间复杂度。

4.4 调试思路：肉眼看不透，就让机器输出答案

初学者最常犯的错误是盯着代码干想，而不是输出中间量。我个人调试图算法时的习惯是这样的：

• 先用 n=5 的小图，把 addEdge 全部打出来，逐条核对是否建对了边。
• 在 DFS/BFS 的入口处打印当前顶点和访问顺序，看看遍历顺序是否符合预期。
• 把 visited 数组在关键步骤打印出来，确认没有顶点被漏访问。

这套“小图 + 打印”的组合，我至今还在用，比任何调试器都直观。另一个好办法是直接用在线可视化工具，把图的邻接表或边列表输入进去，让工具把图和遍历顺序画出来，一眼就能看出哪里有环、哪里断链。

4.5 新手避坑速查表

这些坑我和身边的朋友都踩过不止一次。图算法就是这样，思路对了，细节没跟上，照样全盘皆输。所以遇到问题先别怀疑人生，按表查一遍，大概率能救回来。

5. 从入门到实战：学完这篇能干什么

5.1 已经能落地的四个能力

学完存储和遍历，你已经具备了四个能立刻派上用场的能力。

第一，无向图连通块计数。这个直接对应 LeetCode 200 题“岛屿数量”这种类型，把二维网格抽象成图，每个陆地格子就是顶点，相邻陆地就是边，DFS 一跑就完了。

第二，判断无向图是否有环。原理很简单：DFS 时如果从一个顶点出发又回到它自己，那就有环。加上父节点判重就能得到正确的无向图环检测。

第三，无权图最短路径。朋友圈里“你和某个陌生人隔了几层人脉”，用 BFS 就能算出最短隔着几层关系，这个就是社交网络六度分隔里的经典操作。

第四，生成遍历序列。无论是深度优先生成树还是广度优先生成树，后续逻辑都建立在“生成树”之上。比如迷宫生成、选路的骨架逻辑，都跟这里紧密相关。

5.2 下一篇的路线图：现在该往哪走

如果你这篇内容已经吃透，接下来顺理成章的学习顺序是：先学拓扑排序，因为它在有向无环图的依赖分析里非常经典，也依赖 DFS/入度统计；再学 Dijkstra 和 Bellman-Ford 这些最短路算法；然后再挑战最小生成树的 Kruskal 和 Prim。每一步都建在“存储 + 遍历”之上，地基稳了上面才好盖楼。

我自己带新人时，会先让他们用三种存储方法把同一道连通块题各写一遍，再让他们分别用 DFS 和 BFS 做同一道最短路径题。这种“同一个问题，换不同实现”的对抗式练习，比做十道同类题都有效。

5.3 一道适合练手的小题：随时可以开始

举个例子：给你 n 个顶点和 m 条边（无向无权），求图里面有多少个连通块，并且输出每个连通块包含的顶点。

• 思路：初始化 visited 全 false，遍历 1..n，遇到未访问顶点就让计数器加一，并启动 BFS/DFS 收集整个连通块。
• 参考复杂度：O(n + m)。
• 进阶：如果图有 n=1e6、m=2e6，你该用邻接表还是链式前向星？递归是否能承受？这些问题都能顺带检验你的存储选型能力。

练完这道题，你对“存图 + 遍历”的基本功就算是真正落地了。我当年就是靠反复写这类基础题，把眼睛练到“看到关系问题就觉得该建图”的程度。

6. 我的几点体会与建议

图算法是那种“越学越吃建模能力”的领域。很多初学者卡住，不是不会写 DFS 或 BFS，而是不会把问题抽象成图。所以我的个人建议一直是：多问自己“顶点是什么、边是什么”，少问“该用哪个算法”。算法只是工具，建模才是灵魂。

另外别怕写基础题时“重复劳动”。我见过太多人一上来就冲向 DAG 上的动态规划，结果连链式前向星都建不利索，最后回过头来补基本功反而更费时间。这方面我自己的体会特别深：用熟邻接表和 DFS/BFS 两种遍历，再往后看任何图算法都会顺很多。

最后一个我自己常用的调试小技巧：在遍历的入口处打印当前顶点时，顺便输出缩进深度。这样递归调用的层次一目了然，回溯时哪里对不上，立刻就能看出来。这个小习惯帮我省了大量在复杂记忆化搜索里找 Bug 的时间，你们也可以试试。