图的遍历与拓扑排序

• 各排序算法的时间复杂度三档
• 空间复杂度与原地性
• 稳定性与并行友好性

各种排序的时间复杂度：快排最好/平均 O(n log n)、最坏 O(n²)（可用随机化/三取样避免）；归并恒 O(n log n) 但需 O(n) 辅助空间；堆排恒 O(n log n) 且原地，但不稳定；插入排序最好 O(n)、平均/最坏 O(n²)，稳定、原地，适合小规模；计数排序 O(n+k) 且稳定，适用于值域小；基数排序 O(d·(n+k)) 稳定，适用于位/字符串；桶排序均匀分布下期望 O(n)，稳定。空间：快排/堆排 O(1)（快排递归栈 O(log n)）、归并 O(n)、计数/基数 O(k)、桶 O(n+k)。稳定性：快排、堆排、选择不稳定；归并、插入、计数、基数、桶稳定。并行友好性：归并/基数/桶易并行，快排中等的分治并行，堆排/计数/插入较差。

选型要看数据规模、值域、稳定性、内存：通用大数组用快排（随机化防退化）；需要稳定用归并；内存受限用堆排；小规模或近有序用插入；值域小的整数用计数/基数；分布式并行用归并。没有一个算法全优，取舍由场景决定。

• 递归 DFS 与迭代 DFS 的差异
• 显式栈与入栈顺序对遍历顺序的影响
• 深链图栈溢出的规避

递归 DFS 用调用栈隐式保存状态，代码简洁；迭代 DFS 需显式栈模拟，入栈顺序决定遍历顺序（若按邻居顺序入栈，先入栈的后出栈，遍历顺序与递归不同，需注意顺序）。递归版在深链图（如 10^5 层）上会栈溢出，因为系统调用栈深度受限。规避方法：改用显式栈的迭代 DFS，或用非递归方式（如手写栈、迭代加深），显式栈在堆上分配，可容纳很大深度。也可增大线程栈或改用 BFS。

递归栈在系统栈上，深度受限；显式栈在堆上，深度只受内存限制。迭代 DFS 需显式管理"当前节点、下一邻居"状态，入栈顺序与出栈顺序相反，需注意。深链图是树高很大、层数多的情况，递归易爆栈，迭代更安全。

• 分组取中位数（median of medians）的 pivot 选择
• 至少 3n/10 个元素在 pivot 两侧的证明
• 最坏 O(n) 递推式 T(n)=T(n/5)+T(7n/10)+O(n)

线性时间选择把 n 个元素分成 ceil(n/5) 组，每组 5 个，取每组中位数；再递归取这些中位数的中位数作为 pivot。因为每组 5 个，中位数大于等于组内 3 个元素，而约一半组的组中位数 ≤ pivot，故至少有约 (n/5)/2 · 3 = 3n/10 个元素 ≤ pivot，同理 ≥ pivot 的也有 3n/10 个。因此划分后每侧至少 3n/10，另一侧最多 7n/10。递推式 T(n) = T(n/5) + T(7n/10) + O(n)，解为 T(n)=O(n)，因为 1/5 + 7/10 = 9/10 < 1，递推收敛为线性。

选 5 个一组是因为要保证每组至少 3 个 ≤/≥ 组中位数（3/5 占比），总和中位数候选约一半，从而保证每侧至少 3n/10。递推式中 1/5 + 7/10 < 1 保证线性收敛。若每组取 3 个则 1/3+2/3=1 不收敛，故 5 是保证 O(n) 的最小分组。

• 三色标记（white/gray/black）的 DFS
• gray 再次访问即环的判定
• 与 Kahn 算法（入度法）的对比

三色标记法：white 表示未访问，gray 表示在 DFS 栈中（正在访问其子树），black 表示已访问完成。DFS 时节点进入为 gray，从 gray 节点的邻居开始：若遇到 gray 节点，说明存在一条边指向当前仍在栈中的节点，即形成环；若遇到 black 则跳过。DFS 结束后把节点标为 black。gray 再被访问说明存在"回边"指向祖先，这是有向环的标志。与 Kahn 算法对比：Kahn 用入度，不断删除入度为 0 的节点，若删完所有节点则无环；两者都能判环，DFS 三色更直观，Kahn 同时给出拓扑序。

white-gray-black 三态对应 DFS 的生命周期，gray 表示"在该节点尚未完成时又被访问"，即形成环。Kahn 算法若最终处理的节点数 < 总节点数则存在环。三色法适合判环，Kahn 适合同时求拓扑序。

• Introsort 的快排+堆排混合
• 递归深度阈值 2·log2(n) 的意义
• 三取样中位数选 pivot

Introsort 是"快排 + 堆排 + 插入排序"的混合，用于防御快排最坏 O(n²) 退化。它跟踪递归深度，当深度超过 2·log2(n)（快排理想深度约 log2(n) 的两倍）时，说明划分极不平衡、可能退化，此时对剩余区间改用堆排序，堆排序保证 O(n log n)。同时用三取样中位数（取首、中、尾三个元素的中位数）作为 pivot，避免选到极端值，进一步降低退化概率。小规模子区间用插入排序降低常数。总复杂度稳定 O(n log n)。

深度阈值的意义：理想快排深度为 log2(n)，若超过 2·log2(n) 说明划分严重失衡，继续快排可能 O(n²)，故切换堆排。三取样中位数使 pivot 更接近真实中位数，减少不平衡。Introsort 是 C++ std::sort 的标准实现。

• 拓扑排序的 DAG 前提
• Kahn 算法删除入度为零节点的过程
• 循环依赖的检测

拓扑排序把 DAG 的节点排成线性序列，使每条边的起点在终点之前，用于编译依赖解析、任务编排、课程选课等。Kahn 算法：统计每个节点入度，把入度为 0 的节点放入队列，不断弹出节点加入拓扑序，并把它的所有邻接节点入度减 1，若某邻接入度变为 0 则入队。重复直到队列空。若最终拓扑序节点数 < 总节点数，说明存在环（有节点入度永远不为 0），即检测到循环依赖。编译系统/构建工具据此报错提示循环依赖。

Kahn 算法"删除入度为零节点"的过程本质是反复剥掉 DAG 的源点；若能剥完所有节点则无环，否则剩余节点构成环。入度计数 + 队列实现 O(V+E)。

• 事件最早 ve 与最迟 vl 的求法
• 活动最早 e 与最迟 l 及松弛量
• 关键活动、关键路径与多条关键路径

AOE 网顶点表示事件、边表示活动、边权为活动持续时间。关键路径法：先按拓扑序从前向后计算每个事件的最早发生时间 ve(v)=max(ve(u)+w(u,v))；再按逆拓扑序从后向前计算最迟发生时间 vl(v)=min(vl(w)-w(v,w))，汇点 vl 等于 ve。对每条活动 (u,v)，其最早开始 e=ve(u)，最迟开始 l=vl(v)-w(u,v)，松弛量 l-e=0 的活动即关键活动，关键活动组成的路径是关键路径。多条关键路径并存时，总工期取 ve 的最大值（汇点的最早时间），所有关键路径都达到该值。整体复杂度 O(V+E)。

ve 是"最早能到"的贪心取最大，vl 是"最迟必须到"的反向取最小；松弛量衡量活动时间冗余，为 0 表示该活动无冗余、必须按时完成，否则延误总工期。求 ve/vl 各需一次拓扑/O(V+E) 遍历。

• BFS 的队列与 visited 标记
• 每个顶点入队一次、每条边扫描一次
• O(V+E) 时间与 O(V) 空间

BFS 用队列 + visited 标记。每个顶点入队一次（访问一次）、出队一次，出队时扫描它的邻接表，每条边被扫描一次（从其起点出发）。因此总时间 = 每个顶点出队 O(1) + 每条边扫描 O(1) = O(V+E)。空间上，队列最多同时容纳的顶点数不会超过 V，visited 数组 O(V)，故空间 O(V)。队列容量上界为 V（最坏情况 BFS 层含大量顶点），但因为每个顶点只入队一次，队列总入队次数 V，容量上界 ≤ V。

BFS 的复杂度线性于图规模，因为每个顶点和每条边都只处理一次。空间 O(V) 由队列和 visited 数组决定，队列容量上界是 V（不可能超过顶点总数），与邻接表空间 O(V+E) 不同。

• 计数排序的计数数组与累加定位
• 桶排序的分桶与桶内排序
• 各自的适用条件与复杂度

计数排序：当数据范围 [0,k] 已知且较小，用大小为 k+1 的计数数组统计每个值出现次数，再累加前缀确定每个值在结果中的位置，O(n+k) 时间、O(k) 空间、稳定。它要求 k 不能太大，否则空间浪费。桶排序：把数据分成若干桶，把每个元素放入对应桶，桶内排序，再按桶顺序合并。若数据（如均匀分布）使每个桶内元素数接近常数，桶内排序用插入 O(n/k) 总 O(n)，期望 O(n)；最坏所有元素进同一桶退化为 O(n²)。桶排序适用于均匀分布 / 可线性分桶的数据。

计数排序是"用空间换时间"的线性排序，适合值域小且已知的整数；桶排序是"分治 + 桶内排序"，期望线性依赖输入分布均匀。两者都非比较排序，能突破比较排序 O(n log n) 下界。

• 入度为零节点在 DAG 中的存在性
• 反复删除的归纳推理
• 剩余节点成环的判定

DAG 必存在至少一个入度为 0 的源点（若没有，则沿入边反向可无限回溯形成环，矛盾）。Kahn 算法删除入度为 0 的节点后，剩余的子图仍是 DAG，故又产生新的入度为 0 节点，可继续删除。归纳地，只要图是 DAG，就能不断删除直到所有节点处理完，得到拓扑序。若某时队列空但仍有节点未处理，说明剩余所有节点入度都 >0，即剩余子图存在环（否则会有入度为 0 的节点），因此判定存在环。

正确性基于"DAG 必有源点"和"删除源点后仍为 DAG"两条性质。若剩余节点无入度 0 的，则它们的入边都指向环中节点，构成有向环，故剩余节点即环的证据。

• Kosaraju 的两趟 DFS
• 第一次 DFS 的完成时间序
• 反图上逆序 DFS 与 SCC 的关系

Kosaraju 算法：第一趟在原图上 DFS，记录每个节点的完成时间（出栈顺序）；第二趟在反图（所有边反向）上按完成时间从大到小（逆序）DFS，每次 DFS 访问到的连通块就是一个强连通分量。正确性依据：原图强连通分量之间的边构成一个 DAG（SCC 收缩图），第一趟 DFS 中"汇分量"（无出边）先完成，完成时间序为拓扑序的逆序；第二趟在反图上按完成时间逆序 DFS，从原图"源分量"（无入边）开始，而反图上该分量的出边对应原图的入边、并不存在，因此遍历不会跨出该分量，所得连通块恰为一个 SCC。

第一趟确定"分量完成顺序"，第二趟在反图上按逆序 DFS，利用反图把"出边"变"入边"，使从源分量出发只扫描该分量，保证每个连通块恰为一个 SCC。这是 Kosaraju 的核心思想，复杂度 O(V+E)。

• 邻接矩阵的空间 O(V²) 与 O(1) 边查询
• 邻接表的空间 O(V+E) 与遍历优势
• 稀疏图与稠密图的适用场景

邻接矩阵用 V×V 数组存边，空间 O(V²)，判断两点间是否有边 O(1)，适合稠密图；邻接表每个顶点存它的邻居链表，空间 O(V+E)，遍历某顶点的所有邻居 O(deg(v))，适合稀疏图。遍历整图：邻接矩阵 O(V²)，邻接表 O(V+E)。适用场景：稠密图（E 接近 V²）用邻接矩阵省去查找开销，稀疏图（E 远小于 V²）用邻接表省空间。判边频繁用矩阵，遍历邻居频繁用邻接表。

邻接矩阵空间随 V² 增长，V 大时不可行；邻接表空间随边数增长。判边 O(1) vs 遍历邻居 O(deg) 是矩阵优势；邻接表遍历边 O(V+E) 远优于矩阵 O(V²)。工程上图通常稀疏，故多用邻接表。

• BFS 两色染色判定
• 二分图等价于无奇环
• 染色冲突即存在奇环

二分图是能划分成两部分、使所有边都在两部分之间的图，等价于无奇环（无奇数长度环）。用 BFS 从任意点出发染色：起点染 1，邻居染 2，再把邻居染 1，交替进行。若 BFS 过程中某条边两端颜色相同（染色冲突），说明存在奇环，图不是二分图；若全程无冲突，则成功染色，图为二分图。因为二分图可用 BFS 分层染色（奇偶层不同色），冲突必然源自奇环，所以 BFS 染色即可判定。

二分图判定 = 二染色可行。BFS 按层染色，天然把奇偶层分开；若一条边两端同层（同色），则存在从该层回来的奇数长度路径，构成奇环。故染色冲突等价于奇环存在，等价于非二分图。

• 重复边（平行边）的处理
• 有向图与无向图的方向处理
• 自环的正确处理

常见误区：1）重复边：无向图建边时若重复添加，邻接表会存多条相同边，遍历时可能重复访问，需判断是否去重；2）方向：无向图建边要双向（u→v 和 v→u），有向图只加一条，漏加或误加会导致遍历错误；3）自环：节点到自身的边，在无向图中只需加一次（或按约定），遍历时需注意 visited 判断避免重复计数；4）visited 标记时机：应在入队/入栈时标记而非出队时标记，否则可能重复入队。这些误区会导致遍历结果错误或复杂度偏高。

手写邻接表要理解图的抽象（有向/无向、允许重边/自环），并按题目要求正确建边。visited 标记时机是迭代遍历常见的坑：入队时标记可避免重复。

• 稳定排序的定义
• 多级排序的递推顺序
• 稳定排序保证次级排序序

稳定排序保证"排序后相等元素的相对顺序不变"。多级排序中，先按次要键排、再按主要键排，若用稳定排序，则第二次排序后，主要键相同的一批元素仍保持第一次（次要键）的相对顺序，从而保证"同主要键内按次要键有序"。例如先按年龄排、再按部门排，稳定排序保证最终每个部门内的人仍按年龄升序；若用不稳定排序，部门内年龄顺序会被破坏。因此多级排序应从次要键到主要键依次排，且用稳定排序。

稳定性是"保留前序排序信息"的关键。多级排序的正确顺序是"从最次要键开始，到最主要键"，每步用稳定排序，最终结果对主要键有序且同键内保持次要键序。这在数据库 ORDER BY 多列、Excel 排序等场景很实用。

• Tarjan 的 low-link 值
• Gabow 的两栈（路径栈 + 辅助栈）
• 辅助栈弹出与 SCC 的界定

Tarjan 用 dfn 与 low 值识别 SCC。Gabow 与其原理相同但用两个栈代替 low 值：路径栈 path 存 DFS 路径，辅助栈 aux 存"进入某分量顶部"的节点标记。DFS 时，每遇到一个可作为新分量的节点（其后继无法回到更早的祖先）就压入 aux；当某节点 v 的所有子树处理完，其后继都不能回到 v 之前，则 aux 顶到 v 之间的节点恰好构成一个 SCC，弹出该区间并输出。辅助栈的弹出位置由"竖向传播的根"决定，弹出一段即一个 SCC，无需显式计算 low 值，但本质与 Tarjan 的 low 判定等价。

两栈法把"low 值比较"转化为"栈顶区间判断"，原理仍是"能回到祖先者同分量"。辅助栈标记了各分量的"根候选"，弹出时界定的区间恰是一个 SCC。复杂度同为 O(V+E)。

• dfn 与 low 的定义
• 树边与回边对 low 的影响
• 根（low==dfn）的判定

Tarjan 给每个节点 dfn（访问序）和 low（能回溯到的最早 dfn）。low[v] 由三部分取最小：自身 dfn[v]、树边 to 的 low[to]（子树内能回溯到的最低 dfn）、回边 dfn[to]（指向栈中祖先的边）。若 low[v]==dfn[v]，说明 v 无法通过子树或回边回到更早的祖先，v 是某个 SCC 的根，此时栈顶到 v 之间的节点构成一个强连通分量，全部弹出。根的判定特殊在于：只有 low==dfn 时才输出分量，而普通节点 low<dfn 表示它属于更高层的分量，不能单独输出。

low 值衡量"能回溯到的最早可达节点"，若某节点能回到祖先，则它和祖先在同一 SCC；只有无法回到更早祖先的节点才是分量根。low 公式综合树边回溯与回边直达，能正确识别所有 SCC。

• 稀疏图的邻接表表示
• 社交网络的邻接表应用
• 邻接表的内存与遍历优势

邻接表为每个顶点存储其邻居列表，空间 O(V+E)，适合稀疏图（E 远小于 V²）。社交网络是典型的稀疏图：用户间关系远少于全连接，用邻接表仅存实际好友关系，内存占用低。遍历某用户的邻居（查看好友、点赞传播）只需 O(deg(v))，比邻接矩阵 O(V) 快得多。因此邻接表广泛应用于社交网络、网页链接、推荐系统等稀疏图的建模，配合 BFS/DFS 做社区发现、影响力传播、最短路径等。

邻接表把内存与遍历成本都与"实际边数"对齐，而非顶点数平方，是稀疏图（现实世界图）的最佳选择。社交图谱中点度分布近似幂律，邻接表能灵活处理度数差异大的节点。

• 邻接表的基本数据结构
• 头插与尾插的区别
• 加权边的表示（Edge 类）

邻接表常用数组（或 List）的每个元素对应一个顶点，存该顶点的邻居链表。无向图建边时双向添加（u 加 v、v 加 u），有向图只加一条。尾插（append 到链表末尾）保持输入顺序，头插（插到头部）更高效（O(1)）但遍历顺序颠倒。加权边用节点结构存储 neighbor 和 weight 两个字段（如 Edge 类），或存为 pair。建图时注意数组大小（顶点数）、下标从 0 还是 1 开始、以及是否需去重，避免越界与重复。

邻接表头插 O(1) 但改变邻居顺序，尾插保持顺序但可能 O(deg)；对只遍历不要求顺序的算法头插即可。加权边必须携带权重，常用 Edge 类或二维数组。正确建图是图算法正确的前提。