数据结构笔记——树和图（王道408）（持续更新）

前言

本系列笔记分为三篇，系统总结了王道408数据结构课程的内容，加入了大量个人思考。

数据结构笔记——线性表、栈、队列、串（王道408）
数据结构笔记——树、图（王道408）
数据结构笔记——查找、排序（王道408）

数据结构的笔记相比于其他3门，笔记的重要性要低很多，毕竟对于选择408的同学来说，大二时候应该有足够的时间学习，所以基础是比较好的，再加上csdn上一大堆数据结构和算法的帖子，我再重复造轮子也没啥意思了。

所以我这篇文章不打算写的很细节，就是单纯地把思路提纯出来，并附上自己的理解，再搭配思维导图就行了，而不去记录过于细节的知识。

树（重点）

树的数据结构

定义

除了根节点，任何节点有且仅有1前驱：

1. 根节点：0前驱，n后继
2. 分支节点：1前驱，n后继
3. 叶节点：1前驱，0后继

节点之间的关系：

1. 祖先/子孙：所有有血缘关系的前辈/子孙。注：你叔和你没血缘关系，所以不算祖先
2. 父亲/孩子：直接血缘关系的上下层节点
3. 兄弟/堂兄弟： 在树的同一层，区分点在于是否是同一个爹生的

术语：

1. 高度：从下往上数，叶节点是1
2. 深度：从上往下算，根节点默认是1
3. 节点的度：分支数
   • 在图里要分入度出度，树的入度确定，所以不讨论
   • 叶节点度=0，非叶节点度≠0
4. 树的度：最大的节点度

性质

1. 每个度代表分出一个节点，所以n个度即分出n节点，考虑到1个根节点，即n+1个节点。
   • 不需要考虑重复，因为每次分支都是实实在在的，后面再分支也不会影响现在已经分出去的节点
2. 度为m的树是m叉树（树度≤m）的特例
   • 树度=m，至少有一个为m度节点，因此至少有m+1个节点
3. 给定深度/高度后的最多节点数。满度：m叉树，满度情况下，每层节点数是以1开头，m为比的等比数列，总和用等比数列求和
4. 给定深度/高度后的最少节点数
   • m叉树，度没有下限，为了满足高度，极限情况需要有一条线，即h个节点
   • 度为m的数，在满足高度的一条线前提下，还要找一个节点额外分（m-1）个节点，所以h+m-1
     
5. 给定节点数，求最小高度。列不等式，下界

二叉树的数据结构

定义

二叉树是一个纯粹的递归定义，二叉树只有两种状态：

1. 空树
2. 非空：根节点+左右子树
   • 左右子树也可以是空树或者非空
   • 左右之分，代表有序

具体来讲，有5种细分状态：

1. 空
2. 叶节点：度=0
3. 单个孩子的节点：度=1
4. 两个孩子的节点：度=2

通过度就可以区分节点的状态，后面说的所谓度为几，其实就是说xx状态的节点。

完全二叉树：节点是从上到下，从左到右连续排列的，没有空隙
满二叉树：最后一层是满的完全二叉树

直接特性就是，如果n层有节点，代表n-1层一定是排满的，且n层这个节点左边也是排满的

接下来解读二者差别：

1. 度分析
   • n+1层无节点，因此n层所有节点度=0
   • 完全二叉树
     • n-2层开始往上都满度。n层有节点，说明n-1层满，从n-2层开始往上都是满度（2）的
     • n-1层可能有0,1,2三种度，从左到右，先是一排2度，然后仅有一个1度，然后全是0度。如果有两个1度，就会打破完全二叉树连续排列的定义。
     • 总结，n-2层往上全满，n-1层可能有任何类型节点，n层全是叶子
   • 满二叉树，n层满，因此n-1层往上都是满度
2. 父子关系。
   • 左孩子2i，右孩子2i+1
   • 父亲是孩子除以2，向下取整
3. 结合1,2来定位完全二叉树的1度节点。
   • 1度节点肯定是最后一个孩子的父亲，直接除二向下取整，1度和2度节点都是分支节点，0度节点是叶节点。

性质

二叉树推导：

1. n0=n2+1
   • 推导：n=n0+n1+n2（节点总数），且n=n1+2n2+1（节点总数=总度数+1），减一下可得结果
   • 直观理解：度=1的节点不影响叶子结点数量。度=2的节点，每分叉一次，都是浪费一个叶子结点，同时生成两个叶子结点
   • 即，最开始有1个叶节点（根），每分叉一次（2度节点），就会多一个叶节点，因此最后n0=n2（分叉次数）+1（根）
2. 2,3都是等比数列性质

完全二叉树推导：

1. 推导公式，要从≤或者≥哪里去推导。因为上下界有两种理解方式，所以就会有两种结果：
   • $2^{h-1}-1<n\le 2^h-1$，用右边的小于等于就可以推导出一个公式
   • $2^{h-1}\le n＜2^h$，用左边的大于等于也可以推导一个h公式
2. 给定完全二叉树的n，可以彻底确定其形状，节点的数量，类型，分布，下面有三个方程，联立就可以算出结果：
   • n=n0+n1+n2
   • n0=n2+1
   • n1只可能是0或者1，只需要看n奇偶就可以。n如果是偶数，最后这个节点是独生子，即其父为1度节点，n1=1；如果n是奇数，说明这个节点有亲兄弟，场上就不存在1度节点了。

纵观这些公式，关键在于几点：

1. 完全二叉树对等比数列的认知
2. 对完全二叉树结构的认识，第n-1层的度数排列，左2，中1，右0，分支带来的节点变化（对应公式）

储存结构

顺序存储，先说完全二叉树：

1. 首先是，第一个元素不储存，这样就可以把位序和下标对应，简化代码和逻辑。
2. 其次就是找父子，判断层次，这些都是数量关系
3. 然后就是判断节点状态，是0度还是1,2度？
   • 12度的区分这就需要结合n来判断，看看其左孩子，右孩子的位序是否越界n
   • 0度判断要先找到0度2度的分界点，即n/2向下取整，左边是2，右边是0。至于这个节点本身，就要区分12度了。

一般的二叉树，如果在数组中连续存储，就会破坏位序关系
如果按位序存储，仍然有很多不便。一来节点状态无法通过n来判断了，只能新增bool变量，二来还会浪费空间，因此二叉树其实一般是用链式结构储存的。

链式储存：

假设有n个节点，那么总共就有2n个链域，除根节点外每有一个节点就会有一条边，每条边都会占用一个链域，总共n-1条边
因此就会剩下2n-（n-1）=n+1个空链域
这些链域可以用来逆向构建线索二叉树

在只有两个链域的情况下，找父节点要从根节点遍历，比较麻烦，因此要频繁查找父节点的话，还应该加入parent链域。

二叉树算法

先中后序遍历

所谓的先序，其实是先根序

层次展开法

我此前是直接在脑子里去遍历，就是在脑子里模拟递归调用栈，虽然也能做，但是费脑子，不如下面的省劲：

逐层去展开，就像是前面从中缀转前缀/后缀的时候
先留出括号，然后将未处理部分在下一层继续展开

二叉树，可以理解为一个代表中缀表达式的结构，分支节点上是运算符，叶节点是操作数，树结构代表了运算先后顺序

对其进行先序遍历，就是把符号放在前面，也就是前缀表达式，后序就是后缀表达式。注意，中缀的时候，需要加括号，之前我也写过一道这个算法题，我记得大致是从层次里提取括号。

递归模拟法

至于递归代码，就很简单了：

T!=NULL是判断条件，如果空就不操作，非空就进行遍历。
visit代表对根结点的访问
根据前中后序遍历，可以在对左右孩子的递归调用之间找到一个合适的位置。

有的考题会让你分析递归过程，前进回退，其实无论是哪种遍历，路径都是一模一样的，每个节点都被经过三次（算上左右孩子为空的情况）：

1. 刚到这个节点
2. 从左边返回
3. 从右边返回

前中后序遍历的区别就在于，是在哪一次经过的时候访问节点，先序就是在1，中序就是在2，后序就是3，到时候画一条路，然后脑补在该访问的时候写出节点就好。

需要注意，NULL孩子也算孩子，即使孩子为空，也要象征性地访问一下，一来是程序逻辑，二来是为了你好写顺序。

层次遍历

思路很简单，就是用队列。

访问当前一层的时候，把下一层可以加的孩子都按序加进来。
直到最后队列为空

遍历序列逆向构造二叉树

前/后序+中序的逻辑一样，都是先找到根节点
然后去中序里面切分，对应回去将前/后序序列分割

如此就完成了一段的切分，然后递归地去切分剩下两段，类似于快排的感觉。

层序的话，仍然是利用层序找根节点，然后用中序切割。

层序找根节点，是从前往后，以层为单位去找的，那么每层要考虑几个根节点呢？这就得看中序的切分情况了
中序切分后，该层所有根节点，只要有孩子就+1，最终数量就是下次要考虑的根节点数目比如下图：

1. D
2. AB（D中序切分后，左右非空，因此一个节点分2个）
3. EFCG（AB中序切分后，AB节点左右都非空，因此是2+2）
4. HI（EFCG中序切分后，只有CG有子节点，C和G各有一个，因此是1+1）

又以下图为例：

1. A
2. B（A因为中序左边没有，因此是1）
3. CD（B中序左右都有，因此是2）
4. E

线索二叉树（难点）

这一部分是难点，需要深入理解先中后序的逻辑，灵活利用展开的方法去分析，并且还要熟悉在树上遍历的过程。

定义

线索化的本质

首先这里区分一下，这里说的前驱和后继，都是特指在中序遍历序列中的前驱后继，而不是二叉树上的前驱后继

一般情况下，我们遍历一颗二叉树，一定要从根节点开始，否则后面会有一些节点漏掉。比如下图，要想找到p的（中序）前驱和（中序）后继，要用q和pre指针进行一前一后的移动，从根节点开始把整个树遍历一次。

假如有一种情况，需要反复利用中序遍历序列，那么每次都从根节点获取中序遍历序列就很麻烦，于是有人直接利用线索二叉树，把中序遍历序列的信息储存到空链域里，这就是线索化的本质。姑且不论线索如何生效，你只知道利用线索就可以从中序遍历序列中的一个节点开始遍历出后面完整的中序遍历序列。

在上图中，完全可以从B开始，就可以依次遍历BEAFC，不用担心丢了某个节点。

按这个思路，按照线索可以直接遍历中序，加速遍历，甚至线索里本身就存着p在中序序列的前驱后继，你直接输出就行。

这就是线索化的意义，下图为线索化的过程，先遍历出一个中序序列，然后把中序序列前驱后继的信息填充到线索里，左对应前驱，右是后继，有n+1个空链域，因此有n+1个线索。为了区分链域储存的到底是线索还是孩子，需要用两个tag区分。

此处疑惑的点是，有的节点有后继但是没有链域存放后继，这个后面有解决办法。你姑且知道，有线索，就可以从中提取中序的前驱后继

下图为标准的储存结构图像，先序和后序的思路同中序。

二叉树线索化

二叉树线索化，本质就是把这个节点的左孩子链接到中序前驱，右孩子连到中序后继。

因此当务之急是在中序遍历的过程中，维护前驱和后继信息，其实在最开始已经说了，就是用一个pre指针（全局变量），pre是q的前驱，而q是pre的后继，此乃相对性

已经有信息了，那么在visit过程中就直接修改链域就好

1. 判断条件
   • q一定非空，所以只需要判断左链域
   • 而pre可能空，所以还要都一个非空判断。
2. 添加线索
   • 如果链域为空，就修改为对应的线索
   • 记得把tag同步修改。
3. 最后修补
   • 注意到，最后一次visit，q指向尾部，而pre指向倒数第二，也就是说，q的后继是没有考虑的
   • 因此在程序执行完毕后，还要额外判断pre的右链域，全局变量的好处在此处体现。
   • 有些写法是直接让pre右链域=NULL，pre->rtag=1的，这种也没错，因为在中序遍历里，如果这个节点有右孩子，那这个节点就不是最后一个节点了。但是在后序遍历里面，最后一个visit的节点有可能有右孩子，所以就不能这么个判断。总的来说加判断可以涵盖一切情况，因此就统一加判断，只有前序和中序情况下，才可以不判断。

下图为具体的代码，左上角为主函数：

1. 初始化pre=NULL，
2. 然后线索化，q就是从T开始
3. 最后再善后pre右链域

先序线索化基本照搬，就是在先序遍历的过程中，去添加线索。

但是这里有一个bug，对于没有左孩子的节点（比如D），按道理说，添加完线索以后就没他什么事情了，而且访问过以后，也没有机会再访问第二次了。

但是在先序线索化过程中，会先visit，添加前驱线索，之后左孩子的链域就非空了，此时如果还按照原有逻辑，就又会跳回到前驱，开始进行遍历，这就是一个死循环。

破解办法很简单，本来左孩子的链域应该是空的，此时有了指针，可以用tag来判断原来是否为空，只有tag=0（原来非空，真正的有左子树），这才能跳转到左孩子的节点。

线索二叉树中找前驱后继

总评：这一章是线索二叉树的核心难点，尤其是三叉链表情况下的别扭题。

我的建议是，一切的一切，要抓准先序中序后续的本质特性，比如先序就是“根左右”，你到时候现场推导判断条件，灵活且不容易出错。

中序

之所以用中序为例子，是因为中序线索化是完美的，“左根右”，有根节点，找前驱就去左孩子里面找，找后继就去右孩子里找，而先序只能找后继，后序只能找前驱。

先说后继，判断rtag，两种情况：

1. rtag=1，证明右链域是线索，那么直接用线索
2. rtag=0，证明右链域有右子树，那么就需要找到右子树中序遍历序列中最左边的节点
   • 其实就是右子树左下角的节点
   • 具体就是下面FirstNode函数，一直找左孩子，直到没有左子树
   • 因为此时已经线索化了，终止条件所以不再用NULL，而是用ltag判断

既然能找到中序后继，一次快速的中序遍历就很简单了：

1. 先通过FirstNode，找到第一个节点
2. 然后从第一个节点开始，不停找后继，直到遍历完毕

这种方法的特色在于，找后继过程中，可以通过线索大大加速遍历速度，复杂度为O（1）

中序线索的前驱思路和后继一样，整体是镜像的感觉，左变右，有前驱线索就用线索，没有就找左子树右下角节点。

LastNode函数，就是一直去找右孩子，直到rtag=1

因此也衍生出逆向遍历中序线索的方式。

先序

中序最为规整，符合直观，先序后序就比较别扭，容易混乱，本质上是先序会浪费链域，比如本来就有左孩子，然后你右链域如果为空，还要再指向左孩子，这就是浪费，这也就是其前驱后继只能二选一的原因，浪费了信息，自然就无法实现全部的功能。

回归正题，先序找后继，后序找前驱，反之则不一定，容易记混，而且实际生产也没用，要我说还不如深入理解，临场画图，更加保险

先序找后继，本质思路就是“根左右”：

1. rtag=1，有线索，用线索
2. rtag=0，无线索，即有右孩子，此时用“根左右”思考
   • 有左孩子，则左孩子为后继
   • 无左孩子，则右孩子为后继

前驱不一定有，逻辑如下：

1. ltag=1，有线索，用线索
2. ltag=0，有左孩子
   • 问题在于，遍历序列是“根左右”，以根开始，无论你找左孩子还是右孩子，先序情况下只要你找的是孩子，你顶天了只能是后继
   • 因此ltag=0的时候只能从根开始遍历，用不了线索

但是很明显，这里可以加考点，如果用三叉链表，允许找到父节点，那么事情会有转机，当然也特别麻烦（为考而考），一切的关键是理解先序遍历的根左右思想

1. ltag=1，用线索
2. lgat=0，先找父节点
   • 情况1：p无父节点，则无前驱
   • p有父节点，有前驱，然后进行判断。先看上层结构：“根左右”
     • 情况2：p是左孩子，则为“根（根左右）右”，则父（根）节点为前驱
     • p是右孩子，p处在序列中“右”的位置，则要判断“左这一部分的情况”
       • 情况3：“左”为空，即“根（）（根左右）”，那么父节点当前驱
       • 情况4：“左”非空，即“根（左子树）（根左右）”，那么就要在父节点左子树里，走一遍先序遍历，用其最后一个节点当前驱。这一步要求你对先序遍历极其熟悉（可以简化，有右找右，没右找左，右左都没，就是最后一个）

说实话真的有点大冰，建议直接画图思考，把这几种情况都画出来，这么多背不会的。

后序

后序线索，只能找前驱，如果要找后继，同样麻烦。

后序前驱：

1. ltag=1，用线索
2. ltag=0，则有左孩子，利用“左右根”寻找前驱
   • 有右孩子，则为“左（左右根）根”，因此右孩子就是前驱
   • 无右孩子，则为“（左右根）（）根”，因此左孩子就是前驱

后续后继，因为是“左右根”，无法通过左右子树找根的后继，同样需要三叉链表配合：

1. rtag=1，用线索
2. rtag=0，先找父节点
   • 情况1：p无父节点，则无后继
   • p有父节点，此时上一层为**“左右根”**，我们这一层仍然需要先定位
     • 情况2：p为右孩子，则为左（左右根）根，因此p的后继就是父节点
     • p为左孩子，因此要判断“右”这一部分是否存在
       • 情况3：父节点无右孩子，则为“（左右根）（）根”，p的后继是父节点
       • 情况4：父节点有右孩子，则为“（左右根）（左右根）根”，p的后继是父节点右子树后序遍历序列中第一个输出的节点（简化逻辑就是，有左就左，没左找右，没左没右，就是后继）

再次吐槽，真的是有大冰，建议推导两三次，就不用记了，直接临场速推。

树算法

储存结构

树的难点在于，因为度是没限制的，所以链域给几个是不确定的，树的所有结构都是为了解决这个核心问题而创造的。

最开始双亲表示法的思路：

1. 出度不确定，入度确定啊
2. 因此采用逆向指针，链域=1，非根节点就可以保证有且只有1个前驱

因为结构比较简陋，因此一般用数组存，也只能用数组存，因为找孩子节点只能用遍历实现（查）

增删如何实现呢？增，在最后增加元素就行，删就是直接把链域抹-1就行，但是更好的方法是把最后一个元素挪到这个位置覆盖，因为这样可以缩减数组长度，提高遍历速度。

双亲表示是纯数组表示，而孩子表示法是数组+链表的混合存储结构（其实就是图的邻接表结构用在了树上）

延续链域不确定的思路，解决不确定的数量自然会想到链表，因此用一串链表表示一个节点的所有孩子：

1. 数组元素储存节点本身
2. 链表元素储存孩子的位置信息。
   • 链表元素可以看做是两类指针的结合体，孩子下标算一个指针，指向具体元素，而链表next也是指针，指向下一个链表元素。

这个结构其实是图的结构，优劣势这里就不讲了，简单来说就是找孩子简单找双亲难。

个人认为，孩子表示法可以和双亲结合，只需要加一列双亲指针就好，这是树比较完美的储存办法

最后就是孩子兄弟表示法，纯链式存储。

纯链式存储怎么能解决链域不定的问题呢？换个思路，链域里不储存所有孩子的指针，而是储存一个孩子+右兄弟，这样链域就固定为两个了，可以用二叉树储存了。

从视图来看，新的二叉树就是就是原有的树顺时针旋转45°，然后用孩子兄弟法重新连线后的结果。
逆过来转换就是左转，然后重新连线。

为了防止出错，可以用两种颜色的笔区分孩子链域和兄弟链域，又或者你直接记住左分叉是孩子链域，右分叉是兄弟链域就好。

森林和二叉树，只需要补兄弟边就好，每一颗树的根，合起来在同一层，互为兄弟。

之后就是经典的旋转转化了，还原的时候，几何上应该从右边开始画线，一层一层往左边推。

树和森林的遍历

对应关系，森林->树->二叉树，二叉树是宇宙万法的尽头，硬要你写代码的话，一切代码都可以用二叉树实现。

树遍历

树只有先序和后序，不存在中序的说法，因为无法确定孩子数量，所以干脆就不往中间排，要么先访问再依次递归孩子，要么先递归完孩子再访问。

数的初始逻辑结构和其二叉树形态有所不同，因此遍历序列也不相同，对应关系：

1. 树先序=二叉树先序
2. 树后序=二叉树中序

森林遍历

森林遍历涉及二层递归，这里先简单理解下。先序还好，主要是中序，为什么树没有中序，森林这里就是中序了呢？因为可以以一个节点，切分出两片森林，这才可以把根节点放在中间，即中序。理论上森林还有后序，但是过于阴间，就没有放出来。

写代码的话，比较复杂，直接换个思路，用效果等价：

1. 森林先序=每棵树先序遍历
2. 森林中序=每棵树后序遍历

实在考出来写代码，也可以取巧，先把森林转化为二叉树储存结构，然后把森林的遍历等效到树的遍历，再对标到二叉树的遍历，比如森林中=树后=二叉树中，这样也可以写代码。

树应用

哈夫曼树

首先说带权路径长度（WPL，Weighted Path Length）

一条路径的WPL=经过的边数×终点权值
一棵树的WPL=所有叶节点的WPL

哈夫曼树就是WPL最小的二叉树，给定一些带权叶节点，这里首先定义一下树的总权值=叶节点权值和，构造一颗哈夫曼树过程如下：

1. 所有叶节点构成一个集合
2. 合并
   • 找场上总权值最小的两棵树
   • 二合一，并将树的总权值记录在根节点上
3. 循环2步骤，直到集合中只剩一个元素

哈夫曼树的特点如下：

1. WPL最小。权值小的，路径长，权值大的，路径短，那么总共的WPL就被平衡下来，达到最小。
2. 无歧义。初始节点最后只能成为叶节点，中间结点无意义。
3. 哈夫曼树不唯一
   

哈夫曼树的应用是可变长度编码

权值可以理解为使用频率，或者重要程度。重要的，就应该放在上面，以更少的消耗编码：

1. 先按照权值构造哈夫曼树
2. 哈夫曼树获得编码

如下图，C最重要，因此只用1个bit，ABD长度依次增加。

这种不定长编码的问题在于，可能会有歧义，因为无法定长分节解析，但是恰巧哈弗曼编码无歧义，为前缀编码，因此可以使用异步方式解析。如何解码呢？其实就是把这一串序列送到哈夫曼树里面，走到叶节点就解析一个字符，然后下一个序列继续从根开始。这个过程其实就是一个FDA，和编译原理有共同之处

如此，从概率来看最后编码和解码的总消耗都是最少的（实际上不见得最少）

并查集

数据结构

并查集就是集合，集合之间互不相交，我们此处要用数据结构描述这种互不相交的关系。

基于这个关系，还应该实现两个基本功能：

1. 查：给定元素，判断所属的集合
   • 这个操作说白了就是找根节点
2. 并：合并两个集合
   • 直接让一颗树的根节点成为另一棵树的子节点就好

这两种方法，用双亲表示法都是最有效率的，实现也很容易。

其实也可以用链表，我也做过链表的题，但是因为链表找到头比较慢，要O（n），而树结构分叉，高度大概只有O（logN），查一次要的迭代次数更少，因此时间效率上，双亲表示法完胜

现在唯一的技术难点其实就是如何用一个数组储存一个森林呢？本质就在于要同时维持多个根节点，但是这个问题其实不是问题，因为不同的根节点可以通过下标来区分，反正我们只有并查操作，只需要找双亲，所以这样储存完全没问题，就这么简单粗暴。

说白了，把操作限制在并查，就可以针对性的使用高效率的结构实现，操作越复杂，耗时越多，还需要用更精巧复杂的结构来降低操作的损耗，这是不变的道理

优化

并集：控制高度

优化效率，就要分析复杂度。

并集为O（1），改下指针就行，查需要逆向迭代，如果所有元素串成一条线，那么最坏就是O（n），反之，如果平铺开来，尽可能降低高度，就可以提高效率。

注意，双亲法是树，不限制孩子个数，所以每次并集都是直接并到根节点上，现在我们要优化这个过程：

仔细分析Union过程，在把一颗高度为n的树插到另一颗树上时，这颗子树算上根节点，总高度其实是变成了n+1。
假如有三个节点ABC，把C插到B上，再把B插到A上，总高度就是3
换个思路，如果把C插到B，然后把A插到B，总高度只有2，在第二次插入过程中，总高度并没有变化。

具体逻辑如下：

1. 把矮树并到高树上，就不会增加总高度
2. 若两树高度相同，则并集会令高度+1

但是呢，我们对高度其实并没有一个衡量，所以只能用挂载节点的数量（元素数量）来近似高度，既然无法判断高矮，判断大小也是可以的，具体操作如下：

但是你以为这就完了吗？如果你从离散的叶节点开始合并，你会发现最后的长度无论如何都不会超过这个数，即时间复杂度最好O（1），最坏都是O（logN）

查集：压缩路径

前面说的是在并集过程中对于高度的优化

现在进一步，在查集的过程中进一步优化，属实是脑洞大开，令人拍案：

1. 首先找到根节点，保存根节点位置
2. 然后进行二轮回溯压缩路径，从路径终点开始
   • 先保存父节点备用
   • 拆桥，把当前节点挂载到根节点
   • 保存的父节点派上用场，当做下一轮循环要调整位置的节点

如此，每次查询，都可以进行一次压缩，越查越快，可以对抗并集导致的高度增加，配合并集优化，可以使得一般情况下高度维持在4以内，牛逼。

图

基本概念

图是离散数学里的东西，所以一开始会有很多形式逻辑，比较琐碎：

1. 图的阶：顶点个数
2. 图空的讨论：
   • 顶点不为空，至少有一个（树可空）
   • 边可为空
3. 边的方向
   • 无向图一定是双向关系，叫边，（A，B）=（B，A）
   • 有向图存在单向关系，叫弧，分头尾！=，走路径的时候不可逆向
     
4. 边的重数：重复，则为重边（反向不算重复），自循环，也算重边。数据结构只研究简单图，无重数
5. 节点的度：无向图total degree：TD（v），有向图分为ID（v），OD（v）
6. 路径
   • 路径用顶点序列描述，路径长度用边数量描述
   • 回路：首尾相接
   • 简单路径：其实就是路径里面无环
7. 连通性：
   • 顶点连通即有路径，有向图有可能是单边连通（弱），双向连通则强
   • 强连通，只需要顶点之间可以相互找到就好，不一定要逆着路径来，所以强连通图里，完全可能只有单向边
   • 图的连通性，任意两个顶点
   • 连通图其实就是一个等价类
8. 连通性与边数量的关系：
   • 无向图
     • 连通图，最少得n-1条，比如构成线性结构
     • 非连通图，极限情况是n-1个节点连满了，而有1个节点孤立，这时就是$C_{n-1}^2$条
   • 有向图
     • 只讨论强连通。最少要n条，形成环路
9. 子图：
   • 子图至少是个图，所以挑出来的边一定是有节点可依附的
   • 生成子图即删去一些边，保留全部节点
10. 连通分量
    • 一个图，整体并不一定是连通，但可能有子图是连通，每个连通的子图都算一个连通分量
    • 连通分量要满足极大连通，其实就是完整性，就是不断地扩充，直到连无可连，这才是一个完整的等价类
    • 无向图，连通分量之间在原图中肯定无边
    • 有向图只考虑强连通，因此可能有边，但是只能单向（如下图）
      
11. 生成树/森林
    • 这个仅针对无向图
    • 保证图原有连通性前提下，尽可能简化删减边，变成一棵树/n颗树
    • 连通图，可以化作一棵树，会直接变成极限情况，即n-1条边（回顾树，n节点树必然有n-1边）
    • 非连通图，本就不连通，所有连通分量生成的树构成生成森林
12. 带权图（网）
    • 图的权值为边，代表顶点距离，用于解决现实问题（而树的权值常是节点，比如哈夫曼树）
    • WPL为路径长度的加权和，实际上就是权值之和（因为每条边的原始长度恒为1，加权后就是权值本身）

储存结构

邻接矩阵：数组

这一部分和离散数学关系比较大。

邻接矩阵是图储存的最简单的方法：

1. 顶点信息：Vex数组，内部结构可以自定义，比如记录入度出度之类的信息
2. 边信息：Edge矩阵
   • 1为链接，0为不连接。
   • 无向图是对称的，因为双向，而有向图是不对称的。
3. 数量信息：vecnum和arcnum，储存顶点和边数

关于入度出度：

1. 可以给每个元素单独记录
2. 也可以当场求
   • 横向代表入度，纵向代表出度，遍历一下，1的个数就是度
   • 复杂度为O（|V|）

带权图，只需要把权值放到边矩阵中即可，0和inf都可以代表不连接。

虽然邻接矩阵比较原始，但是仍然有好的性质，比如计算闭包

$A^n$，这个矩阵中的A[i,j]元素，代表从i到j，长度为n的路径数目。

大白话说就是，原始的矩阵是直达，二次方就是中转一次，n次方就是中转n-1次。

引申一下，如果是一个连通图，$\sum A^n$中肯定没有0，这代表任何两个元素都是有路的，而数值就是路径的数量（不论长短）

邻接表：顺序+链式

储存结构：

1. 节点数组：AdjList
2. 数量信息：vexnum，arcnum

边信息并不直接储存在数据结构中，而是以链表的形式散布在内存中，链表的头指针就在节点数组中。

关于度：

1. 邻接表同样是采用当场计算的方式
2. 邻接表本质上是储存了出度节点的信息，因此计算出度很快，但是计算入度要遍历所有边

关于唯一性：

链表顺序不定，因此表示不唯一，后面凡是加了链表进来的，都不唯一

这个和树的孩子表示法其实一样，或者说孩子表示法其实是用图的方法去降维打击树了

但是邻接表，其实真就只适合树，对于图来说，有大缺陷：

1. 储存有向图，丢了入度信息
2. 储存无向图，有翻倍的冗余边

无论储存有向图还是无向图，都有大缺陷，而树，恰恰只有出度是不确定的，压根不用在意是否丢失入度信息
即使考虑入度，也只有一个，完全可以再加一排双亲信息就好

十字链表/邻接多重表：网状

关于十字链表，其实我们之前已经用过了，这张图非常直观，十字链表里储存了完整的行列信息。

邻接矩阵是矩阵，因此也可以压缩，完全可以套用下面这张图。

当然，具体设计是有一些改动的：

首先要把行列和图对上：

1. 行
   • 从一个节点出去的所有弧
   • 弧尾相同的所有弧
   • 对应tail
2. 列
   • 就是进入一个节点的所有弧
   • 弧头相同的所有弧
   • 对应head

然后看数据结构：

1. 顶点数组：大满贯，行列信息都放在一个元素里
   • 数据域（节点）
   • 行列头指针（指向第一个出/入弧）
2. 弧节点：
   • 行列信息：几行几列
   • 链域：指向同行/列下一个元素

需要注意的是：

1. 不唯一性。即使行列都限制了，实际的顺序也不唯一，有可能同一行出现（2,3），（2,1），（2,4）这种列顺序不一致的，链表实在是太灵活了
2. 有向性。很显然，数据结构里规定了出入，因此只适用于有向图，如果用到无向图，可能会形成死循环。
3. 效率。
   • 时空效率综合起来是最高的，又省空间（不冗余），又快（出入度信息都有）
   • 行直接顺着绿色方向横向遍历，列直接顺着橙色方向纵向遍历
   • 硬要说弱势，就是数组和弧节点占用的空间稍微大了点（多放了一排指针），但是实际毫无影响。

对于无向图，使用邻接多重表

可以理解为精简化的十字链表，只看连接，不看出入，甚至左右顺序都可以是反的，（2，4）和（4,2）有一个就行，也就是说，我们前面十字链表可以按照行列遍历，但是这里不能蛮干，需要多加一个判断，判断这个节点是在左边还是右边，进而选择对应链域遍历。

举个左右切换的例子

下图中，E（4）节点为例，找到其所有边：

1. 首先找到（4，1）节点
2. 然后判断，4在左边，因此用橙色指针找下一个，为（2,4）节点
3. 然后判断，4在右边，因此用绿色指针找下一个，图中没有
   • 但是如果下一个节点是（4,5），那么下下次寻找就又要用橙色指针

总之，邻接多重表遍历是要看左右的，而十字链表就直接行列遍历就行
邻接多重表额外加的判断就是消除冗余信息（同时消除左右信息）后必然要付出的代价
当然，删除了左右信息，也是去掉了限制，在增删的时候，也会有意外的效果。

大总结

1. 邻接矩阵是最基础的，基于此衍生出多种方法。
2. 首先是邻接表，可以替代邻接矩阵，这是最原始的，拥有很大的缺陷，为了补足缺陷
3. 然后是十字链表。
   • 这个弥补了十字链表丢失的列信息，怎么弥补呢，其实就是给数组多加了一列，然后给节点也多加了列的链域。
   • 然而，过于丰富的前后信息，使得十字链表无法表达无向图
4. 邻接多重表，可以理解为简化的十字链表
   • 邻接多重表去掉了左右的限制，从而打破有向性
   • 因为打破了有向性，所以弧节点左右可以调换，而数组节点也只需要存一个指针就行

基本操作

基本操作

实际考察，考察邻接矩阵和邻接表的情况较多，因此以这两个数据结构举例。

1. Adjacent：查找边
   • 邻接矩阵直接锁定，而邻接表需要遍历一行
2. Neighbors：查找邻居
   • 无向图：邻接矩阵和邻接表都是遍历一行
   • 有向图：考虑出和入，因此邻接矩阵遍历两行，但是邻接表入度无法计算，所以实际上要遍历全表
3. FirstNeighbor：第一个邻居
   • 无向图：矩阵要遍历一行，碰到有边才停，而邻接表直接取第一个元素就行
   • 有向图：矩阵遍历一行一列，而邻接表考虑入边的话，最坏的情况是需要遍历完整张表
   • NextNeighbor的原理一样，使用频率很高
4. InsertVertex：插入节点
   • 因为邻接矩阵和邻接表的节点信息已经在数组结构中了，所以增加的其实只是节点信息，而不是节点结构
   • 因此插入，只需要写一个信息进去就行，比如一个bool，告诉你这一行可用
5. DeleteVertex：删除节点
   • 和插入节点一样，要删除信息，但是除此之外还要清空边的信息，真正耗时的地方在这里
   • 无向图：删除所有入边和出边，邻接矩阵清空一行一列即可，邻接表最好O（1），最坏要遍历全表
   • 有向图：矩阵一行一列，邻接表直接全表，必须全表
   • 区分下邻接表的操作，有向图必须遍历全表，但是无向图其实不完全是遍历全表，而是要清楚入边对应的对偶出边，比如如果只有AC有连接，那么后面你就只需要去C的那一行里遍历就可以，其他的不用考虑
6. AddEdge：增加边
   • 邻接矩阵直接填入，而邻接表要插入节点，采用头插法是O（1）
   • 实际情况还要判断边是否存在，于是还要用到Adjacent

广度优先遍历（BFS）

思路：

1. 先访问根节点，然后放到辅助队列里
2. 循环直到队空
   • 出队：从辅助队列里取出一个节点
   • 对周围一圈
     • 访问
     • 加入

需要注意细节：

1. 队列里放的都是被访问过的节点，这些节点只是用来寻找下一层的（找到以后马上访问入队），入队前已经被访问过了
2. 邻接矩阵唯一，因此遍历序列唯一，但是邻接表不唯一

考虑到非连通图，需要反复检查visited数组中是否有false，对于每个连通分量，都会调用一次BFS

复杂度：

1. 空间：来自于队列，极限情况是O（|V|）
2. 时间：总时间=遍历节点的时间+探索下一圈节点的时间，因此邻接矩阵是O（|V|+$|V{|}^2$）=O($|V{|}^2$)，而邻接表更快，O(|V|+|E|)

广度优先遍历是逐层且无回路的，因此可以按照层序原则组织成一个生成树，对于多个连通分量，就是生成森林。
对于邻接表，因为遍历序列不唯一，所以生成森林结构也不唯一，邻接矩阵则唯一

深度优先遍历（DFS）

深度优先遍历表面上是逐层圈的逻辑，但是因为没有队列作为记忆辅助，所以是采用递归的方法辅助的，因此就会产生尾递归的效果，实际路径和先序遍历一样。

其实DFS和BFS代码逻辑略有差距

BFS是在遍历循环的时候访问，根节点在出队前已经被访问过
DFS是递归的，在函数之初访问，遍历循环的时候仅仅是递归调用

对于非连通图情况，写法和BFS一致

复杂度：

1. 空间：递归调用栈，最深为线性结构，要把最后一个调用完才能释放前面的
2. 时间=遍历节点时间+寻找下家时间。和BFS一致

分析递归序列比较麻烦，可以自己维持一个递归调用栈防止出错

图算法

最小生成树

Prim算法

核心思想：

1. 以已经生成的节点为一个整体
2. 在整体对外遍历节点，找一个边成本最低的节点纳入

n个节点，选择n-1次就可以把所有节点纳入整体，也就是最小生成树

Kruskal算法

有效连通次数也是n-1

无效：指两端已经联通，再连通就成环了

对比

Prim算法针对顶点，扫描n-1个顶点，每个顶点扫描两轮，Kruskal算法针对边，与并查集有关，判断E轮，每轮判断logE次，因此复杂度如下

（具体分析略，有空补）

最短路径问题

无权图单源——BFS

目标：求得一个源头到所有节点的路径长度：

路径两个要素：

1. d记录路径长度
2. path记录路径，实际上记录的是最短路径上的直接前驱

用两个数组来储存，具体思路如下：

1. 起始节点的d初始化为0，这个很重要
2. 用BFS逐层遍历
   • 每个节点，用path指向父节点
   • d[当前节点]=d[父节点]+1

效果就是，从源头开始，BFS构建一个生成树，每一层的路径长度都要+1
而且可以从终点逆向找到全路径，比如8，倒着可以找到762

带权图单源——Dijkstrea

考虑权值后，转站次数并不能完全代表成本，有可能有一条路转了很多次，但是却最快，因此BFS算法失效。

Dijkstrea算法计算的是带权路径长度，和Prim算法过程很类似

首先明白数组的意义：

1. final：代表是否已经找到这个节点的最短路径
2. dist：代表已知的最短路径
   • 如果final=true，那么dist就是全局最优，否则就不一定
3. path：记录已知路径的前驱
   • 如果final=true，那么path就是最短路径前驱

思路：在n-1轮循环中，每次循环都确定一条最短路径

1. 可以确定初始节点自身到自身是最短的路径，刷新周围一圈路径长度
2. 循环
   • 确定一个最小值：在不确定列表中找到最短的一条路径，则可以确定为一定为最优（凭什么呢？我没动脑子，凭感觉是动态规划的思路，比较抽象，姑且就直接记死）
   • 刷新不确定：每确定一个最短路径节点，就用这个节点的信息更新一遍周边路径，将不确定是否为final的路径长度都刷新一遍。

注意，带负权值的图不可以用Dijkstera，因为判断最小值那一步失效。

各顶点间路径——Floyd

Floyd算法是一个典型的动态规划问题，新状态基于原有的状态求得，经过n-1轮迭代后获得最终状态。

看下图，先说数据结构意义：

1. path：记录最短路径中转前驱（其实不完全是前驱）
   • 比如V0-V1-V2-V4，那么path[0][4]=2
   • 如果是直达就不需要
2. A：记录任意两点之间的最短路径长度
3. 序号：代表考虑了i≤k的所有节点后的数据，比如k=2，则已经考虑了012三个节点

下图为k=-1的时候，即初始直达状态

之后进行n论迭代，每次都加入一个新的节点，遍历A矩阵的所有格子，比较增加这个节点中转后是否路径可以更短，如果可以，就把这个最新的前驱写入path矩阵里

问题来了，如何根据结果进行分析呢？

1. 最短路径长度：直接看A
2. 找到对应的最短路径：比较复杂，因为比如现在有n个节点，那么就要去思考n-1种可能，因为每两个节点之间都不一定是直达，我们要在path中不断找，直到我们最终排列出来的节点列表，相邻两两之间是直达的

算法复杂度，n个节点，每个节点$n^2$次，总共三次方

最后，Floyd可以解决负权问题，但是不能解决负权回路问题。

有向无环图（DAG）应用

DAG描述表达式

我们用二叉树描述中缀式，但是二叉树里面往往有公用的部分：

1. 公用变量
2. 公用运算式

这些都可以合并，只需要让指针同时指向这个部分即可，因为是DAG，所以并不会产生歧义

合并的技巧：

1. 第一步就可以让最底层不重复
2. 第二步：标出计算顺序，这个就是四则的顺序
3. 第三部：分层，要利用上一层数据的，则放在更高层
4. 逐层合并，同时满足如下条件则合并：
   • 操作符需要一致
   • 左右操作数一致（左右箭头指向位置一致）

拓扑排序

拓扑排序思路如上，这里探究一下具体代码：

1. 初始化：把最初没有入度的节点入栈
2. 循环：
   • 进行工作：出栈+记录这个节点，count指针后移
   • 删去节点
     • 删去本节点所有出度——把所有目标节点的入度-1
     • 如果有新的可用节点（入度=0），则入栈
3. 判断DAG：如果输出序列长度count<节点数，代表有环路

时间复杂度=每个节点+每个边，因此邻接表是V+E，而邻接矩阵是$V^2$

逆拓扑排序考虑入度，逻辑一致，时间复杂度有所不同。

邻接表计算入边的成本是遍历全表，太高，因此思路有三：

1. 邻接矩阵
2. 逆邻接表
3. DFS

重点说DFS，在没有环路的前提下，把print插入到递归最后，就会变成尾递归，以下图为例：

1. 顺遍历：0134，那么反向输出4310
2. 顺遍历：2，反向输出2

最终就是逆拓扑排序，当然，有环路的情况下要加一个visited数组，如果重复，那么就报错。

关键路径

这里区分AOV和AOE网：

1. AOV网的信息是顺序：
   • 顶点是任务
   • 边表示先后顺序
2. AOE网的信息是顺序+时间：
   • 顶点是一个里程碑
   • 边不仅表示顺序，还表示从一个里程碑到另一个里程碑要消耗的时间

可以看到，AOE网，不仅仅受到顺序的制约，还要受到时间的制约，先来者要等后来者。
当一个里程碑所需的条件全部达成，当前里程碑后续的任务则开始计时

AOE网错综复杂，如何寻找到决定性的考虑因素呢？其实就是找最慢的那一条路，其他的路一定都要等这条路，这条路就是关键路径，上面的都是关键活动

关键路径总成本就代表整个工程的耗时

1. ve（节点）：第一轮确定最早到达最终节点的时间，这就是我们的目标
   • e（边）：进而确定活动最早开始时间（弧头节点时间）
     
2. vl（节点）：反着根据目标，算最晚到达节点的时间
   • l（边）：进而确定活动最晚开始时间（弧尾节点时间-边消耗时间）
     
3. d：有了e和l后，就可以算出一个任务允许的拖延余量，如果为0，那么代表不可拖延

然后来具体说一下如何计算：

1. 计算ve，走顺拓扑序列
   • 原点=0
   • 某一点的ve，遍历所有可能的前驱，选出前驱+前驱边的值最大的那个（所有前驱都完成，才能完成这一个，因此取所有前驱中最晚的那个）
2. 计算vl，走逆拓扑序列（注意，逆拓扑序列不等于顺拓扑排序翻转）
   • vl（终点）=ve（终点）
   • 某一点的vl，遍历所有可能的后继，选出后继-后继边的值最小的那个（笨鸟先飞，后面的在等也不迟，最小的那个等不了）
3. 用ve求e，用vl求l，之后d=l-e

最后的最后，讨论一下特性：

1. 关键路径的本质：最慢的那条路
   • 因此，关键路径的长短代表整体工程，伸缩特性一致
2. 如果缩短一个任务，可能就会改变关键路径
   • 因为本质是最慢，当关键路径不是最慢，也就不是关键路径了
3. 如果有两条关键路径，那么需要同时缩短
   • 因为如果只缩短一条，马上就会退化为非关键路径，因此要同时保证两条路径都是关键路径，即同时缩短