前言

C++算法与数据结构
打开打包代码的方法兼述单元测试

性质

网格

性质一：四连通、八连通单格图没有自环和重边，故没有一个节点或两个节点的环。
性质二：3个相邻（四连通）的单格只有两情况：一行（列）3个，第一行一个第二行两个，都无法构成环。

连通图（可能有环）

定义一：连通图（可能有环）的层次。选取任意节点root，各节点到root的最短距离就是各节点的层次。显然root的层次是0。
性质一：节点cur的层次是leve，则最短路径的倒数第二个节点一定是leve-1层。否则令其为x层，则cur的层次应该是x+1，与假设矛盾。
操作一：无向连通图转由向连通图。规则：层次小的节点指向层次大，层次相同则节点编号小的指向大的。父节点指向子节点。
性质二：操作一后，root可以访问所有节点。最短路径反向。

树（连通无环无向图）

相关定义

树的层次，距离根的距离，根的层次是0。
树的半径，有根树的最大层次。
树的中心，使得树的半径最小的根。
如果在树中选择某个节点并删除，这棵树将分为若干棵子树，统计子树节点数并记录最大值。取遍树上所有节点，使此最大值取到最小的节点被称为整个树的重心。

性质

性质一：如果有n个节点，则一定有n-1条边。以任意节点为根，初始已访问集只有根，其它节点都在未访问集。选择任意一条一个节点在已访问集的边e，如果不存在,说明已访问集未访问集未连通，与定义矛盾。e的另一个节点一定不在已访问集，否则有环。上述操作每条边，都增加一个节点。故增加n-1个节点，需要n-1条边。
性质二：如果树的直径是d，令两个端点是n1,n2。d是偶数。则树的半径r = d/2。中心就是直径的中点o。一定不存在端点n3到o的距离大于r。否则n1到n3的距离大于d，与假设矛盾。
性质三：如果d是奇数，直径的两个中点都是中心，r = d/2+1。除了n1,n2外，不存在端点n3距离o的距离大与d/2。
总结： r = (d+1)/2
性质三：如果d是偶数，可以有多条直径，这些直径有共同的中心。否则与性质二矛盾。
性质四：如果d是奇数，只能有一条直径，否则与性质三矛盾。

求树的直径方法一：DFS

以任意节点为根DFS，枚举各子树的直径。DFS(cur)返回值：cur子树的最大层次，cur子树的直径。

求树的直径方法二：两轮BFS

以任意节点root，BFS到任意最大层次节点n3，n3 一定是直径的一个端点。令此树的中心是o，某直径端点是n1,n2。o到n3的路径上不可能同时包括n1,n2。不失一般性，节点n2不在o到n3的路径上。由于o是中心，root到非o方向的距离一定小于等于r，否则此节点到n2的距离大于直径，与题设矛盾。root到o方向的最大距离显然是n2。
以n3为根的最大层次，就是直径。

代码

经典DFS

对树进行连通图操作一（如果临接点是父节点就忽略）后，DFS(root)。DFS(cur)的大致逻辑：依次DFS cur的孩子。
性质四：每个节点都会被调用到，调用堆栈就是最短路径。
性质五：每个节点都只会被调用一次。无环，故最短路径只有一条，即只有一个父节点。即每条边只被调用一次。n-1条边，DFS共调用n-1次，加上初始调用共n次。
结论一：经典DFS对树，访问所节点一次。

连通图2（可能有环）

结论一：对有环无向图连通图，经典DFS，会死循环，故要提前退出。经典DFS可以判断是否有环，不失一般性，令某环abcda，且第一次访问的是a，则一定会依次访问bcda。如果临接点是父节点就忽略$⟺$ 忽略cur的前一个节点和后一个节点相同的路径，最短路径显然不符合。故通过最短路径的反向路径一定能访问到a。

经典BFS

经典BFS用vis数组，除重，故不会重复访问节点。
连通区域的所有节点都会被访问到。某节点的leve > 0。则至少和一个leve-1层的节点连通。如果leve-1层的所有节点都访问了，则一定会访问所有的leve层节点。leve=1是成立，因为根初始被访问。根据数学归纳法，任意层的节点都会被访问。

子分类

深度优先搜索汇总
C++算法：广度优先搜索(BFS)的原理和实现

并集查找

C++二分查找或并集查找：交换得到字典序最小的数组
【图论】【并集查找】【C++算法】928. 尽量减少恶意软件的传播 II
【广度优先搜索】【图论】【并集查找】2493. 将节点分成尽可能多的组

最短路径

C++算法：多源最短路径的原理及实现
C++算法：存在负权边的单源最短路径的原理和实现
动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本
【单源最短路 图论】882. 细分图中的可到达节点
暂无题解：
2203

最小生成树

【图轮】【 最小生成树】【 并集查找】1489. 找到最小生成树里的关键边和伪关键边

拓扑排序

【图论】【拓扑排序】1857. 有向图中最大颜色值
【拓扑排序】【 图论】1203. 项目管理
【图论】【树】 【拓扑排序】2603. 收集树中金币
【逆向思考 】【拓扑排序】1591. 奇怪的打印机 II
暂无题解：2050 2392

树

【图论 深度优先搜索】树的直径
换根法
【深度优先搜索】【C++算法】834 树中距离之和
【图论】【深度优先搜索】【换根法】2858. 可以到达每一个节点的最少边反转次数
【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目
树的路径
【深度优先搜索】【树】【状态压缩】2791. 树中可以形成回文的路径数

欧拉路径、欧拉环

【深度优先搜索】【图论】【推荐】332. 重新安排行程
【数学】【深度优先搜索】【图论】【欧拉环路】753. 破解保险箱
【欧拉回路】【图论】【并集查找】765. 情侣牵手
暂无题解：2097

基环树

基环树，也是环套树，是一种有 n 个点 n 条边的图，简单地讲就是树上在加一条边。它形如一个环，环上每个点都有一棵子树的形式。
基环内向树：每个点出度为1（因此每个环上点的子树，儿子指向父亲）
基环外向树：每个点入度为1（因此每个环上点的子树，父亲指向儿子）
基环树的关键就是找到环，可以先把环当作这个无根树的 “根” ，也就是把环当成一个点（先不管它），这样一颗基环树就变成了一个普通的树，然后我们先按照解决普通树的方法对“根”的所有子树依次处理求解答案

【图论】【基环内向树】【广度优先】【深度优先】2127. 参加会议的最多员工数

暂无题解：
2876 有向图访问计数 基环内向树
2360图中的最长环

树上倍增

【树上倍增】2836在传球游戏中最大化函数值
【深度优先】【树上倍增 】2846. 边权重均等查询

扩展内容难道较大

二分图（染色判定、最大匹配）

【广度优先搜索】【二分图】【并集查找】2493. 将节点分成尽可能多的组
【二分图】【二分图最大匹配】LCP 04. 覆盖

割点、割边

很难点，割点周赛、双周赛没出过。 割边出现过一次。
割点原理及封装好的割点类 有四五题应用，不是必选算法