企业官网建设流程全解析

• 教程

图（Graph）是算法面试与工程实践中最高频的数据结构之一。本文以本仓库「9 Algorithms Job Interview/8 图.md」记录的经典面试题为骨架，结合仓库内图论专题文档（图的基础概念、DFS 和 BFS 搜索算法、最短路径算法）展开，系统讲解深度优先遍历（DFS）与广度优先遍历（BFS）的实现原理，并逐一攻破三道高频面试题：蜂窝结构图的最短路径搜索、有向连通图的割点求解、平面上斜率最大直线的查找。读完本文，你将掌握图遍历的代码模板、最短路径算法的选型依据，以及这类面试题的通用分析框架。

一、图的基础：先建立共同语言

面试题中的"图"不是抽象概念，而是由**顶点（Vertex）和边（Edge）**组成的数学模型：顶点代表事物，边表示事物之间的关系。本仓库 5 Graph/README.md 给出了三个必须先说清楚的基础概念：

• 有向图：边有方向，A→B 不代表 B→A，例如关注关系、依赖关系。
• 无向图：边没有方向，A-B 即 B-A，例如朋友关系、交通路网。
• 环：首尾相接的路径。有环与无环直接决定能否使用拓扑排序等算法。

图的工程应用场景非常广泛：司机与乘客的匹配引擎、带优先级的并行任务调度、导航软件的路径规划（路程最短/不走高速/时长最短）、好友关系中的社区发现与精准营销、金融贷后催收中的失联人联系人修复等。理解了"图描述的是关系"这一本质，再看遍历算法就顺理成章了。

二、图的存储结构：面试中先选对容器

同样是图，用不同方式存储，代码复杂度和运行效率天差地别。本仓库 5 Graph/README.md 列出的三种存储方式，对应三种代码写法：

1. 对象和指针：每个顶点是一个对象，持有一组指向邻居的指针。直观但不利于批量计算。
2. 邻接矩阵（二维数组）：graph[i][j]表示顶点 i 与 j 是否有边（或边的权值）。适合稠密图，判断两点是否相邻为 O(1)，但空间 O(V²)。
3. 邻接表：每个顶点维护一个邻居列表。适合稀疏图，遍历某点的所有邻居非常自然，是面试中最常用的写法。

在后续 DFS/BFS 代码中，我们统一采用邻接表（用vector<vector<int>>或List<List<Integer>>表示），这也是 leetcode 与工程中最常见的输入形态。

三、深度优先遍历 DFS：一条路走到底，走不通就回溯

本仓库 5 Graph/DFS 和 BFS.md 对 DFS 的描述非常精辟：以深度为准则，先一条路走到底，直到达到目标；没有达到目标又无路可走时，则退回上一步的状态，走其他路，这便是回溯。DFS 天然用递归实现，底层依赖栈结构（系统调用栈），遵循先进后出。

DFS 的核心是"每访问一个顶点，就标记它已访问（visited），防止重复进入"，这是所有图遍历题的命门：

// 邻接表存储的图，递归 DFS 模板 void dfs(int u, vector<vector<int>>& adj, vector<bool>& visited) { if (visited[u]) return; visited[u] = true; // 处理顶点 u 的业务逻辑（如打印、统计、判目标） for (int v : adj[u]) { dfs(v, adj, visited); } }

DFS 在面试中常用于：全排列与组合枚举、迷宫/连通块求解、拓扑排序的 DFS 实现、以及"是否存在一条从起点到终点的路径"这类可达性问题。它的时间复杂度为 O(V+E)，空间复杂度最坏 O(V)（递归栈深度）。

四、广度优先遍历 BFS：逐层扩散，先进先出

仓库 5 Graph/DFS 和 BFS.md 同样生动地定义了 BFS：在面临一个路口时，把所有的岔路口都记下来，然后选择其中一个进入，再返回来进入另外一个岔路，并重复这样的操作。BFS 用队列实现，遵循先进先出，天然适合"求最短路径/最少步数"——因为 BFS 按层扩散，第一次到达目标节点的层数就是最短距离。

// BFS 模板：队列 + visited void bfs(int start, vector<vector<int>>& adj) { queue<int> q; vector<bool> visited(adj.size(), false); q.push(start); visited[start] = true; int depth = 0; // 记录层数，常用于最短步数 while (!q.empty()) { int size = q.size(); // 当前层的节点数 for (int i = 0; i < size; i++) { int u = q.front(); q.pop(); // 处理顶点 u；若 u 是目标节点，depth 即最短步数 for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; q.push(v); } } } depth++; } }

BFS 的经典应用包括：迷宫最短路径、单词接龙（每个单词是一个顶点，相差一个字母的单词之间连边）、网络爬虫的分层抓取、以及社交网络的"六度分隔"。时间复杂度同为 O(V+E)。

五、最短路径算法：蜂窝图面试题的武器库

关联文档的第一道题"类似蜂窝结构的图，搜索最短路径（5 分钟）"，本质是带权或无权的图上求最短路。本仓库 5 Graph/最短路径.md 列出了可供选型的算法全家桶：

• A* 算法：静态路网中最有效的直接搜索方法，用启发式函数（距离估算值）引导搜索，估算值越接近真实值，搜索越快。适合已知目标点的导航类场景。
• Dijkstra（迪杰斯特拉）：解决图中单源点到其余各点的最短路径问题，要求边权非负，是工程与面试中使用率最高的算法。值得一提的是，Dijkstra 是荷兰计算机科学家，他同时提出了"信号量与 PV 原语"、"哲学家就餐问题"与"死锁"等著名概念。
• Floyd：多源最短路，三重循环动态规划，适合顶点数较少的稠密图。
• Bellman-Ford / SPFA：支持负权边，可用于检测负权环，但效率低于 Dijkstra。

对蜂窝结构图而言，若每个蜂窝之间的代价相同（等价于无权图），直接用 BFS 即可得到最短路径；若移动代价不同，则用 Dijkstra；若已知目标位置且想要更快收敛，则可升级为 A*（启发式可用蜂窝中心点的欧氏距离/曼哈顿距离）。这道"5 分钟"题考查的正是快速选型能力：先判断边的权重类型，再选择匹配的算法，而不是盲目套用。

六、面试题一：蜂窝结构图的最短路径搜索（华为）

蜂窝图可建模为规则网格的变体：每个六边形有 6 个相邻蜂窝，将其抽象为顶点，相邻关系抽象为边，就得到一个无向无权图。求解步骤：

1. 将蜂窝编号映射为顶点，构建邻接表（六边形六个方向的邻居）。
2. 若边权均等，用 BFS 从起点逐层扩散，首次到达终点时的层数即最短步数；BFS 能保证"最早到达即最短"，这是它的理论保证。
3. 若题目给每个蜂窝赋予穿越代价（如地形、拥堵度），改用 Dijkstra：维护一个优先队列，按当前累计代价最小优先扩展，松弛每个邻居的代价。
4. 若在大型地图上追求效率，可叠加 A* 启发式剪枝。

参考仓库中 5 Graph/最短路径.md 的算法清单，可以明确这道题的完整答题路径：无权图 → BFS；非负权图 → Dijkstra；已知目标 + 静态路网 → A*。5 分钟之内能完成选型 + 写出核心循环，即可通过。

七、面试题二：有向连通图的割点（关节点）

题目原文："如果除去此节点和与其相关的边，有向图不再连通，描述算法"。割点（Articulation Point / Cut Vertex）是图论经典问题，标准解法是 Tarjan 算法，核心是用一次 DFS 同时算出两个关键值：

• dfn[u]（发现时间）：DFS 首次访问 u 的时间戳。
• low[u]（回溯值）：从 u 出发，通过 u 的子树中的边以及一条**回边（back edge）**能到达的最小发现时间。

割点的判定规则：

• 若 u 是 DFS 树的根节点：当 u 拥有≥2 个子树时，u 是割点（去掉 u 后各子树互相不连通）。
• 若 u 是非根节点：存在一个子节点 v 满足low[v] >= dfn[u]，即 v 的子树中没有任何边能绕回 u 的祖先，去掉 u 后该子树将被孤立，u 即为割点。

void tarjan(int u, int parent) { dfn[u] = low[u] = ++timer; int childCount = 0; for (int v : adj[u]) { if (v == parent) continue; // 跳过父边 if (!dfn[v]) { // 未访问，是树边 childCount++; tarjan(v, u); low[u] = min(low[u], low[v]); if (parent != -1 && low[v] >= dfn[u]) isCut[u] = true; } else { low[u] = min(low[u], dfn[v]); // 回边，更新 low } } if (parent == -1 && childCount >= 2) isCut[u] = true; // 根节点特殊判定 }

面试时先答"割点定义 → Tarjan 一次 DFS 求 dfn/low → 两条判定规则 → 复杂度 O(V+E)"，即可完整体现对图论经典算法的掌握。注意题目说的"有向图"，工程中还需区分强连通分量（SCC）语境，Tarjan 同样可以处理，只需在此基础上增加栈与"是否在栈中"的判定来求强连通分量。

八、面试题三：平面上 N 个点，求斜率最大的直线

题目原文："平面上 N 个点，每两个点都确定一条直线，求出斜率最大的那条直线所通过的两个点（斜率不存在的情况不考虑），时间效率越高越好"。

这类题的关键是放弃 O(N²) 的暴力枚举，利用排序后的几何性质：最大斜率必然出现在按 x 坐标排序后相邻的两个点之间。

证明思路：任取三个点 A(x1,y1)、B(x2,y2)、C(x3,y3) 满足 x1 < x2 < x3，设 AB、BC、AC 的斜率分别为 k1、k2、k3。可以推导出 k3 介于 k1 与 k2 之间（几何上，AC 的斜率是 AB 与 BC 斜率的加权平均），因此全局最大斜率一定出现在某对相邻点上。

算法步骤：

1. 将 N 个点按 x 坐标排序，复杂度 O(N log N)；
2. 线性扫描一遍，计算每对相邻点的斜率并记录最大值，复杂度 O(N)；
3. 总复杂度 O(N log N)，远优于 O(N²)。

sort(points, points + n, byX); // 按 x 排序 double maxK = -INF; Point a, b; for (int i = 0; i < n - 1; i++) { double k = (points[i+1].y - points[i].y) / (points[i+1].x - points[i].x); if (k > maxK) { maxK = k; a = points[i]; b = points[i+1]; } }

题目明确"斜率不存在（x 相等）的情况不考虑"，因此可直接用上述除法；若要稳健，可在比较前特判dx == 0。这道题考查的是将几何问题转化为排序 + 相邻扫描的思维能力，是典型的高效算法设计题。

九、图的延伸考点：拓扑排序、二部图与最小生成树

面试题往往从遍历延伸出去。本仓库的图论专题还收录了三个高频延伸主题，建议与本文一并复习：

• 拓扑排序：仅适用于有向无环图（DAG），用于任务调度、编译依赖排序。实现方式为 Kahn 算法（不断删除入度为 0 的顶点）或 DFS 后序逆序输出；若过程中出现"删不完"的顶点，说明图中有环。
• 二部图（二分图）：可用 BFS/DFS 染色法判定，是匹配问题（如司乘匹配、婚配问题）的基础。
• 最小生成树：Prim（类 Dijkstra，适合稠密图）与 Kruskal（并查集 + 边排序，适合稀疏图），用于网络布线、连通成本最小化。
• A* / 启发式搜索：详见 5 Graph/最短路径.md，用于游戏编程与分布式计算中的路径规划。

十、面试答题框架总结

回顾 9 Algorithms Job Interview/8 图.md 的全部题目，可以提炼出一套通用的图论面试答题流程：

1. 建图：先明确是有向图还是无向图、有权还是无权，选择邻接表/邻接矩阵；
2. 选遍历：可达性、枚举、连通块 → DFS；最短步数、层次扩散 → BFS；
3. 选最短路：无权 → BFS；非负权 → Dijkstra；已知目标 → A*；含负权 → Bellman-Ford/SPFA；多源全对 → Floyd；
4. 经典算法扩展：割点/强连通用 Tarjan，拓扑排序用 Kahn 或 DFS，匹配用染色法判定二部图；
5. 复杂度的"一页纸"：DFS/BFS 为 O(V+E)，Dijkstra 堆优化为 O((V+E)logV)，Tarjan 为 O(V+E)，排序类几何题常用 O(N log N)。

把 DFS 和 BFS.md 中"DFS 用栈（递归）、BFS 用队列"这一句话记牢，再配合本文给出的 DFS/BFS 代码模板、Tarjan 割点框架与排序几何证明，本仓库收录的这几道图论面试题就能从容应对。建议对照 5 Graph/README.md 的应用场景章节，将每个算法与真实业务（调度、导航、社区发现、催收修复）一一对应，这既是面试加分项，也是工程落地的正确姿势。

• 教程