1. 概述
在本篇文章中，我们将介绍一种在有向无环图（DAG）中寻找两个节点的最低公共祖先（Lowest Common Ancestor, LCA）的算法，并分析其时间复杂度。
同时，我们也会对比在无向树和有向无环图中寻找 LCA 的算法差异。本文假设读者已具备图论和大 O 记号的基础知识。
2. 有向无环图（DAG）
有向无环图（Directed Acyclic Graph, DAG）是一种没有有向环的图结构。图中每条边都有方向，表示从一个节点可以到达另一个节点，但不能反向到达。
如下图所示：
在 DAG 中，节点之间可以有多个路径，但不能形成循环。例如，从节点 u 到 v 可以有路径，但从 v 到 u 却不一定存在路径。
需要注意的是，即使一个图是 DAG，其对应的无向图可能仍然包含环。例如下图左侧是一个 DAG，右侧是其对应的无向图：
虽然左侧图中没有有向环，但右侧的无向图中却存在多个环。这是因为无向图中每条边都可以双向通行。
3. 最低公共祖先（LCA）
最低公共祖先（LCA）是图论中的经典问题。通常我们只在有根树中讨论 LCA，但在 DAG 中也可以定义。
LCA 定义：对于两个节点
u和v，其 LCA 是它们的最深公共祖先节点，即该节点是u和v的祖先，并且在所有公共祖先中深度最大。
在无向树中，任意两个节点之间有且仅有一个 LCA。但在 DAG 中，可能有 0 个、1 个或多个 LCA。
3.1 节点的度数（Degree）
在 DAG 中，每个节点有两个度数：
入度（In-degree）：指向该节点的边的数量。
出度（Out-degree）：从该节点出发的边的数量。
如果一个节点的入度为 0，则称为源节点（Source）。
如果一个节点的出度为 0，则称为叶子节点（Leaf）。
例如下图所示：
每个节点旁边标注了入度和出度。节点 0 和 2 是源节点，节点 3、5、6 是叶子节点。
3.2 DAG 中节点的深度
在 DAG 中，一个节点的深度定义为从任意源节点到该节点的最长路径长度。
可以通过广度优先搜索（BFS）来计算每个节点的深度。
例如下图中，节点 5 的深度为 2：
如果移除节点 0，节点 5 的深度就变为 1，因为其只能通过节点 1 或 2 到达。
3.3 DAG 中 LCA 的示例
DAG 中的 LCA 可能有多个。例如下图中：
- LCA(3, 5) 是 1 或 2
- LCA(4, 5) = 2
- LCA(4, 7) = 4（因为 4 是 7 的祖先）
也有可能不存在公共祖先，例如节点 3 和 5 之间就没有 LCA。
4. DAG 中寻找 LCA 的算法
我们介绍一种基于深度优先搜索（DFS）的算法，用于找出 DAG 中两个节点的所有 LCA。
4.1 算法步骤
目标：找出节点 u 和 v 的所有 LCA。
步骤：
- 对节点
u进行 DFS，标记其所有祖先为红色。 - 对节点
v进行 DFS，标记其所有祖先为黄色。 - 找出红色和黄色节点的交集，将这些节点标记为黑色。
- 构建由黑色节点组成的子图。
- 子图中出度为 0 的节点即为 LCA。
示例：
初始图如下：
我们想找 LCA(4, 7)：
DFS 7，标记其祖先为红色：
DFS 4，标记其祖先为黄色：
找出交集，标记为黑色：
构建子图，出度为 0 的节点是 LCA：
最终结果：LCA(4, 7) = 1 或 2。
4.2 时间复杂度分析
- 假设图中只有一个源节点，算法的时间复杂度为 **O(V + E)**。
- 如果图中有多个源节点，则最坏情况下需要从每个源节点开始 DFS，因此时间复杂度为 **O(V(V + E))**。
其中：
V是节点数E是边数
算法主要包括两次 DFS、一次子图构建和一次出度判断，每一部分的时间复杂度均为 O(V + E)，因此整体时间复杂度仍为 O(V + E)。
5. 总结
本文介绍了一种在 DAG 中寻找两个节点所有 LCA 的算法，并对比了无向树和 DAG 中 LCA 的区别。
虽然该算法为暴力解法，但实现简单，适用于中等规模的数据集。若需优化性能，可考虑使用预处理技术（如跳跃指针或二进制提升），但这些方法在 DAG 中实现复杂度更高。
✅ 踩坑提醒：在 DAG 中寻找 LCA 时，注意处理多个祖先路径和多个 LCA 的情况，否则容易遗漏结果。 ⚠️ 注意事项：如果图中存在多个源节点，记得对每个源节点分别执行 DFS，否则可能漏掉部分祖先节点。