常用英文

最近公共祖先（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)的节点 $⟺$ 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;
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40

枚举各节点的孩子

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;
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15

计算各节点层次

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;
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15

暴力计算树直径

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;
	}
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22

题解

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。