常用英文
最近公共祖先（Lowest Common Ancestor，简称LCA）
posterity，英语单词，主要用作名词，作名词时译为“子孙，后裔；后代”。
什么是深度优先搜索
深度优先搜索，Depth First Search, 简称DFS。它从初始节点出发，按预定的顺序扩展到下一个节点，然后从下一节点出发继续扩展新的节点，不断递归执行这个过程，直到某个节点不能再扩展下一个节点为止。此时，则返回上一个节点重新寻找一个新的扩展节点。如此搜索下去，直到找到目标节点，或者搜索完所有节点为止。
通俗的说：
每个节点都有选择类表，如果列表为空，则结束。否则依次DFS(x) , x ∈ \in ∈ 选择列表。节点中间的数字就是DFS序（时间戳）
某个节点为cur，它的任意祖先节点为anc，任意后代为pos。
深度优先有如下性质：
一，当DFS(cur)没有开始执行时，DFS(pos)一定没有开始执行。
二，当DFS(cur)执行结束时，DFS(pos)一定执行结束。
三，如果cur是长子节点，则DFS(cur)结束后。DFS(anc)正在执行，DFS(pos)已经执行结束。其它节点，都没有开始执行。
四，当前节点，可能是后代节点的前置条件，比如： 求层次(leve)。后代节点也可能是当前节点的前置条件，如：求后代数量。
五，DFS(cur)时的DFS序为time1 ，结束时的DFS序为time2。 则DFS序为[time1,time2)的节点 ⟺ \iff ⟺ cur及cur的后代。
经典应用
无向图的DFS。需要cur节点parent，当next == parent 是忽略，否则无需循环{cur,parent,cur,parent ⋯ \cdots ⋯ }
有向图，一般不需要，因为大部分情况是无环图。
封装类
枚举
CEnumNeiBo 枚举邻接点，如果有环，以第一次访问为准。CEnumChild 枚举孩子、无环、无向图。
class IDFSEnum
{
public:
virtual void Enum(int cur, std::function<void(int)> fun) =0;
virtual int NodeCount() = 0;
virtual void Clear() = 0;
};
class CEnumNeiBo : public IDFSEnum
{
public:
CEnumNeiBo(const vector<vector<int>>& vNeiBo) :m_vNeiBo(vNeiBo) {
Clear();
}
virtual void Clear() override{ m_vVisit.assign(m_vNeiBo.size(), false); };
protected:
virtual void Enum(int cur, std::function<void(int)> fun) override {
m_vVisit[cur] = true;
for (const auto& next : m_vNeiBo[cur]) {
if (m_vVisit[next]) { continue; }
fun(next);
}
}
virtual int NodeCount() { return m_vNeiBo.size(); };
const vector<vector<int>>& m_vNeiBo;
vector<int> m_vVisit;
};
class CEnumChild : public IDFSEnum
{
public:
CEnumChild(const vector<vector<int>>& vChild) :m_vChild(vChild) {}
protected:
virtual void Enum(int cur, std::function<void(int)> fun) override {
for (const auto& next : m_vChild[cur]) {fun(next);}
}
virtual int NodeCount() { return m_vChild.size(); };
virtual void Clear() override {};
const vector<vector<int>>& m_vChild;
};
枚举各节点的孩子
class CDFSChild
{
public:
const vector<vector<int>>& DFSChild(IDFSEnum& dfsEnum, int root) {
dfsEnum.Clear();
m_vChild.resize(dfsEnum.NodeCount());
DFS(dfsEnum, root);
return m_vChild;
};
protected:
void DFS(IDFSEnum& dfsEnum, int cur) {
dfsEnum.Enum(cur, [&](int next) {m_vChild[cur].emplace_back(next); DFS(dfsEnum, next); });
}
vector<vector<int>> m_vChild;
};
计算各节点层次
class CDFSLeve
{
public:
vector<int>& DFSLeve(IDFSEnum& dfsEnum,int root) {
dfsEnum.Clear();
m_vLeve.assign(dfsEnum.NodeCount(), -1);
m_vLeve[root] = 0;
DFS(dfsEnum,root);
return m_vLeve;
}
protected:
void DFS(IDFSEnum& dfsEnum, int cur) {
dfsEnum.Enum(cur, [&](int next) {m_vLeve[next] = m_vLeve[cur] + 1; DFS(dfsEnum, next); }); }
vector<int> m_vLeve;
};
暴力计算树直径
class CDFSForDiameter
{
public:
int DFSDiameter(IDFSEnum& dfsEnum, int root) {
dfsEnum.Clear();
m_iRet = 1;
DFS(dfsEnum, root);
return m_iRet;
}
protected:
int m_iRet = 1;//记录树的直径,0个节点的树会出错。
int DFS(IDFSEnum& dfsEnum,int cur) {
int left = 0;
dfsEnum.Enum(cur, [&](int next) {
auto right = DFS(dfsEnum,next);
m_iRet = max(m_iRet, left + right + 1);
left = max(left, right);
});
return left + 1;
}
};
题解
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。