九. 图1. 图的概念2. 图的存储2.1 邻接矩阵法邻接矩阵存放普通图邻接矩阵法存放带权图邻接矩阵性能分析与性质2.2 邻接表2.3 邻接表与邻接矩阵对比2.4 十字链表2.5 邻接多重表2.6 总结3. 图的基本操作4. 图的广度优先搜索4.1 图的BFS实现4.2 图BFS遍历非连通图4.3 图的BFS算法复杂度分析4.4 广度优先生成树与森林广度优先生成树广度优先生成森林5. 图的深度优先搜索5.1 图的DFS实现5.2 图DFS遍历非连通图5.3 图的DFS算法复杂度分析5.4 深度优先生成树与森林5.5 图的遍历与图的连通性6. 图的应用6.1 最小生成树普利姆(Prim)算法克鲁斯卡尔(Kruskal)算法两个算法比较6.2 最短路径问题BFS算法解决最短路径Dijkstra算法解决最短路径Floyd算法解决最短路径6.3 总结7. 有向无环图(DAG图)7.1 DAG应用——有向无环图表达式7.2 DAG应用——拓扑排序拓扑排序代码实现逆拓扑排序DFS实现逆拓扑排序8. 关键路径十. 查找1. 查找算法评价指标2. 顺序查找2.1 代码实现2.2 查找效率分析2.3 顺序查找的优化(有序表)3. 二分查找(折半查找)3.1 查找步骤及实现3.2 查找的效率分析3.3 二分查找判定树构造4. 分块查找4.1 分块查找实现4.2 分块查找效率分析5. 二叉排序树5.1 二叉排序树查找5.2 二叉排序树的插入5.3 二叉排序树的删除5.4 二叉排序树查找效率分析6. 平衡二叉树6.1 调整最小不平衡子树调整最小不平衡子树(LL)调整最小不平衡子树(RR)调整最小不平衡子树(LR)调整最小不平衡子树(RL)平衡二叉树查找效率分析总结6.2 平衡二叉树的删除7. 红黑树7.1 红黑树的插入7.3 红黑树的删除8. B树8.1 B树的插入8.2 B树的删除9. $B^+$ 树9.1 $B^+$ 树的查找9.2 $B^+$ 树与 $B$ 树区别10. 哈希表10.1 拉链法解决哈希冲突10.2 常见的哈希函数除留余数法直接定址法数字分析法平方取中法10.3 开放定址法解决哈希冲突线性探测法平方探测法伪随机序列法10.4 再哈希法

九. 图

$V$ $E$ $|V|$ $|E|$ 表示边个数。

顶点集表示图的顶点个数组成的集合，也可以称为图的阶。边集表示的是连接顶点的边组成的集合，任何一条边两头必须连接一个顶点。

即V一定是非空集 $E$ 可以是空的。如下：

图数据结构应用：地图、社交软件好友关系等。

1. 图的概念

无向图与有向图：
1. $E$ G $(v, w)$ $(w,v)$ $(v, w)=(w,v)$ $v、w$ $w$ $v$ $(v, w)$ $w$ $v$ $(v, w)$ $v、w$ 相关联。
  $\begin{aligned} G_{2} = (V_{2}, E_{2}) \\ V_{2} = {A, B, C, D, E} \\ E_{2} = {(A, B), (B, D), (B, E), (C, D), (C, E), (D, E)} \end{aligned}$
2. $E$ $G$ $<v, w>$ $v、w$ $v$ $w$ $<v, w>$ $v$ $w$ $v$ $w$ $w$ $v$ $<v, w>\ne<w, v>$

\begin{aligned} G_{1} = (V_{1}, E_{1}) \\ V_{1} = {A, B, C, D, E} \\ E_{1} = {< A, B >, < A, C >, < A, D >, < A, E >, < B, A >, < B, C >, < B, E >, < C, D >} \end{aligned}

简单图与多重图：
1. 简单图：①不存在重复边；②不存在顶点到自身的边
  可分为简单无向图和简单有向图：
2. 多重图：图G中某两个结点之间的边数多于条，又允许顶点通过同一条边和自己关联，则G为多重图
  可分为多重无向图和多重有向图：
  数据结构课程只探讨简单图。
顶点的度：
1. 对于无向图：
  $v$ 的度是指依附于该顶点的边的条数，记为TD(v)。
  $n$ $e$ $\sum\limits_{i=1}^{n}TD(v_i)=2e$ ，即无向图的全部顶点的度的和等于边数的2倍。
2. 对于有向图：
  $v$ 为终点的有向边的数目，记为ID(v)，即该顶点有多少个箭头指向它。
  $v$ 为起点的有向边的数目，记为OD(v)。即该顶点有多少个箭头指向别的顶点。
  $v$ $TD(v) = ID(v) + OD(v)$ 。
  $A$ $ID(v) + OD(v)=1+4=5$
  $n$ $e$ $\sum\limits_{i=1}^{n}ID(v_i)=\sum\limits_{i=1}^{n}OD(v_i)=e$
描述顶点和顶点关系的术语：
1. $v_p$ $vq$ 之间的一条路径是指顶点序列。在无向图中路径的方向是没有限制的，有向图中路径的方向是有限制的，要和弧的方向一致。
2. $V_B,V_D,V_E$ 组成的路径就是回路。
3. 简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。
4. 简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
5. 路径长度：路径上边的数目。
6. $u$ $v$ $u$ $v$ $u$ $v$ $(\infty)$ 。
7. $v$ $w$ $v$ $w$ 是连通的。
  $G$ 任意两个点都是连通的则称为连通图：
  常见考点 $n$ $G$ $G$ $n-1$ 条边。
  $G$ $C_{n-1}^2$ 条边。
8. $v$ $w$ $w$ $v$ 之间都有路径，则称这两个顶点是强连通的。
  $V_A$ $V_B$ 之间是强连通的。
  若图中任何一对顶点都是强连通的，则称此图为强连通图：
  常见考点 $n$ $G$ $G$ $n$ 条边(形成回路)。
子图：
$G=(V, E)和G'=(V',E')$ $V'$ $V$ $E'$ $E$ $G'$ $G$ 的子图。
上面子图可以是：
生成子图：如果原图中包含子图所有顶点，这个子图就可以称为原图的生成子图：

有向图子图和生成子图概念同上。

连通分量：
无向图中的极大连通子图称为连通分量。子图必须连通，且包含尽可能多的顶点和边。
上图三个连通分量如下：
强连通分量
有向图中的极大强连通子图称为有向图的强连通分量。子图必须强连通，同时保留尽可能多的边。
上图强连通分量是：
同样的剩下两个顶点F和G也是图的一部分，所以这两个顶点单独拿出来也是极大强连通子图，故这个图强连通分量有三个。
生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图。边要尽可能的少，但要保持连通。
上图的生成树是：
同时也有别的生成路径，所以对于一个生成树来说生成树结果不唯一。
$n$ $n-1$ 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
生成森林
在非连通图中，连通分量的生成树构成了非连通图的生成森林。
上面生成森林可以拆分成几个连通分量：
再生成上面连通分量与之对应的生成树，这样就得到了森林非连通图得生成森林：
带权图
边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
带权图/网：边上带有权值的图称为带权图，也称网。
带权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。
几种特殊的图
无向完全图：无向图中任意两个顶点之间都存在边
有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧
稀疏图：边数很少的图
稠密图：反之称为稠密图
树：不存在回路，且连通的无向图
$n$ 个顶点的图， $|E|>n-1$ ¹，则一定有回路。
$0$ $1$ 的有向图，称为有向树。
有向树并不是强连通图

2. 图的存储

2.1 邻接矩阵法

邻接矩阵存放普通图

用二维数组存放各个顶点之间边的关系

无向图存储结构：

有向图存储结构：

上图中无论是有向图还是无向图，右边二维数组中存放的是边的关系。如：顶点A与顶点B之间有边，故二维数组[A][B]=1

代码存储结构如下：


xxxxxxxxxx
7
1
#define MaxVertexNum 100
2
//顶点数目的最大值
3
typedef struct{
4
    char Vex[MaxVertexNum];                 //顶点表
5
    int Edge[MaxVertexNum][MaxVertexNum];   //邻接矩阵，边表
6
    int vexnum, arcnum;                     //图的当前顶点数和边数/弧数
7
} MGraph;

上面存放顶点信息的vex数组，可以存放更复杂的信息。同时，由于二维数组中只存放0和1，所以可以使用更小的bool变量。

vex数组存放顶点信息时，数组下标要与edge数组中边的信息一致。即：

$n$ $G= (V, E)$ $A$ $n\times n$ $G$ $v_1,v_2....v_n$ 则

\begin{matrix} A [i] [j] {\begin{matrix} 1, & 若 (v_{i}, v_{j}) 或 < v_{i}, v_{j} > 是 E (G) 中 的 边 \\ 0 & 若 (v_{i}, v_{j}) 或 < v_{i}, v_{j} > 不 是 E (G) 中 的 边 \end{matrix} \end{matrix}

求顶点的度、入度和出度方法：

$i$ $=$ $i$ $i$ 列)的非零元素个数。

对于无相图：

$i$ $=$ $i$ 行的非零元素个数
$i$ $=$ $i$ 列的非零元素个数.
$i$ $=$ $i$ $i$ 列的非零元素个数之和

$/$ $/$ $O(|V|)$

邻接矩阵法存放带权图

同样用二维数组存放，但同时存放的不再是0和1权值 $\infty$ 。

存储结构代码如下：


x
1
#define MaxVertexNum 100        //顶点数目的最大值
2
#define INFINITY 0x3f3f3f3f     //宏定,义常量"无穷"
3

4
typedef char VertexType;        //顶点的数据类型
5
typedef int EdgeType;           //带权图中边上权值的数据类型
6
typedef struct{
7
    VertexType Vex[MaxVertexNum];//顶点
8
    EdgeType Edge[MaxVertexNum][MaxVertexNum];//边的权
9
    int vexnum,arcnum;//图的当前顶点数和弧数
10
}MGraph;

邻接矩阵性能分析与性质

$O(|V|^2)$ ，只和顶点数相关，和实际的边数无关。

$/$ 下三角区)。

性质：

$G$ $G$ $0$ $1$ $G^n$ $G^n[i][j]$ $i$ $j$ $n$ 的路径数目。

$\Large例1:$ $G^2[1][4]=a_{11}a_{14}+a_{12}a_{24}+a_{13}a_{34}+a_{14}a_{44}=1$

$a_{12}a_{34}=1$ $0$ $a_{12}a_{24}=1$ $A\rightarrow B$ $B\rightarrow D$ $1$ $A\rightarrow D$ $2$ 情况下只能找到一条路径 $a_{12}$ $AB$ $a_{24}$ $BD$

$\Large 例2:$ $G^2[2][2]=a_{21}a_{12}+a_{22}a_{22}+a_{23}a_{32}+a_{24}a_{42}=3$

$B\rightarrow B$ $2$ $a_{21}a_{12}$ $B\rightarrow A$ $A\rightarrow B$ $a_{22}a_{22}=0$ $B\rightarrow B,B\rightarrow B$ $a_{23}a_{32}$ $B\rightarrow C,C\rightarrow B$ $a_{24}a_{42}$ $B\rightarrow D,D\rightarrow B$ 这条路径存在。

$G^2$ $2$ 的路径总共多少条。

2.2 邻接表

$+$ 链式存储方式实现：

存储上面无向图可以用下面存储结构：

代码结构实现如下：


xxxxxxxxxx
18
1
//"边/弧"
2
typedef struct ArcNode{
3
    int adjvex;             //边/弧指向哪个结点
4
    struct ArcNode *next;   //指向下一条弧的指针
5
    //InfoType info;        //边权值
6
}ArcNode;
7

8
//"顶点"
9
typedef struct VNode{
10
    VertexType data;//顶点信息
11
    ArcNode *first;//第一条边/弧
12
}VNode,AdjList[MaxVertexNum];
13

14
//用邻接表存储的图
15
typedef struct{
16
    AdjList vertices;
17
    int vexnum,arcnum;
18
}ALGraph;

AdjList[MaxVertexNum]存储各个顶点信息(data*first $/$ 边)；vertices顶点结点数组，代表一个图，其中的vexnum表示有多少条结点，arcnum表示有多少条边；每个边和弧也会有与之对应的结点ArcNode

有向图邻接表法存储结构：

$2|E|$ $O(|V| + 2|E|)$ 。

$|E|$ $(O(|V| + |E|)$ 。

无向图找度和边：
找无向图顶点的度只需要遍历和这个顶点相关的边链表(*first指针指向的链表)即可，有几个边结点，度就是多少。同时这个边链表就是这个顶点的所有边。
有向图的入度，出度和边
找一个结点出度，只需要遍历和这个结点相关的边链表即可，这个边链表也是指向其他结点的弧。
找入度和指向当前结点的弧较为复杂：依次遍历所有顶点边链表，找对应的边。这也是邻接表存储图一大缺点。

2.3 邻接表与邻接矩阵对比

邻接表与邻接矩阵：

	邻接表	邻接矩阵
空间复杂度	$O(\|V\|+2\|E\|)$ $O(\|V\|+\|E\|)$	$O(\|V\|^2)$
适合用于	存储稀疏图	存储稠密图
表示方式	不唯一	唯一
$/$ $/$ 入度	计算有向图的度、入度不方便，其余方便	必须遍历对应行或列
找相邻的边	找有向图的入边不方便，其余很方便	必须遍历对应行或列

2.4 十字链表

只能用于存储有向图。

邻接矩阵主要问题是：空间复杂度高。而邻接表问题在于找有向图的入边不方便，其余很方便。

十字链表结构体结构：

存储以下有向图：

则十字链表数据存储结构如下：

$ABCD$ $0123$ 位置。

$A$ 绿色指针代表弧尾 $1$ $B$ $A\rightarrow B$ $B$ $2$ $C$ $A\rightarrow C$ 。

$A$ $2$ $C$ $C\rightarrow A$ $C$ $3$ $D$ $D\rightarrow A$ 。

总结：通过绿色指针往后找可以找到所有从当前结点发射的所有弧(该节点指向了谁)。橙色指针往后找则可以找到所有指向当前结点的弧。

$O(|V|+|E|)$ 。V代表顶点个数，E代表边的个数。

即解决邻接矩阵空间复杂度高的问题。又解决邻接表找有向图的入边不方便的问题。

2.5 邻接多重表

只能用于存储无向图。

$O(|V|^2)$ 。邻接表的每条边对应两份冗余信息导致删除顶点、删除边等操作时间复杂度高。

邻接多重表结构体存储结构：

存储以下有向图：

则邻接多重表数据存储结构如下：

结点存放ABCDE是一个数组，firstedge指针指向当前顶点相连的第一条边。

$A$ 结点firstedge指向0和1相连的边，即A——BB $A$ $D$ 。

$B$ 结点firstedge指向0和1相连的边，其中B结点在整个结点中是绿色1结点，其绿色指针指向的就是B2 $C$ 结点，同样下一个绿色1结点是B结点，再顺着绿色指针指向E结点。此时绿色指针域为NULL。

总结：边结点存放的该结点下标是什么颜色就找这个颜色指针指向的边界点。直到指针指向NULL。另一个颜色就是该结点相连的结点下标。

总之用邻接多重表存放无向图很方便，想要找到和某个顶点相连的边是很方便的，同时每一条只会对应一个边界点，所以不用再像邻接表那也同时维护两份冗余的数据，删除顶点、删除边等操作效率高很多。

如删除AB之间连接的边，我们只需要顺着A中firstedge指向的边结点0|1，顺着对应颜色橙色找到下一个与A相连的边结点0|3，将firstedge指针指向这个0|3边结点即可。如下图：

如果要删除E整个结点，只需要将E边指向的边结点4|1和2|4删除，再将指向这两个边结点的2|1和2|3边结点对应指针域指向NULL即可。

$O(|V|+|E|)$ ，

2.6 总结

	邻接矩阵	邻接表	十字链表	邻接多重表
空间复杂度	$O(\|V\|^2)$	$O(\|V\|+2\|E\|)$ $O(\|V\|+\|E\|)$	$O(\|V\|)+\|E\|$	$O(\|V\|+\|E\|)$
找相邻边	$O(\|V\|)$	找有向图的入边必须遍历整个邻接表	很方便	很方便
删除边与顶点	删除边很方便，删除顶点需要大量移动数据	无向图中删除边或顶点都不方便	很方便	很方便
适用于	稠密图	稀疏图和其他	只能存储有向图	只能存储无向图
表示方式	唯一	不唯一	不唯一	不唯一

3. 图的基本操作

考研常考邻接矩阵和邻接表这两中结构。所以这里主要讲这两种存储结构的基本操作。

$Adjacent(G,x,y)$ ：判断图G是否存在边<x, y>或(x,y)。
1. 对于邻接矩阵存储无向图：
  判断很方便，如上图要找B和D之间是否有边，只需要B行和D1 $O(1)$ 。
2. 对于邻接表存储无向图：
  要找B和D之间是否有边，我们要先遍历B的边结点指针有没有D结点，也就是后面链表data域有没有3*first $O(1)$ 。最坏情况遍历完整个B的边结点也没有发现要找的结点，而和Bn-1 $O(|V|)$ $O(1)\sim O(|V|)$ 。
3. 邻接矩阵和邻接表存储有向图分析同上。
$Neighbors(G,x)$ ：列出图G中与结点x邻接的边。
1. 对于邻接矩阵存储无向图：
  1 $O(|V|)$
2. 对于邻接表存储无向图：
  *first $O(1)\sim O(|V|)$
3. 对于邻接矩阵存储有向图方法同上，而邻接表存储时候我们需要考虑入边和出边：
  *first $O(1)\sim O(|V|)$ 。
  而对于入边，由于邻接表的缺点只能遍历所有data*first $O(|E|)$ 。
  所以列出图G中与结点x邻接的边这个操作用邻接矩阵存储有向图是更优秀的方案。但如果邻接表存储的是稀疏图，可能优于邻接矩阵。
$InsertVertex(G,x)$ 在图G中插入顶点x。
1. 对于邻接矩阵存储无向图
  只需要在data后面写入新的结点x即可。由于矩阵已经完成了初始化，所以x0 $O(1)$ 。
  邻接矩阵插入新元素：
2. 对于邻接表存储无向图：
  同样只需要在data域中写入x即可，*firstNULL $O(1)$ 。
3. 邻接矩阵和邻接表存储有向图分析同上。
$DeleteVertex(G,x)$ ：从图G中删除顶点x。
1. 对于邻接矩阵存储无向图
  一个简单方法是，在data中删除这个结点后，再把矩阵跟这个结点相关的行和列都变为0即可。对于如何在data中删除这个结点，可以设置一个bool0 $O(|V|)$ 的时间复杂度即可完成。
2. 对于邻接表存储无向图
  我们在data中删除该顶点后，除了要将该结点的*first置空，同时要将其他顶点*first边链表中包含该删除顶点下标的链表结点也要删除。如下删除C顶点：
  $O(1)$ $O(|E|)$ 。
3. 对于邻接矩阵存储有向图方法同上，而邻接表删除顶点时候我们需要考虑入边和出边
  删除顶点的出边很方便只要删除*first指向的边链表即可。而要删除入边，那就需要遍历整个邻接表找*first指向的边链表包含被删除顶点下标的结点删除即可。
  $O(1)\sim O(|V|)$ $O(|E|)$ 。
  所以列出图G中删除顶点x这个操作用邻接矩阵存储有向图是更优秀的方案。但如果邻接表存储的是稀疏图，可能优于邻接矩阵。
$AddEdge(G,x,y)$ ：若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边。(x,y之间没有变，则添加一条)
1. 对于邻接矩阵存储无向图
  直接将矩阵中x行y1 $O(1)$ 。
2. 对于邻接表存储无向图
  假如添加C和F之间的一条边，需要在各自结点*first对方 $O(1)$ 。
3. 邻接矩阵和邻接表存储有向图分析同上。
$FirstNeighbor(G,x)$ ：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1
1. 对于邻接矩阵存储无向图
  1 $O(1)$ $O(|V|)$
2. 对于邻接表存储无向图
  *first $O(1)$ 时间复杂度。
3. 对于邻接矩阵存储有向图
  对于出边要扫描该顶点对应的行；入边要扫描列。
4. 对于邻接表存储有向图
  *first $O(1)$ 。
  $O(1)\sim O(|E|)$
$NextNeighbor(G,x,y)$ ：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
1. 对于邻接矩阵存储无向图
  1 $O(1)\sim O(|V|)$ 。
2. 对于邻接表存储无向图
  *first $O(1)$ 时间复杂度。
3. 邻接矩阵和邻接表存储有向图分析同上。
$GetEdgeValue(G,x,y)$ ：获取图G中边(x, y)或<x, y>对应的权值。
$SetEdgeValue(G,x,v)$ ：设置图G中边(x, y)或<x, y>对应的权值为v。
这两个操作同上 $Adjacent(G,x,y)$ ，其核心在于找边

此外，还有图的遍历算法，包括深度优先遍历和广度优先遍历。

4. 图的广度优先搜索

树的广度优先搜索是层次遍历。图的广度优先搜索和树的类似。如下无向图：

从顶点2出发，可以遍历到顶点1和顶点6，接着再根据顶点1和6找到其他顶点，即5,3,7三个顶点。接着再从这三个顶点出发找到更下一层的4,8两个顶点。这个过程和树很类似。两个结构对比如下：

树搜索不存在"回路"，搜索相邻的结点时，不可能搜到已经访问过的结点。树BFS算法步骤如下： ①若树非空，则根节点入队 ②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队 ③重复②直到队列为空

图在搜索相邻的顶点时，有可能搜到已经访问过的顶点。如上无向图，通过6顶点可以访问到2,3,7三个顶点，但此时2结点已经访问过了，仍会再次访问。解决方法也很简单，只需要给各个结点一个标记，来标记结点有没有被访问即可。

4.1 图的BFS实现

图的BFS算法如下：

找到与一个顶点相邻的所有顶点
标记哪些顶点被访问过
需要一个辅助队列

FirstNeighbor(G,x) $x$ $x$ $x$ $-1$ 。
NextNeighbor(G,x,y) $y$ $x$ $y$ $x$ $y$ $x$ $-1$ 。
定义一个bool visited[MAX_VERTEX_NUM];记录访问标记数组，初始值全为false。

实现代码如下：


xxxxxxxxxx
18
1
bool visited[MAX_VERTEX_NUM]; // 访问标记数组.
2
//广度优先遍历
3
void BFS(Graph G,int v){    //从顶点v出发，广度优先遍历图G
4
    visit(v);               //访问初始顶点v
5
    visited[v]=TRUE;        //对v做已访问标记
6
    Enqueue(Q,v);           //顶点v入队列Q
7
    while(!isEmpty(Q)){
8
        v=FrontQueue();
9
        DeQueue(Q,v);       //顶点v出队列
10
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
11
            //检测v所有邻接点
12
            if(!visited[w] ){       //w为v的尚未访问的邻接顶点
13
                visit(w);           //访问顶点W
14
                visited[w]=TRUE;    //对w做已访问标记
15
                EnQueue(Q,w);       //顶点w入队列
16
            }
17
    }
18
}

图存储结构：

visited数组：

	1	2	3	4	5	6	7	8
visited	false	false	false	false	false	false	false	false

假如先从2顶点开始遍历：

先访问2号顶点，再将2号顶点对应的visited数组设为true
1 2 3 4 5 6 7 8
visited false true false false false false false false
之后将2号顶点入队，进入while循环，判断队列是否为NULL，不为NULL将队中2顶点出队，进入for循环
for循环中先获取与2顶点相邻顶点1，访问1号顶点后将对应visited数组设为true，再入队。NextNeighbor(G,v,w)再获取邻接点下一个顶点即6，同样，访问后数组设置为true后再入队。此时6顶点已经为2顶点最后一个邻接点，结束循环，进入外层while循环。
1 2 3 4 5 6 7 8
visited true true false false false true false false
此时队列为：1,6
循环1，2，3步，得到该无向图的BFS序列为：2，1，6，5，3，7，4，8

	1	2	3	4	5	6	7	8
visited	false	true	false	false	false	false	false	false

	1	2	3	4	5	6	7	8
visited	true	true	false	false	false	true	false	false

同样，从顶点1出发得到的广度优先序列为：1，2，5，6，3，7，4，8

对于BFS算法，如果图的存储结构不一样，得到的遍历序列也可能不一样。但对于邻接矩阵来说，它的存储方式是唯一的，所以其BFS遍历顶点其他邻接点时，一定是从小到大遍历。

4.2 图BFS遍历非连通图

有以下非连通图：

上面的代码不能访问9,10,11顶点。这个问题可以通过visited数组解决。解决代码如下：


xxxxxxxxxx
26
1
bool visited[MAX_VERTEX_NUM];   // 访问标记数组.
2
void BFSTraverse(Graph G){      //对图G进行广度优先遍历
3
    for(i=0; i<G.vexnum;++i)
4
        visited[i]=FALSE;       //访问标记数组初始化
5
    InitQueue(Q);               //初始化辅助队列Q
6
    for(i=1;i<G.vexnum;++i)     //从1号顶点开始遍历
7
        if(!visited[i])         //对每个连通分量调用一次BFS
8
            BFS(G,i);           //vi未访问过，从vi开始BFS
9
}
10

11
//广度优先遍历
12
void BFS(Graph G,int v){    //从顶点v出发，广度优先遍历图G
13
    visit(v);               //访问初始顶点v
14
    visited[v]=TRUE;        //对v做已访问标记
15
    Enqueue(Q,v);           //顶点v入队列Q
16
    while(!isEmpty(Q)){
17
        DeQueue(Q,v);       //顶点v出队列
18
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
19
            //检测v所有邻接点
20
            if(!visited [w] ){      //w为v的尚未访问的邻接顶点
21
                visit(w);           //访问顶点W
22
                visited[w]=TRUE;    //对w做已访问标记
23
                EnQueue(Q,w);       //顶点w入队列
24
            }
25
    }
26
}

以上代码在BFSTraverse函数中会先从1号顶点开始遍历，对每个连通分量检查是否访问，没有访问则调用BFS。

假如从1号结点开始访问，BFSTraverse函数第一次调用BFS会遍历1~8顶点，此时visited数组如下：

接着BFSTraverse函数会一直遍历直到发现没有访问的顶点9，接着从9号顶点开始继续调用BFS，之后BFS函数会访问10,11顶点。此时所有顶点访问完毕，结束循环。

结论 $=$ 连通分量数。

4.3 图的BFS算法复杂度分析

$O(|V|)$
时间复杂度：
- 邻接矩阵存储的图：
  $|V|$ $O(|V|)$ $O(|V|)$ $|V|$ $= O(|V|^2)$
- 邻接表存储的图：
  $|V|$ $O(|V|)$ $O(|E|)$ $= O(|M|+|E|)$

这里显然不能分析BFS函数最深层的forfor $0$ $O(|V|)$ 次。

4.4 广度优先生成树与森林

广度优先生成树

上面BFS遍历序列中，红色的边表示顶点第一次被访问的时候是从哪个边过去的。如上面43 $n$ $n-1$ 条边。

如果把上面没有标红边去掉，则得到以下图：

这个图实际上变为了树，因为里面已经没有回路出现了。这个树就是广度优先生成树。

转换成生成树如下：

同样的，通过邻接表存储的图生成树不唯一。

广度优先生成森林

同样对非连通图的广度优先遍历，可得到广度优先生成森林：

5. 图的深度优先搜索

图的DFS与树一致，树的DFS是用先根遍历实现的：


xxxxxxxxxx
8
1
//树的先根遍历
2
void Pre0rder(TreeNode *R) {
3
    if (R!=NULL){
4
        visit(R)                //访问根节点
5
            while(R还有下一个子树T)
6
                Pre0rder(T);    //先根遍历下一棵子树 
7
    }
8
}

以上树的先根遍历序列是：1，2，5，6，3，4，7，8

5.1 图的DFS实现

由于树的特性树的遍历新找到的结点肯定是没被访问过的结点。但图遍历的新结点有可能是已经被访问的。所以同广度优先搜索一样，同样要设置一个visited数组标记顶点有没有访问过。

DFS遍历上面无向图，需要先初始化visited数组为false：

	1	2	3	4	5	6	7	8
visited	false	false	false	false	false	false	false	false

代码实现如下：


xxxxxxxxxx
9
1
bool visited [MAX_VERTEX_NUM];      // 访问标记数组
2
void DFS(Graph G,int v){            //从顶点v出发，深度优先遍历图G
3
    visit(v);                       //访问顶点v
4
    visited[v]=TRUE;                //设已访问标记
5
    for(w=FirstNeighbor(G,v);w>=0;w=nextNeighbor(G,v,w))
6
        if(!visited[w]){            //w为u的尚未访问的邻接顶点
7
            DFS(G,w);
8
        }
9
}

代码执行步骤如下：

假设从2号顶点出发，先访问2号，再将其对应visited数组设置为true；接着进入for循环内部，先获取2号顶点下一个邻接点1，1号邻接点显然没有被访问，进入递归函数DFS，递归遍历1号顶点。
visited数组：
函数调用栈：
重复执行第一步操作，在进入for循环后获取1号邻接点2，2顶点已经访问，所以不会进入递归，再和1号邻接的点为5，5号顶点进入递归
visited数组：
函数调用栈：
重复第一步操作，5号顶点访问完毕后，由于没有邻接点，本层递归执行结束，依次出栈：由于1号顶点5顶点已经是最后一个邻接点，所以1号顶点出栈；2号顶点已经处理了第一个邻接点，接着进入第二次循环处理邻接点6，6顶点没有访问进入递归。
visited数组：
函数调用栈：
访问6号顶点并设置visited数组后，进入for循环。第一个邻接点是2，已经访问过，接着访问下一个邻接点3，顶点3没有被访问过，同样进入递归。
visited数组：
函数调用栈：
访问3号顶点设置visited数组后，进入for循环。其第一个邻接点是4号顶点，没有被访问进入递归。
visited数组：
函数调用栈：
访问完4号顶点后，由于其第一个邻接点3已经被访问过，所以访问下一个邻接点7，进入递归。
visited数组：
函数调用栈：
访问完7号顶点后，与7相邻的顶点只有8没有被访问，进入递归
visited数组：
函数调用栈：
在访问完8号顶点后，由于与之相邻的邻接点都已经被访问过，所以循环结束，本次递归结束，依次出栈：7号顶点与之相邻的顶点都被访问完，同样结束出栈；其他层递归过程类似，全部出栈。

所以从2号顶点出发得到的DFS序列为：2，1，5，6，3，4，7，8

5.2 图DFS遍历非连通图

有以下非连通图：

上面的代码并不能访问9,10,11顶点。这个问题可以通过visited数组解决。解决代码如下：


xxxxxxxxxx
16
1
bool visited[MAX_VERTEX_NUM];       //访问标记数组
2
void DFSTraverse(Graph G){          //对图G进行深度优先遍历
3
    for(v=0; v<G.vexnum; ++v)
4
        visited[v]=FALSE;           //初始化已访问标记数据
5
    for(v=0;v<G.vexnum; ++v)        //本代码中是从v=0开始遍历
6
        if(!visited[v])
7
            DFS(G,v);
8
}
9
void DFS(Graph G,int v){            //从顶点v出发，深度优先遍历图G
10
    visit(v);                       //访问顶点v
11
    visited [v]=TRUE;               //设已访问标记
12
    for(w=FirstNeighbor(G,v);W>=0;w=NextNeighor(G,v,w))
13
        if(!visited[w]){            //w为u的尚未访问的邻接顶点
14
            DFS(G,w);
15
        }
16
}

以上代码在DFSTraverse函数中会先从1号顶点开始遍历，对每个连通分量检查是否访问，没有访问则调用DFS。

假如从1号结点开始访问，DFSTraverse函数第一次调用DFS会遍历1~8顶点，此时visited数组如下：

接着DFSTraverse函数会一直遍历直到发现没有访问的顶点9，接着从9号顶点开始继续调用DFS，之后DFS函数会访问10,11顶点。此时所有顶点访问完毕，结束循环。

其他顶点出发得到的遍历序列(邻接表存储不唯一)：

从2出发的深度优先遍历序列：2，1，5，6，3，4，7，8

从3出发的深度优先遍历序列：3，4，7，6，2，1，5，8

从1出发的深度优先遍历序列：1，2，6，3，4，7，8，5

5.3 图的DFS算法复杂度分析

$O(|V|)$
$+$ 探索各条边所需时间
- 邻接矩阵存储的图：
  $|V|$ $O(|N|)$ $O(|V|)$ $|V|$ $=O(|V|^2)$
- $|V|$ $O(|V|)$ $O(|E|)$ $=O(|V|+|E|)$

5.4 深度优先生成树与森林

深度优先生成树
如果通过某一条边找到了一个还没有被访问的顶点，那么这条边标记为红色，上面的DFS遍历后标记如下：
去掉没有标记红色的边，得到的就是一个没有回路的无向图，此时可以转换为树，这个树就被称为深度优先生成树。
同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一，深度优先生成树也唯一
同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一，深度优先生成树也不唯一
深度优先生成森林
同样对非连通图的深度优先遍历，可得到深度优先生成森林：

5.5 图的遍历与图的连通性

无向图：
对无向图进行BFS/DFS遍历，调用BFS/DFS函数的次数=连通分量数
而对于连通图，只需调用1次BFS/DFS。
对有向图进行BFS/DFS遍历调用BFS/DFS函数的次数要具体问题具体分析若起始顶点到其他各顶点都有路径, 则只需调用1次 BFS/DFS函数
有向图：
对有向图进行BFS/DFS遍历，调用BFS/DFS $1$ 次BFS/DFS $1$ 次BFS/DFS
强连通图：

6. 图的应用

6.1 最小生成树

前面介绍过生成树的概念。生成树的概念是：包含图中全部顶点的一个极小连通子图。边要尽可能的少，但要保持连通。

$G=(V, E)$ $R$ $G$ $T$ $R$ $T$ $G$ 的最小生成树(Minimum-Spanning-Tree, MST)。

有以下无向图：

P城要进行道路规划。道路规划要求：所有地方都连通，且成本尽可能的低。

图中边上的数字是修一条路所需成本。所以最小生成树就是一颗边上权之和最小的树。

最小生成树特点：

最小生成树可以有多个。但边的权值之和总是唯一且最小的。
$=$ $-1$ 。砍掉一条则不连通，增加一条边则会出现回路
如果一个连通图本身就是一棵树，则其最小生成树就是它本身
只有连通图才有生成树，非连通图只有生成森林

普利姆(Prim)算法

算法核心：

从某一个顶点开始构建生成树；

每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

上图最小生成树生成方式如下：

先从P城1 $P城——学校$ 。
$P城——学校$ ，相连的最小边为4，即矿场渔村 $P城——矿场$ 。
$P城——学校——矿场$ 2 $矿场——渔村$
$P城——学校——矿场——渔村$ 5 $农场——P城$
$P城——学校——矿场——渔村——农场$ 3 $农场——电站$

$P城——渔村$ ，最后的最小生成树权值和仍为15：

代码实现思路如下：

$V_0$ 开始创建两个数组：

$V_0$ isJoin $V_0$ 对应标记为truelowCost $V_4$ $V_5$ $V_0$ $\infty$ 。

lowCast $V_3$ lowCoast $V_0$ isJoin $V_3$ 标记位true。
lowCast $V_1$ $V_2$ $V_4$ $V_5$ $V_0$ $V_3$ $V_3$ $V_0$ $V_1$ $V_3$ 5 $V_2$ $V_4$ 4 $V_4$ $V_5$ 变为6和4。
变化后的数组如下：
lowCast $V_2$ 4 $V_0——V_3$ 树中。
lowCast $V_2$ $V_5$ $V_5$ $V_2$ 2 $V_5——V_3$ 边的权4lowCast $V_5$ 对应的值改为2：
第三轮循环继续之前操作。

克鲁斯卡尔(Kruskal)算法

算法核心：

每次选择一条权值最小的边，使这条边的两头连通(原本已经连通的就不选)，直到所有结点都连通。

用Kruskal得到上图最小生成树方式如下：

先找到权值最小的边，为1，这条边两边顶点是学校，P城市且没有连通，连通这两个顶点
接着在剩下边中找权值最小的，即2，两边顶点是矿场和渔场且没有连通，连接这两个点
剩下边中最小的是3，两边顶点是农场和电站，且没有连通
接着权值最小的是4，两个为4的边任意选一条即可
剩余权值最小的边是4，但由于矿场已经连通P城，所以跳过。接着选剩下边中最小的5将农场和P城连接

代码实现思路如下：

首先初始化将各条边按权值排序

$1$ 条边的两个顶点是否连通(是否属于同一个集合，可以参考之间的并查集)
1 $V_0$ $V_3$ 两个顶点，通过并查集查询两个顶点不是在同一集合中，则将其连接。
$V_0$ $V_3$ 合并为一个集合中
2 $V_2$ $V_5$ $V_2$ $V_5$ 合并为一个集合中。
3 $V_1$ $V_4$ $V_1$ $V_4$ 合并为一个集合中。
4 $V_2$ $V_3$ $V_2$ $V_3$ 合并为一个集合中。
4 $V_3$ $V_5$ 两个顶点，通过并查集查询两个顶点已经在同一集合中，则跳过
后面同上。

两个算法比较

普利姆(Prim)算法：
$O(|V|^2)$ ，适合用于边稠密图。
克鲁斯卡尔(Kruskal)算法：
$O(|E|\log2|E|)$ ，适合用于边稀疏图。

6.2 最短路径问题

有以下无向图：

第一个问题是：

G港是个物流集散中心，经常需要往各个城市运东西，求运送距离最近路径。这种问题可以归类为单源(从一个顶点出发)最短路径问题。

解决方法用：BFS算法(无权图)、Dijkstra算法(带权图、无权图)解决。

第二个问题是：

各个城市之间也需要互相往来，相互之间怎么走距离最近?这类问题归类为：每对顶点间的最短路径。

解决方法是：Floyd算法(带权图、无权图)。

BFS算法解决最短路径

有以下无权的无向图：

$1$ .

假设从顶点2出发BFS算法遍历过程参考图的BFS实现。通过BFS遍历便可以得到2顶点到各个顶点的距离。

修改BFS算法的visit(w)方法：


xxxxxxxxxx
21
1
void BFS_MIN_Distance(Graph G,int u){
2
    //d[i]表示从u到i结点的最短路径
3
    for(int i=0;i<G.vexnum;++i){
4
        d[i]=0x3f3f3f3f; //初始化路径长度为无穷大
5
        path[i]=-1; //最短路径从哪个顶点过来
6
    }
7
    d[u]=0;
8
    visited[u]=TRUE;        //对v做已访问标记
9
    Enqueue(Q,u);           //顶点v入队列Q
10
    while(!isEmpty(Q)){
11
        u=DeQueue(Q,u);         //顶点v出队列
12
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))
13
            //检测v所有邻接点
14
            if(!visited[w]){        //w为u的尚未访问的邻接顶点
15
                d[w]=d[u]+1;        //路径长度加1    
16
                path[w]=u;          //最短路径应从u到w 
17
                visited[w]=TRUE;    //对w做已访问标记
18
                EnQueue(Q,w);       //顶点w入队列
19
            }
20
    }
21
}

第12行和12行修改后的代码。其中d[]数组是存放顶点w到遍历初始顶点u之间的长度；path[]数组作用存放当前遍历顶点的前一个顶点位置。两个数组初始化如下：

执行步骤如下：

假设从顶点u=2开始遍历，会先将顶点2的path对应的值设置为0，接着visited设置为true，并将2号顶点入队。
遍历2顶点的邻接点为1和6，访问这两个顶点时，由于d[u]=0，所以这两个顶点的d[w]=d[u]+1=1，其前一个顶点2，故path[w]=u
同样操作同上，执行完所有遍历操作后得到的d[]和path[]数组如下：

求得d[]和path[]数组后使用：假设要找2顶点到8号顶点的路径：

28 $=d[8]=3$ 通过path数组可知，28 $8\leftarrow7\leftarrow6\leftarrow2$

同时通过BFS得到的广度优先生成树，其树每个结点在第几层也直接反应了，其到初始顶点的距离。

BFS缺点：只能用于不带权的图，或所有边的权值都相同的图。

Dijkstra算法解决最短路径

可以解决带权图单源问题(从一点到另外几个点的最短路径)。其实现方法和Prim算法十分相似。

$V_0$ 点到其他顶点的最短路径。

其实核心思路是：dist $V_i$ $V_i$ 将其final值设置为truefinal=false $V_i$ 到各个邻接点权值是否小于邻接点原本的distpath $V_i$ 的位置即path[]=i。

$V_0$ 开始，初始化三个数组信息如下：

$V_0$ $V_0$ path[0]=-1 $V_0$ $V_1$ $V_4$ ，所以将初始化dist[1]=10和dist[4]=5，前驱path[1]=0path[4]=0 $V_2$ $V_3$ $V_0$ 连接的边所以dist[2]dist[3] $\infty$ ，path[2]和path[3]为-1。
final[5]：标记各个顶点是否已经找到最短路径。
$V_0$ $V_1$ $V_2$ $V_3$ $V_4$
true false false false false
dist[5]：最短路径的长度。
$V_0$ $V_1$ $V_2$ $V_3$ $V_4$
0 10 $\infty$ $\infty$ 5
path[5]：路径上的前驱
$V_0$ $V_1$ $V_2$ $V_3$ $V_4$
$-1$ $0$ $-1$ $-1$ $0$

$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
true	false	false	false	false

$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
0	10	$\infty$	$\infty$	5

$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
$-1$	$0$	$-1$	$-1$	$0$

循环执行以下步骤：

$1$ dist $V_i$ ，令final[i]=ture。即：
首先找到final数组不为truedist $V_i=V_4$ ；
$V_4$ 后先将其final[4]=true，表明这个顶点已经找到最短路径。其最短路径是dist[4]=5path[4]=0 $V_0$ $V_i$ 的顶点，若其final值为false，则更新dist和path信息。即：
$V_4$ $V_1$ $V_2$ $V_3$ 这几个顶点中finalfalse $V_4$ dist $V_1$ dist[1]=10 $V_4$ dist[4]=5 $V_1$ $8$ dist[1]=10 $V_1$ dist[1]=8path[1]=4 $V_2$ $V_3$ $V_4$ 点经过路径长度为147 $\infty$ ，所以dist[2]=14，dist[3]=7，path[2]=4，path[3]=4。处理完后数组信息如下：
final[5]：标记各个顶点是否已经找到最短路径。
$V_0$ $V_1$ $V_2$ $V_3$ $V_4$
true false false false true
dist[5]：最短路径的长度。
$V_0$ $V_1$ $V_2$ $V_3$ $V_4$
0 8 14 7 5
path[5]：路径上的前驱
$V_0$ $V_1$ $V_2$ $V_3$ $V_4$
$-1$ 4 4 4 $0$
第二轮循环同上。剩下final数组不为truedist $V_i=V_3$ ；先将其final[4]=true，表明这个顶点已经找到最短路径。其最短路径是dist[3]=7path[3]=4 $V_4$ $V_3$ $V_0$ $V_2$ $V_0$ 的finaltrue $V_2$ $V_3$ $V_2$ ，所需的权值为13dsit[2]=14 $V_2$ 的dist[2]=13，path[2]=3。处理完后数组信息如下：
final[5]：标记各个顶点是否已经找到最短路径。
$V_0$ $V_1$ $V_2$ $V_3$ $V_4$
true false false true true
dist[5]：最短路径的长度。
$V_0$ $V_1$ $V_2$ $V_3$ $V_4$
0 8 13 7 5
path[5]：路径上的前驱
$V_0$ $V_1$ $V_2$ $V_3$ $V_4$
$-1$ 4 3 4 $0$
第三轮，找剩下final=flasedist $V_1$ 。将其fianl值设置为true，并遍历其邻接点中finalfalse $V_2$ $V_1$ $V_2$ 8+1=9 $V_2$ dist[2]=13 $V_2$ 的dist[2]=9，path[2]=1。处理完后数组信息如下：
final[5]：标记各个顶点是否已经找到最短路径。
$V_0$ $V_1$ $V_2$ $V_3$ $V_4$
true true false true true
dist[5]：最短路径的长度。
$V_0$ $V_1$ $V_2$ $V_3$ $V_4$
0 8 9 7 5
path[5]：路径上的前驱
$V_0$ $V_1$ $V_2$ $V_3$ $V_4$
$-1$ 4 1 4 $0$
$V_2$ ，将其final值设置为true即可。处理完后数组信息如下：
final[5]：标记各个顶点是否已经找到最短路径。
$V_0$ $V_1$ $V_2$ $V_3$ $V_4$
true true true true true
dist[5]：最短路径的长度。
$V_0$ $V_1$ $V_2$ $V_3$ $V_4$
0 8 9 7 5
path[5]：路径上的前驱
$V_0$ $V_1$ $V_2$ $V_3$ $V_4$
$-1$ 4 1 4 $0$

$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
true	false	false	false	true

$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
0	8	14	7	5

$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
$-1$	4	4	4	$0$

$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
true	false	false	true	true

$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
0	8	13	7	5

$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
$-1$	4	3	4	$0$

$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
true	true	false	true	true

$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
0	8	9	7	5

$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
$-1$	4	1	4	$0$

$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
true	true	true	true	true

$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
0	8	9	7	5

$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
$-1$	4	1	4	$0$

得到上面的数组使用方法如下：

$V_0$ $V_2$ 的最短(带权)路径长度为：dist[2]=9path[] $V_0\rightarrow V_4\rightarrow V_1\rightarrow V_2$

代码实现思路如下：

$V_0$ 开始，令final[0]=ture；dist[0]=0；path[0]=-1final[k]=false $V_0$ $k$ $\infty$ dist[k]=arcs[0][k] $V_0$ $-1$ path[k]=(arcs[0][k]== $\infty$ )? -1:0

$n-1$ dist $V_i$ final[i]=ture $V_i$ $V_i$ $V_j$ ，若final[j]=false且dist[i]+arcs[i][j]<dist[j]，则令dist[j]=dist[i]+arcs[i][j]；path[j]=i。

arcs[i][j] $V_i$ $V_j$ 的弧的权值。

dist $O(n)$ $n-1$ $O(n^2)$ $O(|V|^2)$ 。

如果带权图中有带负权值的图：

用Dijkstra算法得到的数组如下：

final[3]：标记各个顶点是否已经找到最短路径。

$V_0$	$V_1$	$V_2$
true	true	true

dist[3]：最短路径的长度。

$V_0$	$V_1$	$V_2$
0	10	7

path[3]：路径上的前驱

$V_0$	$V_1$	$V_2$
$-1$	0	0

$V_0$ $V_2$ dist[2]=7 $V_0\rightarrow V_1\rightarrow V_2$ ，其路径长度为10-(-5)=5。故Dijkstra算法不适用于有负权值的带权图。

Floyd算法解决最短路径

可以求出每一对顶点之间的最短路径。其核心思想是使用动态规划思想，将问题的求解分为多个阶段。如：

$n$ $G$ $V_i\rightarrow V_j$ 之间的最短路径可分为如下几个阶段:

初始：不允许在其他顶点中转，最短路径是?
$V_0$ 中转，最短路径是?
$V_0$ $V_1$ 中转，最短路径是?
$V_0$ $V_1$ $V_2$ 中转，最短路径是?
$V_0$ $V_1$ $V_2\cdots V_{n-1}$ 中转，最短路径是?

其执行代码如下：


xxxxxxxxxx
10
1
for(int k=0;k<n;k++){////考虑以k作为中转点
2
    for(int i=0; i<n; i++) {//遍历整个矩阵， i为行号，j为列号
3
        for (int j=0; j<n; j++){
4
            if (A[i][j]>A[i][k]+A[k][j]){//以k为中转点的路径是否比原先的路径更短
5
                A[i][j]=A[i][k]+A[k][j];//更新最短路径长度
6
                path[i][j]=k;//中转点
7
            }
8
        }
9
    }
10
}

求以下带权图每对顶点之间的最短路径：

$V_0$ $k=0$ $V_0$ 所以没有一个点的路径需要更新。
$V_0,V_1$ $V_1$ $k=1$ $A[2][3]>A[2][1]+A[1][3]$ $V_2$ $V_1$ $V_1$ $V_3$ $V_2$ $V_3$ $A[2][3]=2$ 且path[2][3]=1
$A[2][4]>A[2][1]+A[1][4]$ $V_2$ $V_1$ $V_1$ $V_4$ $V_2$ $V_4$ $A[2][4]=6$ 且path[2][4]=1修改后的数组如下：
$V_0,V_1,V_2$ $V_2$ $k=2$ $A[0][1]>A[0][2]+A[2][1]$ $A[0][1]=2$ 且path[0][1]=2
$A[0][3]>A[0][2]+A[2][3]$ $A[0][3]=3$ path[0][3]=2 $V_2$ $V_3$ $V_2$ $V_3$ $V_2\rightarrow V_1\rightarrow V_3$ $V_2$ $V_3$ 的是有路径的。
$A[0][4]>A[0][2]+A[2][4]$ $A[0][4]=7$ 且path[0][4]=2。
$V_0,V_1,V_2,V_3$ $V_3$ $k=3$ $A[0][4]>A[0][3]+A[3][4]$ $A[0][4]=4$ 且path[0][4]=3
$A[1][4]>A[1][3]+A[3][4]$ $A[1][4]=2$ 且path[1][4]=3。
$A[2][4]>A[2][3]+A[3][4]$ $A[2][4]=3$ 且path[2][4]=3。
$V_4$ 为中转点时，没有要修改的值。

$V_0$ $V_4$ $A[0][4]=4$ 。path数组找路径如下：

$V_0\rightarrow V_4$
$V_0\rightarrow V_3\rightarrow V_4$
$V_0\rightarrow V_2\rightarrow V_3\rightarrow V_4$
$V_0\rightarrow V_2\rightarrow V_1\rightarrow V_3\rightarrow V_4$

这个过程可以通过遍历path[]数组递归实现，代码实现如下：


xxxxxxxxxx
7
1
void printPath(int i,int j){
2
    if(path[i][j]==-1) cout<<i;
3
    else{
4
        printPath(i,path[i][j]);
5
        printPath(path[i][j],j);
6
    }
7
}

$O(n^3)$ ，所以一般情况下三阶矩阵情况多。并且Floyd算法可以解决带负权值的带权图。但Floyd算法不能解决带有负权回路的图。因为这种图可能没有最短路径。如下：

从图上可知有两条边的权值为7<-9，这样的图又形成了回路，走的越多权值越小。所以没有最短路径。

6.3 总结

7. 有向无环图(DAG图)

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图(Directed Acyclic Graph)

7.1 DAG应用——有向无环图表达式

$((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)$ .其树形存储结构如下：

这些树结点存在有重复的部分，我们可以将其合并：

合并后的图是一个有向无环图。

具体步骤如下：

把各个操作数不重复地排成一排
标出各个运算符的生效顺序(先后顺序有点出入无所谓)
按顺序加入运算符，注意分层
自底向上逐层检查同层的运算符是否可以合体

有表达式(符号运算优先级已经标记，可不唯一)：

先把表达式中操作数去重排列
运算符连接操作数，但注意层次。如操作符需要用到下一层两个操作数运算结果，则这个操作符应该在操作数符号运算的上一层。
$c+d$ 的操作，所以可以合并。
$(c+d)*e$ 的操作，所以可以合并。而再往上操作符都是单独的，所以不可能合并。故这个DAG图如下：

$12$ 。

7.2 DAG应用——拓扑排序

AOVDAG $<V_i, V_j>$ $V_i$ $V_j$ 进行。注意AOV网不能有环路。

这是一个表示"番茄炒蛋"工程的AOV网。上面切番茄有个入边，表示其执行这个步骤前要先执行入边对应的顶点，即切番茄前要洗番茄。

$B$ $A$ 的路径。

上面项目可以先准备厨具也可以先买菜：

接着买菜：

此时洗番茄或者打鸡蛋，这里选洗番茄：

之后切番茄也可以打鸡蛋：

之后的顺序就是：打鸡蛋、下锅炒、吃

所以这个工程的拓扑排序是：准备厨具、买菜、洗番茄、切番茄、打鸡蛋、下锅炒、吃

拓扑排序代码实现

通过上面这个例子可以归纳处拓扑排序实现方式：

AOV $0$ )的顶点并输出。 ②从网中删除该顶点和所有以它为起点的有向边。 ③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。

同时每个AOV网都有一个或多个拓扑排序序列。拓扑排序代码实现如下：


xxxxxxxxxx
35
1
#define MaxVertexNum 100//图中顶点数目的最大值
2
typeder struct ArcNode{     //边表结点
3
    int adjvex;             //该弧所指向的顶点的位置
4
    struct ArcNode * nextarc;//指向下一条弧的指针
5
    //InfoType info;        //网的边权值
6
} ArcNode;
7
typedef struct VNode{       //顶点表结点
8
    VertexType data;        //顶点信息
9
    ArcNode *firstarc;      //指向第一条依附该顶点的弧的指针
10
}VNode,AdjList[MaxVertexNum];
11
typedef struct{
12
    AdjList vertices;       //邻接表
13
    int vexnum, arcnum;     //图的顶点数和弧数
14
} Graph;                    //Graph是以邻接表存储的图类型
15

16
bool TopologicalSort(Graph G){
17
    InitStack(S);               //初始化栈， 存储入度为0的顶点
18
    for(int i=0; i<G.vexnum;i++)
19
        if(indegree[i]==0)
20
            Push(S,i);          //将所有入度为0的顶点进栈
21
    int count=0;                //计数，记录当前已经输出的顶点数
22
    while(!IsEmpty(S)){         //栈不空，则存在入度为0的顶点
23
        Pop(S,i);               //栈顶元素出栈
24
        print [count++]=i;      //输出顶点i
25
        for(p=G.vertices[i].firstarc;p;p=p->nextarc){//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈s
26
            v=p->adjvex;
27
            if(!(--indegree[v]))
28
                Push(S,v);      //入度为0， 则入栈
29
        }
30
    }//while
31
    if (count<g.vexnum)
32
        return false;           //排序失败，有向图中有回路
33
    else
34
        return true;            //拓扑排序成功
35
}

上面代码执行方式如下：

有一AOV网：

其邻接表存储结构如下：

初始化数组indegree[]print[] $/$ s $0$ 的顶点)如下：

$19\sim21$ for $0$ indegree[] $0$ 的顶点有0和1。
在whileprint[] $0$ 的顶点放入拓扑序列中。
while中的for循环将与2号顶点相连的顶点的indegree对应值-1，即将3和4的indegree值-1。这在逻辑上相当于删除2号结点的出边。之后判断3和4indegree $0$ $0$ 则入栈。
while循环第二次循环弹出0号顶点，重复以上操作。最后要判断count的值是否等于结点数vexnum的值。如果小于，证明图中有环路，排序失败。

最后拓扑排序序列为：2，0，1，3，4

$O(|V|+|E|)$ $O(|V|^2)$

逆拓扑排序

对一个AOV网，如果采用下列步骤进行排序，则称之为逆拓扑排序： ①从AOV网中选择一个没有 $0$ )的顶点并输出。 ②从网中删除该顶点和所有以它为终点的有向边。 ③重复①和②直到当前的AOV网为空。

上面图的逆拓扑排序为：吃、下锅炒、切番茄、洗番茄、打鸡蛋、准备厨具、买菜。

注意逆拓扑排序当删除一个顶点后，需要同时删除指向这个顶点的边。如果采用邻接表存储，找一个顶点指向的边较为复杂需要遍历整个邻接表，显然十分低效。而如果采用邻接矩阵当删除一个顶点后想要找到这个顶点对应的边，只需要遍历这一列即可。

同样这里可以使用逆邻接表方式存储图，即邻接表保存的是入边信息，而逆邻接表存放的是出边的信息。逆邻接表存储如下：

如上面3顶点，其邻接表存放的入边顶点，即1顶点和2顶点同时指向了3顶点。这样也十分方便。

DFS实现逆拓扑排序

DFS实现逆拓扑排序：在顶点退栈前输出。

实现方式如下：


xxxxxxxxxx
16
1
void DFSTraverse(Graph G){      //对图G进行深度优先遍历
2
    for(v=0;v<G. vexnum; ++v)
3
        visited [v]=FALSE;      //初始化已访问标记数据
4
    for(v=0; v<G.vexnum; ++v)   //本代码中是从v=0开始遍历
5
        if( !visited[v])
6
            DFS(G,v);
7
}
8
void DFS(Graph G,int v){        //从顶点v出发，深度优先遍历图G
9
    visit(v);                   //访问顶点v
10
    visited[v]=TRUE;            //设已访问标记
11
    for(w=FirstNeighbor(G,v);W>=0;w=NextNeighor(G,v,W))
12
        if( !visited[w]){       //w为u的尚未访问的邻接顶点
13
            DFS(G,W);
14
        }
15
    print(v);
16
}

上面代码相对于正常DFS算法新加一行print(v);。执行大致步骤如下：

先通过0号顶点，进入递归，一直递归到4号顶点，此时4号顶点没有邻接点，所以打印第一个顶点是4。此时栈如下：
4号顶点打印完毕后，出栈，栈顶3号顶点唯一邻接点4已经访问过，所以打印出栈。
对于栈中1号顶点和0号顶点同样依次出栈打印。
接着DFSTraverse()函数中for循环会对没有进行访问2号顶点调用DFS()函数，由于2号顶点所有邻接点均已访问，所以直接打印结束。

所以用DFS逆拓扑排序序列为：4，3，1，0，2

如果有回路情况下可以加一个形参flag来记录当前递归调用次数，如果次数大于顶点数vexnum则表示有环路存在，退出循环。也可以通过if(NextNeighor(G,v,W)&&visited[w])，即下一个邻接点存在，并且还被访问过，就代表图有回路存在。

8. 关键路径

AOE网：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销(如完成活动所需的时间)，称之为用边表示活动的网络，简称AOE网(Activity On Edge NetWork)

上面图是一个AOE网，上面图入边指向的顶点表示，前一个出边的顶点需要在入边顶点之前完成。也就是说上图V_1顶点开始之后，才能进行打鸡蛋洗番茄 $V_3$ $V_3$ 顶点的事件。所以AOE网有以下性质：

只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的。
$0$ $0$ 的顶点，称为结束顶点(汇点)，它表示整个工程的结束。

关键路径：从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。

$V_1\rightarrow V_3\rightarrow V_4$ $V_1\rightarrow V_2\rightarrow V_3\rightarrow V_4$

$V_1\rightarrow V_2\rightarrow V_3\rightarrow V_4$ 路径长度最大，所以是关键路径。

求关键求法：

$ve(k)$ $ve(k)$ ：决定了所有从以开始的活动能够开工的最早时间。如上图：洗番茄最早开工时间是1切番茄 $3$ 分钟并且必须要等洗番茄完成后进行，所以切番茄最早开工时间是3+1=4，而打鸡蛋这个事件可以在洗番茄切番茄 $V_3$ $4$ 炒菜 $V_4$ 结束最早时间是4+2=6分钟。
$a_i$ $e(i)$ $a_i$ $V_2$ $V_1$ $1$ $V_3$ $V_2$ $1$ $V_4$ $V_3$ $4$ 。
$v_k$ $vl(k)$ ：它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。
$a_i$ $l(i)$ ：它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。
$V_3$ 必须在4这个时刻开始，而打鸡蛋又需要两分钟时间，所以打鸡蛋这个活动最晚可以23 $V_3$ 4 $4-3=1$ 这个时间进行。下面绿色标记的是活动最迟开始时间：
将活动最早开始时间和最晚开始时间放在一起(红色最早开始时间，绿色最晚开始时间)：
$0$ 时刻立即开始或者2分钟后开始，剩下的活动最早开始时间和最晚开始时间都是一样的，即这些活动时间都不能延后。
$a_i$ $d(i)=l(i)-e(i)$ $a_i$ $a_i$ $0$ $a_i$ 是关键活动。
由关键活动组成的路径就是关键路径。

求关键路径步骤：

$ve()$
$vl()$
$e( )$
$l()$
$d( )$ $d(i)=0$ 的活动就是关键活动，由关键活动可得关键路径。

$ve()$ $e()$ $vl()$ $vl()$ $vl()$ $l()$ $e( )$ $l()$ $d( )$ 。

算法实现步骤：

求上图的关键路径：

$ve()$
$ve(k)$ $ve(源点)=0$ $ve(k) = \max\{ve(j) + Weight(v_j,v_k)\}$ $v_j$ $v_k$ 的任意前驱
$V_1$ $V_3$ $V_2$ $V_5$ $V_4$ $V_6$
$ve(1)=0$ $ve(3)=ve(1)+a_2=2$ $ve(2)=ve(1)+a_1=3$ $ve(5)=ve(2)+a_4=6$ $ve(4)=\max\{ve(2) +2,ve(3)+4\}$ $ve(6)=\max\{ve(5)+1, ve(4)+2, ve(3)+3\}=8$
$vl()$
$vl(k)$ $vl(汇点)= ve(汇点)$ $vl(k)=\min\{v(j)-Weight(v_k, v_j)\}$ $v_j$ $v_k$ 的任意后继
$V_6$ $V_4$ $V_5$ $V_2$ $V_3$ $V_1$
$vl(6)=8$ $vl(5)=vl(6)-a_8=7$ $vl(4)=vl(6)-a_7=6$ $vl(2)=\min\{vl(5)-a_4,vl(4)-a_3\}=4$
$vl(3)=\min\{vl(4)-a_5,vl(6)-a_6\}=2$ $vl(1)=\min\{vl(2)-a_1,vl(3)-a_2\}=0$
$e()$
$<v_k, v_j>$ $a_i$ $e(i) = ve(k)$ $ve$ 值。
$l()$
$<v_k, v_j>$ $a_i$ $l(i) = vl(j) - Weight(v_k, v_j)$ $vl$ 值减去这条边的权值。
$vl()-$ 这条弧的权值。
$d()$
$d(i)= l(i)-e(i)$
$d(k)$ $a_2,a_5,a_7$ $0$ ，代表关键活动，所以关键路径为：

关键活动、关键路径特性：

若关键活动耗时增加，则整个工程的工期将增长
缩短关键活动的时间，可以缩短整个工程的工期
当缩短到一定程度时，关键活动可能会变成非关键活动
可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

十. 查找

查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找

查找表(查找结构)：用于查找的数据集合称为查找表，它由同一类型的数据元素(或记录)组成

关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

例子：

查找表：学生成绩信息(线性结构、可顺序可链式存储) 数据元素(记录)：每个学生的信息关键字：学号

查找表的常见操作：①查找符合条件的数据元素。②插入、删除某个数据元素

如果只进行①操作就是静态查找表，那仅仅关注查找速度即可。

$/$ 删操作是否方便实现。

1. 查找算法评价指标

查找长度：在查找运算中，需要对比关键字的次数称为查找长度

平均查找长度(TASL , Average Search Length)：所有查找过程中进行关键字的比较次数的平均值。ASL计算方法如下：

$/$ 查找失败两种情况的ASL。

2. 顺序查找

顺序查找，又叫线性查找，通常用于线性表。

算法思想：从头查到尾。

2.1 代码实现

$1$ ：


xxxxxxxxxx
11
1
typedef struct{//查找表的数据结构(顺序表)
2
    ElemType *elem;//动态数组基址
3
    int TableLen;//表的长度
4
}SSTable;
5
//顺序查找
6
int Search_Seq(SSTable ST, ElemType key){
7
    int i;
8
    for(i=0;i<ST.TableLen && ST.elem[i]!=key; ++i);
9
    //查找成功，则返回元素下标;查找失败，则返回-1
10
    return i==ST.TableLen? -1:i;
11
}

查找成功情况：

查找失败情况：

$2$ ：


xxxxxxxxxx
11
1
typedef struct{//查找表的数据结构(顺序表)
2
    ElemType *elem;//动态数组基址
3
    int TableLen;//表的长度
4
}SSTable;
5
//顺序查找
6
int Search_Seq(SSTable ST, ElemType key){
7
    ST.elem[0]=key; //"哨兵”，将查找元素key放入表头
8
    int i;
9
    for(i=ST.TableLen;ST.elem[i]!=key;--i); //从后往前找
10
    return i; //查找成功， 则返回元素下标;查找失败，则返回0
11
}

查找成功：

查找失败：

这种算法优点是：无需判定是否越界，效率更高。

2.2 查找效率分析

$2$ 为例：

$p_i=\frac{1}{n}$ $1·\frac{1}{n}+2·\frac{1}{n}+\cdots$ ，则

A S L_{成 功} = \frac{1 + 2 + 3 + \dots + n}{n} = \frac{n + 1}{2}

$n+1$ 次

A S L_{失 败} = n + 1

2.3 顺序查找的优化(有序表)

优化一：

$/$ 递减)

那么我们只用判断查找的元素在哪个区间内即可。加入要查找21元素，当我们遍历到29号元素时，21<29所以后面的就没必要查找。

$n+1$ $p_i=\frac{1}{n+1}$ ，则

A S L_{失 败} = \frac{1 + 2 + 3 + \dots + n + n}{n + 1} = \frac{n}{2} + \frac{n}{n + 1}

优化二：

如果每个元素被查概率不相等情况下，可以将被查概率大的放在靠前位置。

被查元素：

此时

A S L_{成 功} = 1 * 0.4 + 2 * 0.28 + 3 * 0.15 + 4 * 0.1 + 5 * 0.05 + 6 * 0.02 = 2.18

但对于查找失败情况仍和之前一样。

3. 二分查找(折半查找)

二分查找：仅适用于有序的顺序表。这是因为顺序表具有随机访问的特性，而链表没有。

3.1 查找步骤及实现

如下顺序表查找：

$\{7,10,13,16,19,29,32,33,37,41,43\}$ $33$

查找步骤是：

先用low和high两个指针分别指向数组的头部和尾部。而第一轮要检查元素是low和high中间的元素，用指针mid=(low+high)/2指向。即指向5位置上的29元素。而要查找的33元素大于29所以只有可能在mid指针右边。
所以将值改为low=mid+1，即32元素所在的位置。同样mid指针指向mid=(low+high)/2的位置，即位置8所在的37元素。
而元素33小于37，所以只可能在mid指针的左边。
将值改为high=mid+1，此时mid=[(low+high)/2]=6，所以mid指向6位置的32元素。
而33>32，所以只可能在mid指针的右边。即low=mid+1=7，同样mid=(low+high)/2=7，而位置7所在元素是33满足查找条件，查找成功。

看一个查找失败步骤：

$\{7,10,13,16,19,29,32,33,37,41,43\}$ $12$

前面查找过程一致，最后一步mid指向位置1所在10元素。而此时查找元素12仍然大于10，所以查找元素会在mid指针的右边。此时仍然会执行low=mid+1这个操作，之后low>high本来在左边指针跑到右边，所以查找失败，即在数组种没有查找到12这个元素。

代码实现如下：


xxxxxxxxxx
33
1
//折半查找
2
typedef struct{             //查找表的数据结构(顺序表)
3
    ElemType *elem;         //动态数组基址
4
    int TableLen;           //表的长度
5
}SSTable;
6
//方法一：
7
int Binary_Search(SSTable L,ElemType key){
8
    int low=0,high=L.TableLen-1,mid;
9
    while(low<=high){
10
        mid=(low+high)/2;   //取中间位置
11
        if(L.elem[mid]==key)
12
            return mid;     //查找成功则返回所在位置
13
        else if(L.elem[mid]>key)
14
            high=mid-1;     //从前半部分继续查找
15
        else
16
            low=mid+1;      //从后半部分继续查找
17
        return -1;          //查找失败，返回-1
18
    }
19
}
20
//方法二：
21
int Binary_Search(SSTable L,ElemType key){
22
    int low=-1,high=TableLen;
23
    while(low+1!=high){
24
        mid=(low+high)/2;
25
        if(L.elem[mid]==key)
26
            return mid;
27
        else if(L.elem[mid]>key)
28
            high=mid;
29
        else
30
            low=mid;
31
        return -1;
32
    }
33
}

3.2 查找的效率分析

上面例子中的表：

刚开始mid指针指向5所在位置29元素。此时有三种可能性：要么查找元素大于，要么小于，要么等于。如果小于就在mid左边查找，如果大于就在mid右边查找。

如果查找的元素小于29，那么此时mid指向13，如果大于29，mid指向37元素。如果仍然不是这两个元素中的任意一个，则继续上面操作。第三轮查找情况如下：

如果仍没有找到元素，则进入第四轮循环：

最后一轮如果查找失败，只需要补上失败区间即可：

上面元素如果在紫色方框内，则表示查找失败。

11 $p_i=\frac{1}{11}$ $1*1$ $2*2$ $3*4$ $4*4$ 。故

A S L_{成 功} = (1 * 1 + 2 * 2 + 3 * 4 + 4 * 4) / 11 = 3

12 $p_i=\frac{1}{12}$ 。第三层失败元素有四个，且要查找三次。第四次失败元素有八个，且要查找四次。故

A S L_{失 败} = (3 * 4 + 4 * 8) / 12 = 11 / 3

3.3 二分查找判定树构造

如果当前low和high之间有奇数个元素，则mid分隔后，左右两部分元素个数相等。

如果当前low和high之间有偶数个元素，则mid分隔后(这里是向下取整)，左半部分比右半部分少一个元素。

上图分割后构造树如下：

二分查找构造树特点：

$mid=[(low + high)/2]$ $-$ $=0$ $1$ 。
$1$ 。因此，只有最下面一层是不满的。
$n$ $h= [\log_2(n+ 1)]$ ， $h= \lceil \log_2(n+ 1)\rceil$ 是二分查找的最多比较次数。
$n+1$ (等于成功结点的空链域数量)

二分查找对比顺序查找：

$h= [\log_2(n+ 1)]$ $\le h$ $\le h$ $O(\log_2n)$ $O(n)$ 。显然二分查找可能优于顺序查找，但不一定完全优于顺序查找。如下：

使用顺序查找第一次就可以找到元素7，使用二分查找显然次数更多。

4. 分块查找

有以下数组：

数组中各个元素可以根据元素位置不同分成一个个小区间。如下：

划分不同区间后，数组变得有序，可以建立上级索引表。索引表当中保存每个分块的最大关键字和分块的存储区间。

不难看出分块查找特点是：块内无序，块间有序。其中索引表元素是区间数组块上的最大值。

4.1 分块查找实现

其算法过程如下：

在索引表中确定待查记录所属的分块(可顺序、可折半)
在块区间内顺序查找

假如查找元素是30，有两种方法：

顺序表查找：通过查找上级索引表，找到大于查找元素30的第一个索引元素。再根据30区间在数组中对比6到8这三个元素对应值是否包含30即可。
二分查找找元素同样计算mid=(low+high)/2指针指向的是30这个索引数组元素，而30=30，故查找数组下标区间6到8这三个元素对应值是否包含30即可。

假如查找元素是19，二分查找步骤如下：

如上图第一次查找mid指向的是索引表中30元素，由于30>19，故查找元素可能在索引表左边，所以high=mid-1，mid=(low+high)/2=0。
此时索引表mid指向的元素是10<19，所以low=mid+1，mid=(low+high)/2=1
索引表mid指向的元素是20>19，故查找元素可能在索引表左边，所以high=mid-1=0，此时low>high，所以二分查找结束。我们在low指向的分块中查找元素，当前low指向20元素区间是2,5，故在数组中找下标2到5之间的元素是否包含19。
注意：若索引表中不包含目标关键字(要查找的元素)，则折半查找索引表最终停在low>high的位置，此时要在low所指分块中查找。
这样做原因在于，索引表保存的是区间块上的最大值，而我们要找的元素要比索引元素小才有可能在数组区间中找到。即要保证找第一个比查找元素大的索引元素。

再看一个二分查找失败例子，假如查找元素是54，二分查找最后一步如下：

查找元素54大于表中所有元素，所以二分查找low指针一直往右移，当最后一次移动时low超出索引表范围，所以查找失败。

4.2 分块查找效率分析

$14$ $\frac{1}{14}$

7 $2$ 10 $3$ $13$ $3$ 次

30 $4$ 27 $2$ 次，因为我们要找的是第一个比查找元素27大的索引元素，虽然索引表第一个被查元素30>27，但有可能索引表之前的元素仍有比27大的元素，这样30就不是第一个比查找元素大的元素了。正确查找步骤是：

low $10$ ，high指向元素50，mid指向30，由于30>27，high=mid-1指向20
重新计算mid=(low+high)/2=0，指向元素10，而10<27，故low=mid+1指向20
mid=(low+high)/2=1指向20，此时20<27，故low=mid+1指向30，由于low>high，所以二分查找结束，查找区间为low所在的数组区间。low指向30，且区间为[6,8]
根据区间[6,8]查找数组对应下标区间，发下第一个元素即27查找成功。

27 $4$ 次。

而计算查找成功ASL值，我们需要把所有元素查找次数计算出来，并相加，再除元素总个数。对于顺序表分块查找相对来说可以计算，但对于二分查找显然不可能计算这么多元素的查找次数。所以考试只考顺序查找次数进行ASL计算。

而计算查找失败的ASL值，由于分块查询具有块内无序的特点，所以查找失败情况更加复杂。故不做讨论。

以上是分块不均匀情况，考试常考分块均匀情况下计算分块查找效率：

$n$ $b$ $s$ $L_I$ $L_S$ , 则分块查找的平均查找长度为

A S L = L_{I} + L_{S}

$b$ 个分块，则索引查找平均查找长度为：
$L_{I} = \frac{(1 + 2 + \dots + b)}{b} = \frac{b + 1}{2}$
$s$ 个元素，而查找块内元素的平均查找长度为：
$L_{S} = \frac{(1 + 2 + \dots + s)}{s} = \frac{s + 1}{2}$
$ASL=L_I+L_S$ ，即
$A S L = \frac{b + 1}{2} + \frac{s + 1}{2} = \frac{s^{2} + 2 s + n}{2 s}$
$n$ $b$ $s$ $n=sb$ 。
那么此时在什么情况下可以使ASL的平均长度最少：
$\begin{aligned} A S L = \frac{s^{2} + 2 s + n}{2 s} = \frac{1}{2} s + 1 + \frac{n}{2 s} \\ A S L^{'} = \frac{1}{2} - \frac{n}{2 s^{2}} \\ 当 \frac{1}{2} - \frac{n}{2 s^{2}} = 0, 得 s = \sqrt{n} \\ 故当 s = \sqrt{n} 时, 得极小值点, 极小值为 : \\ A S L |_{s = \sqrt{n}} = (\frac{1}{2} s + 1 + \frac{n}{2 s}) |_{s = \sqrt{n}} = \sqrt{n} + 1 \end{aligned}$
$n$ $\sqrt{n}$ $\sqrt{n}$ $\sqrt{n}+1$ 。
$n=10000$ $n$ $\sqrt{n}$ $100$ $100$ $\sqrt{n}+1=101$ 。
$L_I=\lceil\log_2(b+1)\rceil$ $L_S=\frac{(1+2+\cdots+s)}{s}=\frac{s+1}{2}$
则
$A S L = ⌈ \log_{2} (b + 1) ⌉ + \frac{s + 1}{2}$

5. 二叉排序树

二叉排序树，又称叉查找树(BST Binary Search Tree)一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

左子树上所有结点的关键字均小于根结点的关键字
右子树上所有结点的关键字均大于根结点的关键字
左子树和右子树又各是一棵二叉排序树

$<$ $<$ 右子树结点值。根据这个特性进行中序遍历，可以得到一个递增的有序序列。如下：

5.1 二叉排序树查找

若树非空，目标值与根结点的值比较：

若相等，则查找成功

若小于根结点，则在左子树上查找，否则在右子树上查找。

$NULL$

$30$ 得结点：

查找步骤：

根结点19<30，所以结点可能在根结点右侧。
右侧结点50>30，所以结点在该结点左侧。

查找实现代码如下：


xxxxxxxxxx
14
1
//二叉排序树结点
2
typedef struct BSTNode{
3
    int key;
4
    struct BSTNode *lchild, *rchild;
5
}BSTNode,*BSTree;
6

7
//在二叉排序树中查找值为key的结点
8
BSTNode *BST_Search(BSTree T,int key){
9
    while(T!=NULL&&key!=T->key){        //若树空或等于根结点值，则结束循环
10
        if(key<T->key) T=T->lchild;     //小于，则在左子树上查找
11
        else T=T->rchild;               //大于，则在右子树上查找
12
    }
13
    return T;
14
}

递归实现方法：


xxxxxxxxxx
11
1
//在二叉排序树中查找值为key 的结点(递归实现)
2
BSTNode *BSTSearch(BSTree T,int key){
3
    if (T==NULL)
4
        return NULL;            //查找失败
5
    if (key==T->key)
6
        return T;               //查找成功
7
    else if (key < T->key)
8
        return BSTSearch(T->lchild,key);//在左子树中找
9
    else
10
        return BSTSearch(T->rchild,key);//在右子树中找
11
}

$O(1)$ $O(h)$

5.2 二叉排序树的插入

$k$ $k$ 大于根结点值，则插入到右子树。

代码实现如下：


xxxxxxxxxx
16
1
//在二叉排序树插入关键字为k的新结点(递归实现)
2
int BST_Insert(BSTree &T,int k){
3
    if(T==NULL){            //原树为空,新插入的结点为根结点
4
        T=(BSTree)malloc(sizeof(BSTNode));
5
        T->key=k;
6
        T->lchild=NULL;
7
        T->rchild=NULL;
8
        return 1;           //返回1, 插入成功
9
    }
10
    else if(k==T->key)      //树中存在相同关键字的结点，插入失败
11
        return 0;
12
    else if(k<T->key)       //插入到T的左子树
13
        return BST_Insert(T->lchild,k);
14
    else                    //插入到T的右子树
15
        return BST_Insert(T->rchild,k);
16
}

同样构造二叉排序树得的过程就是不断插入新结点的过程。构造代码如下：


xxxxxxxxxx
9
1
//按照str[] 中的关键字序列建立二叉排序树
2
void Creat_BST(BSTree &T,int str[],int n){
3
    T=NULL;//初始时T为空树
4
    int i=0;
5
    while(i<n){//依次将每个关键字插入到二叉排序树中
6
        BST_Insert(T,str[i]);
7
        i++;
8
    }
9
}

$str=\{50, 66, 60, 26, 21, 30, 70, 68\}$ 建立BST

结果如下：

$str=\{50, 26, 21, 30, 66, 60, 70,68\}$ 建立BST

结果同上：

$str=\{26, 21, 30, 50, 60, 66, 68, 70\}$ 建立BST

结果如下：

由此可知不同的关键字序列可能得到同款二叉排序树。也可能得到不同款二叉排序树。

5.3 二叉排序树的删除

分三种情况：

$z$ 是叶结点，则直接删除，不会破坏二叉排序树的性质。
$z$ $z$ $z$ $z$ 的位置。
$z$ 后的结点：
$z$ $z$ $z$ ，然后从二叉排序树中删去这个直接后继(或直接前驱)，这样就转换成了第一或第二种情况。
$z$ 的右子树中最左下的结点，该结点一定没有左子树)。
$p$ $z$ $p$ $z$ $z$ $z$ $z$ 的位置。
$z$ $z$ 结点左子树中最右下的结点(该结点一定没有右子树)。

5.4 二叉排序树查找效率分析

查找长度：在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度。

$ASL_{成功}=(1*1 + 2*2 + 3*4 + 4*1)/8= 2.625$

$ASL_{成功}=(1*1+ 2*2 + 3*1 + 4*1 + 5*1 + 6*1+ 7*1)/8= 3.75$

下面看查找失败平均查找长度：

$7$ $2$ $ASL_{失败}=(3*7 + 4*2)/9=3.22$

$ASL= (2*3 +3+4+5+6+7*2)/9 = 4.22$

虽然上面两个树结点都一样，但查找长度不同，所以二叉排序树查找效率很大程度上由这棵树的高度决定。

$n$ $\lceil\log_2n\rceil+ 1$ $O(\log_2n)$

$h=结点数n$ $O(n)$

所以在构建二叉排序树时，尽量保证树上任一结点的左子树和右子树的深度之差不超过1，即建立平衡二叉树。

6. 平衡二叉树

$1$ 。

$=$ $-$ 右子树高

$2$ $3$ $=2-3=-1$ $-1$ 就是这棵树根结点的平衡因子。

$-1$ $0$ $1$ $1$ 就不是平衡二叉树。

二叉树平衡树的结构如下：


xxxxxxxxxx
6
1
//平衡二叉树结点
2
typedef struct AVLNode{
3
    int key;//数据域
4
    int balance;//平衡因子
5
    struct AVLNode *lchild,*rchild;
6
}AVLNode,*AVLTree;

上图平衡二叉树在按照二叉排序树方法插入新结点后，会变得不平衡

让这个平衡二叉树恢复平衡的办法是从插入点往回找到第一个不平衡结点，调整以该结点为根的子树。则其他祖先节点都会恢复平衡。

6.1 调整最小不平衡子树

$A$ ，分四种情况：

情况	具体原因
LL	$A$ 的左孩子的左子树中插入导致不平衡
RR	$A$ 的右孩子的右子树中插入导致不平衡
LR	$A$ 的左孩子的右子树插入导致不平衡
RL	$A$ 的右孩子的左子树中插入导致不平衡

调整最小不平衡子树(LL)

左子树的左孩子结点(LL) $A$ 为根结点的树不平衡情况。

$H$ 。目标是要恢复平衡并保持二叉排序树特性。

$<$ $<$ $BL<B<BR<A<AR$ $A$ $(L)$ $(L)$ $A$ $1$ $2$ $A$ 为根的子树失去平衡，需要一次向右的旋转操作。

$A$ $B$ $A$ 成为根结点。
$A$ $B$ 的右子树的根结点
$B$ $A$ 结点的左子树。

代码实现核心：


xxxxxxxxxx
3
1
A->lchild=B->rchild;
2
B->rchild=A;
3
gA->lchild||gA->rchild=B;

gA是A结点的父结点，A代表A结点，B代表B结点。

调整最小不平衡子树(RR)

右子树的右孩子结点(RR) $A$ 为根结点的树不平衡情况。

$<$ $<$ $AL<A<BL<B<BR$ $A$ $(R)$ $(R)$ $A$ $-1$ $-2$ $A$ 为根的子树失去平衡，需要一次向左的旋转操作。

$A$ $B$ $A$ 成为根结点
$A$ $B$ 的左子树的根结点
$B$ $A$ 结点的右子树

代码实现核心：


xxxxxxxxxx
3
1
A->rchild = B->lchild;
2
B->lchild=A;
3
gA->lchild||gA->rchild=B;

gA是A结点的父结点，A代表A结点，B代表B结点。

调整最小不平衡子树(LR)

左子树的右孩子结点(LR) $A$ 为根结点的树不平衡情况。

BR $BR$ 结点是一个以C为根的树，其左子树是CL高度为H-1，右子树是CR高度为H-1。

这里将新插入的结点放在CR结点，也可以放在CL结点。那么恢复平衡的具体做法是先左后右双旋转：

$A$ $(L)$ $(R)$ $A$ $1$ $2$ $A$ 为根的子树失去平衡，需要进行两次旋转操作先左旋转后右旋转：

$A$ $B$ $C$ $B$ 结点的位置
$C$ $A$ 结点的位置

$BL<B<CL<C< CR<A<AR$

调整最小不平衡子树(RL)

右子树的左孩子结点(RL) $A$ 为根结点的树不平衡情况。

BR $BL$ 结点是一个以C为根的树，其左子树是CL高度为H-1，右子树是CR高度为H-1。将新插入的结点放在CL结点，也可以放在CR结点。

先右后左双旋转 $A$ $(R)$ $(L)$ $A$ $-1$ $-2$ $A$ 为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。

$A$ $B$ $C$ $B$ 结点的位置
$C$ $A$ 结点的位置

$AL<A<CL<C<CR<B<BR$

平衡二叉树查找效率分析

$h$ $h$ $O(h)$ 。所以查找效率分析实际就是分析一颗平衡二叉树高度有多高。

$1$ $n_h$ $h$ $h$ 的平衡二叉树最少结点数为：

n_{h} = n_{h - 1} + n_{h - 2} + 1

$+$ $n_{h-1}$ $+$ $n_{h-2}$ $h$ 平衡二叉树最少结点数：

\begin{matrix} n_{0} = 0, n_{1} = 1, n_{2} = 2 \\ n_{3} = n_{2} + n_{1} + 1 = 4 \\ n_{4} = n_{3} + n_{2} + 1 = 7 \\ n_{5} = n_{4} + n_{3} + 1 = 12 \end{matrix}

$n=9$ $h_{\max}=4$ $4$ 次。

$n$ $O(\log_2n)$ ，平衡二叉树的 $O(\log_2n)$ 。

总结

只有左孩子插入结点才进行右旋操作，只有右孩子插入结点才进行右旋操作。

看个例子，有以下二叉排序树，由于再添加结点67变为非平衡二叉树

恢复平衡的办法是从插入点往回找到第一个不平衡结点，即70。调整以该结点为根的子树：

首先观察这是一个LL类型的最小不平衡子树
采用右旋操作，将68结点成为根结点，70结点成为68结点的右子树。

结果如下：

$+1$ ，经过调整后高度恢复，则祖先平衡因子也会恢复正常。

$2$ ：有以下二叉排序树

插入结点57

此时平衡二叉树变为非平衡二叉树，其第一个不平衡结点为66。不平衡原因是在其左孩子的右子树中插入新结点，所以是LR类型。

解决方法是：让66结点的左孩子的右孩子60结点先左旋，再右旋。熟练方法是左旋右旋之后60会成为根结点，而50和66为根结点的左孩子和右孩子。之后让60原本的左子树(55和57)与右子树(63)，按照二叉排序树规则插入即可。

6.2 平衡二叉树的删除

$<$ $<$ 右)。若删除结点后导致结点不平衡，则需要调整平衡。

平衡二叉树删除操作具体步骤：

删除结点(方法同二叉排序树)
- 若删除的结点是叶子，直接删。
- 若删除的结点只有一个子树，用子树顶替删除位置
- 若删除的结点有两棵子树，用前驱(或后继)结点顶替，并转换为对前驱(或后继)结点的删除。
若删除后出现不平衡现象，则从被删除结点开始往上找到最小不平衡子树，找不到就完结撒花
如果找到最小不平衡子树，高度最高的儿子结点和孙子结点
$LL/RR/LR/RL$ )
- $LL$ ：儿子结点右单旋
- $RR$ ：儿子结点左单旋
- $LR$ ：孙子结点先左旋，再右旋
- $RL$ ：孙子结点先右旋，再左旋
如果调整完后，不平衡特性向上传导，则继续②
对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡(不平衡向上传递)

删除下面平衡二叉树的32结点：

因为32结点是叶子结点，所以直接删除，删除后出现二叉树出现不平衡现象。找最小不平衡子树为44结点
找最小不平衡子树下面最高儿子结点78和孙子结点50
50 $RL$ 情况，所以要先右旋，再左旋。
先右旋：
再左旋：
此时最小不平衡子树恢复平衡

整个平衡二叉树如下：

通过上图可以观察出，由于右侧树做了恢复调整，由于树高变矮，所以不平衡性向上传到。处理方法是从第二步开始：

从刚刚调整的树的根50出发，往上找最小不平衡子树，是33。对这棵最小不平衡树再做调整
找最小不平衡子树下面最高儿子结点10和孙子结点20
接着根据孙子结点2020 $LR$ 情况，所以孙子结点要先左旋，再右旋。
先左旋：
再右旋：

整棵树恢复平衡。

$O(\log_2n)$

7. 红黑树

$O(\log_2n)$ 。

由于平衡二叉树的插入和删除两个操作很容易破坏平衡性，需要频繁调整树的形态。而红黑树在插入或删除时不会破坏红黑特性，无需频繁调整树的形态，即便需要调整一般都在常数级时间内完成。

使用场景：

$AVL$ $/$ 删除的场景。
红黑树：适用于频繁插入、删除的场景，实用性更强。实用场景中一般都用红黑树。

$\le$ $\le$ 右子树结点值。

$/$ 特点：

每个结点或是红色，或是黑色
根节点是黑色
叶结点(外部结点、NULL结点、失败结点)均是黑色的
不存在两个相邻的红结点(即红结点的父节点和孩子结点均是黑色)
对每个结点，从该节点到任一叶子结点的简单路径上，所含黑结点的数目相同

红黑树结构定义：


xxxxxxxxxx
7
1
struct RBnode {     //红黑树的结点定义
2
    int key;        //关键字的值
3
    RBnode* parent; //父节点指针
4
    RBnode* lChild; //左孩子指针
5
    RBnode* rChild; //右孩子指针
6
    int color;      //结点颜色， 如:可用0/1表示黑/红， 也可使用枚举型enum表示颜色
7
};

黑结点的高度：从某一结点出发（不包含该结点）到达任意空叶结点的路径上黑结点总数。由于红黑树特点我们只用看一条路径就可以知道该结点的黑结点高度。

$h$ $2h-1$ 个.

根据红黑树特点可以得到以下性质：

4,5 $2$ $2$ 倍。
$n$ $h\le2\log_2(n+1)$
$=h$ $\ge\frac{h}{2}$ $n\ge 2^{\frac{h}{2}}-1$ $h\le2\log_2(n+1)$

红黑树的查找与BST、AVL 相同，从根出发，左小右大，若查找到一个空叶节点，则查找失败。

7.1 红黑树的插入

红黑树的插入和平衡二叉树有很多相似地方。

插入步骤：

先查找，确定插入位置（原理同二叉排序树），插入新结点
新结点是根，则染为黑色。如果新结点非根，则染为红色。
若插入新结点后树依然满足红黑树的定义，则插入结束
若插入新结点不满足红黑树定义，则需要进行调整，使其能重新满足红黑树定义。

如何调整：

找新插入结点的父结点的兄弟结点。
$+$ 染色。具体做法仍要判断新插入的结点从爷结点开始的类型：
$LL$ 型：父结点右单旋和爷结点交换，之后对两个结点颜色取反。
$RR$ 型：父结点左单旋和爷结点交换，之后对两个结点颜色取反。
$LR$ 型：新结点先左旋再右旋，儿子结点和爷结点交换，之后对两个结点颜色取反。
$RL$ 型：新结点先右旋再左旋，儿子结点和爷结点交换，之后对两个结点颜色取反。
$+$ 爷结点变为新结点，再判断新结点能不能满足红黑树定义。如果不能再接着重复上面调整方法。

注意：新结点在插入的时候如果需要调整一般都是违背了"不存在两个相邻的红结点"这一原则。

例子：从一棵空的红黑树开始，插入：20，10，5，30，40，57，3，2，4，35，25，18，22，23，24，19，18

$20$ 结点插入：
上面蓝色框是新插入结点，下面两个叶子结点是NULL结点。
为了保证某节点到叶子结点任意一条简单路径上黑色结点数量都相同，这一特性我们要将插入的非根结点都设置为红色。
$10$ 结点：
$5$ 结点：
此时发现破环了，"不存在两个相邻的红结点"这一原则，需要进行调整，使其能重新满足红黑树定义。
$5$ $NULL$ $4$ $20$ $LL$ 型，调整方法是：父结点右单旋和爷结点交换，之后对两个结点颜色取反。
先右单旋：
再对两个结点颜色取反：
$30$
新结点插入后破环了红黑树定义，违反了"不存在两个相邻的红结点"这一原则。
$30$ $5$ $+$ 爷结点变为新结点，再判断新结点能不能满足红黑树定义。如果不能再接着重复上面调整方法。
颜色取反：
爷结点变为新结点，再判断红黑树是否满足定义。
发现违背"根节点是黑色"这一原则。将新结点改为黑色即可。
$40$ 结点
同样是违背了"不存在两个相邻的红结点"这一原则。
$40$ $NULL$ $40$ $20$ $RR$ 型，调整方法是：父结点左单旋和爷结点交换，之后对两个结点颜色取反。
左单旋：
颜色取反：
$57$ ，同样违背了"不存在两个相邻的红结点"这一原则。
$57$ $20$ $+$ 爷结点变为新结点，再判断新结点能不能满足红黑树定义。如果不能再接着重复上面调整方法。
颜色取反：
$30$ 是新插入的结点，再次判断红黑树发现满足定义。
$3$ 结点，满足红黑树定义，不需要调整。
$2$ ，违背了"不存在两个相邻的红结点"这一原则。
$2$ $NULL$ $2$ $5$ $LL$ 型，调整方法是：父结点右单旋和爷结点交换，之后对两个结点颜色取反。
右单旋：
颜色取反：
$4$ ，同样违背了"不存在两个相邻的红结点"这一原则。
$4$ $2$ $+$ 爷结点变为新结点，再判断新结点能不能满足红黑树定义。如果不能再接着重复上面调整方法。
颜色取反：
$3$ 是新插入的结点，再次判断红黑树发现满足定义。
$35$ $25$ $18$ 都没有违背红黑树定义。
$22$ ，违背了"不存在两个相邻的红结点"这一原则。
$22$ $18$ $+$ 爷结点变为新结点，再判断新结点能不能满足红黑树定义。如果不能再接着重复上面调整方法。
颜色取反：
$20$ $3$ $+$ 爷结点变为新结点，再判断新结点能不能满足红黑树定义。如果不能再接着重复上面调整方法。
颜色取反：
$10$ $10$ 颜色取反即可
$23$ ，发现违背了"不存在两个相邻的红结点"这一原则。
$23$ $NULL$ $23$ $25$ $LR$ 型，调整方法是：新结点先左旋再右旋，儿子结点和爷结点交换，之后对两个结点颜色取反。
先左旋：
再右旋：
颜色取反：
$24$ ，违背了"不存在两个相邻的红结点"这一原则。
$24$ $22$ $+$ 爷结点变为新结点，再判断新结点能不能满足红黑树定义。如果不能再接着重复上面调整方法。
颜色取反：
$23$ $40$ $23$ $25$ $LR$ 型，调整方法是：新结点先左旋再右旋，儿子结点和爷结点交换，之后对两个结点颜色取反。
先左旋：
再右旋：
颜色取反：
$19$ 结点
$18$ $18$ 结点左子树或者右子树
$18$ $NULL$ $18$ $18$ $RL$ 型，调整方法是：新结点先右旋再左旋，儿子结点和爷结点交换，之后对两个结点颜色取反。
先右旋：
再左旋：
颜色取反：

将所有元素插入红黑树完毕。

7.3 红黑树的删除

重要考点：

$=O(\log_2n)$

②在红黑树中删除结点的处理方式和"二叉排序树的删除"一样

③按②删除结点后，可能破坏"红黑树特性"，此时需要调整结点颜色、位置，使其再次满足"红黑树特性"。

8. B树

由前面的二叉排序树可以知道，二叉树中每个结点都可以将查找范围缩小到两个区间内。

而B树就是拥有更多分支结点的树。具体定义如下：

$B$ 多路平衡查找树 $B$ $B$ $m$ $m$ $B$ $m$ 叉树：

$m$ $\lceil m/2\rceil$ $\lceil m/2\rceil-1$ 个关键字 $m-1$ 个关键字。
这样构造出来的多叉树就是B树。这样规定是因为若每个结点内关键字太少，导致树变高，要查更多层结点，导致效率低。
$m$ 叉查找树中，规定对于任何一个结点，其所有子树的高度都要相同。
若根结点不是终端结点，则至少有两棵子树。
$m$ $m-1$ 个关键字。
所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。

$5$ $\lceil 5/2\rceil=3$ $\lceil 5/2\rceil-1=2$ 个关键字。

$5$ 叉查找树。其代码定义结构如下：


xxxxxxxxxx
6
1
//5叉排序树的结点定义
2
struct Node {
3
    ElemType keys[4];//最多4个关键字
4
    struct Node * child[5]; //最多5个孩子
5
    int num;//结点中有几个关键字
6
};

$9$ 元素

$22>9$ ，所以只可能在根结点左子树。
$5$ $11$ $11>9>5$ $5$ $11$ 中间指针指向子树。
$6,8,9$ 遍历关键字成功找到元素。

注：如果一个结点包含关键字有多个，可以用折半查找。

$41$ 元素：

$22<41$ ，所以只可能再根结点右子树
$36,45$ $36<41<45$ $36$ $45$ 中间指针指向子树。
$40,42$ $40<41<42$ ，所以可能在两个关键字中间指针指向子树
$NULL$ ，是失败结点，返回查找失败，未找到。

$m$ $B$ 树的核心特性：

$\in[2, m]$ $\in[1, m-1]$ $\in\Big[\lceil m/2\rceil, m\Big]$ $\in\Big[\lceil m/2\rceil-1, m-1\Big]$
对任一结点，其所有子树高度都相同
$0<$ $1<$ $1<$ $2<$ $2<\dots$ $<$ $<$ 右)。即每个结点指针和关键字之间存储结构。

B树的高度（这里计算B树的高度不计算叶子结点(失败结点)）：

$n$ $m$ $B$ $m-1$ $m$ 个分叉，则有

\begin{aligned} n \leq (m - 1) (1 + m + m^{2} + m^{3} + \dots + m^{h - 1}) = m^{h} - 1 \\ ∴ h \geq \log_{m} (n + 1) \end{aligned}

$n$ $m$ $B$ $2$ $\lceil \frac{m}{2}\rceil$ $1$ $2$ $2\lceil\frac{m}{2}\rceil\cdots$ $h$ $2(\lceil\frac{m}{2}\rceil)^{h-2}$ $h+1$ $2(\lceil\frac{m}{2}\rceil)^{h-1}$ $n$ $n+1$ $n$ $n+1$ $n+1\ge2(\lceil\frac{2}{m}\rceil)^{h-1}$ $h\le\log_{\lceil\frac{2}{m}\rceil}\frac{n+1}{2}+1$

还可以从另一个角度分析：

$n$ $m$ $B$ $k=\lceil \frac{m}{2}\rceil$

$h$ $m$ $B$ $1+2(k-1)(k^0+k^1+k^2+\cdots+k^{h-2}) = 1+2(k^{h-1}-1)$

$h$ $n\ge1+2(k^{h-1}-1)$ 化简可得：

h \leq \log_{k} \frac{n + 1}{2} + 1 = \log_{⌈ \frac{m}{2} ⌉} \frac{n + 1}{2} + 1

总结： $n$ $m$ $B$ 树，最大高度和最小高度：

⌈ \log_{m} (n + 1) ⌉ \leq h \leq ⌈ \log_{⌈ \frac{m}{2} ⌉} \frac{n + 1}{2} ⌉ + 1

8.1 B树的插入

插入核心要求：

$\lceil\frac{m}{2}\rceil-1\le n\le m-1$ $2\le n\le4$
每个结点符合有序的特性

插入步骤：

$(\lceil\frac{m}{2}\rceil)$ $(\lceil\frac{m}{2}\rceil)$ $1$ 。

$5$ $B$ 树的插入：

$25,38,49,60$ 三个关键字，插入后如下：

$80$ $5$ $4$ $80$ 关键字导致原结点关键字数超过上限， $(\lceil\frac{m}{2}\rceil)$ $(\lceil\frac{m}{2}\rceil)$ 的结点插入原结点的父结点。

$49$ $49$ $25,38$ $60,80$ 为其右子树

接着新元素一定是插入到最底层"终端节点"，用"查找"来确定插入位置。

$90$ $90>49$ $49$ $60<80<90$ 插入最右边

$99$ $88$ 插入操作相同

$88$ $5$ $88$ $60,80$ $90,99$ 为其右子树

$83,70$ ，这两个关键字不影响B树平衡所以直接插入

$70$

$70$ $5$ $80$ $49,88$ $60,70$ $83,87$ 为其右子树。

$92,93,94$ 三个关键字

$94$ $5$ $93$ $90,92$ $94,99$ 为其右子树。

$73,74,75$

$75$ $5$ $73$ $49,80$ $60,70$ $74,75$ 为其右子树。
$75$ $5$ $80$ $49,73$ $88,93$ 为其右子树。

8.2 B树的删除

删除关键字操作分情况：

可以直接删除 $5$ $60$ $2\le n\le4$ 的特性。所以直接删除。
如果删除的关键字位于根结点，可以找该关键字的直接前驱或直接后继，顶替这个位置。直接前驱：当前关键字左侧指针所指子树中"最右下"的元素。直接后继：当前关键字右侧指针所指子树中"最左下"的元素。
$80$ $80$ $77$ $82$ $80$ 的位置即可。
所以，对非终端结点关键字的删除，必然可以转化为对终端结点的删除操作。
如果删除的关键字位于终端结点，但删除完后破坏B树关键字个数特性，则：
如果兄弟结点够借：若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右(或左) 兄弟结点的关键字个数还很宽裕，则需要调整该结点、右(或左)兄弟结点及其双亲结点(父子换位法)。再具体一点做法是(这里是中序遍历)：
1. 当左兄弟很宽裕时，用当前结点的前驱、前驱的前驱来填补空缺
2. 当右兄弟很宽裕时，用当前结点的后继、后继的后继来填补空缺
$38$ $70$ $49$ $49$ $38$ 位置。
$90$ $94,99$ $90$ $88$ $90$ $87$ $88$ 的位置。
则将删除关键字的结点与左（或右）兄弟结点及双亲结点中的关键字进行合并 $1$ $\lceil\frac{m}{2}\rceil-1$ ，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合B树的要求为止。
$49$ $70$ $49$ $71,72$ $70$ 后面位置。
$73$ $82$ $73$ $87,93$ $82$ 后面
由于父结点内没有关键字，可以删除该结点

$B^+$ 树

$b^+$ 树和分块查找很相似，每个结点内部分块，都保存对应指针指向结点的最大值。

$m$ $B^+$ 需要满足以下条件：

非叶根结点至少有两棵子树至少 $\lceil\frac{m}{2}\rceil$ $B$ 树一样可以理解为：要追求"绝对平衡"，即所有子树高度要相同。
$m$ 棵子树(孩子结点)。
所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。
结点的子树个数与关键字个数相等 $B$ $B^+$ $B$ 树有三个分支。
所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。

$4$ $B^+$ 树：

$B^+$ 树的查找

$4$ $B^+$ 树：

$9$ ：

$9<15$ $15$ $3,9,15$ 内出现。
$9$ $B^+$ $9$ $6,8,9$
$9$ $B$ 树，到这里就查找成功，不用再找下一层的叶子结点。
$B$ 树的记录：

$B^+$ 树中，无论查找成功与否，最终一定都要走到最下面一层结点。

$P$ $P$ 结点往后查找每个结点中的关键字，直到找到对应的关键字即可。

$B^+$ $B$ 树区别

$m$ $B$ 树	$m$ $B^+$ 树
$n$ $n+1$ 棵子树	$n$ $n$ 棵子树
$\lceil\frac{m}{2}\rceil-1$ $m-1$ ，但根结点个数可以只有一个	$\lceil\frac{m}{2}\rceil$ $m$ ，但根结点个数可以只有一个
在B树中，各结点中包含的关键字是不重复的	叶结点包含全部关键字，非叶结点中出现过的关键字也会出现在叶结点中
B树的结点中都包含了关键字对应的记录的存储地址	叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

$B^+$ $B$ $B^+$ $B^+$ 树的阶更大，树高更矮，读磁盘次数更少，查找更快。

10. 哈希表

散列表(Hash Table)，又称哈希表。是一种数据结构，特点是：数据元素的关键字与其存储地址直接相关。

$\{19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79\}$ $H(key)=key\%13$ $0\sim 12$ 范围内。

$13$ 取余，所得的值就是数组下标索引值，将关键字放入索引对应的数组位置即可。但取余操作会有以下两种情况：

若不同的关键字通过散列函数映射到同一个值，则称它们为"同义词"
通过散列函数确定的位置已经存放了其他元素，则称这种情况为"冲突"

解决哈希冲突，是哈希表的关键。

10.1 拉链法解决哈希冲突

用拉链法(又称链接法、链地址法)处理冲突：把所有"同义词"存储在一个链表中。这也是实际开发中常用的方法。

$H(key)=key\%13$ $\{19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79\}$ $14$ $1$ $13$ $1$ ，出现哈希冲突，用拉链法就是将关键字通过链表的形式放在同一个索引位置。

存储所有关键字后哈希表结构如下：

拉链法的查找方法是，首先基于散列函数计算出被查找关键字的哈希值。根据哈希值找到对应数组索引位置，如果存放的是链表则遍历看是否有被查找关键字。

$27$ $27\%13=1$ $1$ 内存放的链表

$27$ $3$ $NULL$ $0$ 。

$ASL=\frac{1\times6+2\times4+3\times1+4\times}{12}=1.75$ $1\times6$ $6$ $2\times4$ $4$ 个元素。

$ASL=\frac{0+4+0+2+0+0+2+1+0+0+2+1+0}{13}=0.92$ $\frac{1}{13}$ 。

$ASL_{失败}$ 就是 $\alpha=$ $/$ 散列表长度。装填因子值越大代表散列表装的关键字越多。

通过上面对查找长度和平均查找长度的计算，可以知道哈希冲突会导致查询效率变低。且查找长度越大，代表冲突越大，查找效率越低。

$O(1)$ $1$ 。

如果拉链法中链表元素采用顺序存储方式，可以提高查找效率。

10.2 常见的哈希函数

哈希函数的设计可以直接决定一个哈希表的查找效率，所以哈希函数设计很重要，下面介绍几种常见的哈希函数。

除留余数法

$H(key)=key\%p$ $m$ $m$ $m$ $p$ 。

$13$ $H(key)=key\%13$

$15$ $H(key)=key\%13$ $15$ $15$ $13$ 。

这样设计的原因是：质数分布更均匀，冲突更少。参见《数论》。大致原因是和数的公因子多，所以冲突概率更高。

直接定址法

$H(key)=key$ $H(key)=a*key+b$

$a$ $b$ 是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间浪费。

$(1120112176\sim 1120112205)$ $176$ $H(key)=key-1120112176$ 。每个学号都和第一个人的学号相减的值即为数组索引位置。存储如下：

数字分析法

选取数码分布较为均匀的若干位作为散列地址。

设关键字是r进制数(如十进制数)，而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等，而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合,若更换了关键字，则需要重新构造新的散列函数。

例如：以"手机号码"作为关键字设计散列函数

平方取中法

取关键字的平方值的中间几位作为散列地址。

具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

例如：要存储整个学校的学生信息，以“身份证号”作为关键字设计散列函数

尽管这里表的长度十万，但还是有冲突的可能性。要完全解决哈希冲突，方法是设计的表要足够长，但这样空间复杂度也会很高，所以散列查找是一个典型的"空间换时间的"算法。

10.3 开放定址法解决哈希冲突

所谓开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为：

H_{i} = (H (k e y) + d_{i}) % m

$i=0,1,2\cdots,k(k\le m-1)$ $m$ $d_i$ $i$ $i$ 次发生冲突。

$d_i$ 计算有三种：

线性探测法
平方探测法
伪随机序列法

开放地址法删除关键字：删除关键字不能只是简单的删除而是标记删除

线性探测法

$d_i=0,1,2,3,\cdots,m-1$ ；即发生冲突时，每次往后探测相邻的下一个单元是否为空。

$\{19,14,23,1,68,20,84,27,55,11,10,79\}$ $H(key)=key\%13$

$H_i=(H(key)+d_i)\%16$

前三个关键字没有发生冲突直接放入
$1$ $H(1)=1\%13=1$ $d_1=1$ $H_1=(1+1)\%16=2$ $2$ 位置
$68,20$ 不会发生冲突，直接放入。
$84$ $H(84)=84\%13=6$ $d_1=1$ $H_1=(6+1)\%16=7$ $d_2=2$ $H_2=(6+2)\%16=8$ 。没有冲突放入
$[0,12]$ $[0,15]$

$27$ 关键字：

$27\%13=1$ $1$ $14$ $H_1=(1+1)\%16=2$ $2$ $1$ $H_2=(1+2)\%16=3$ $3$ $68$ $H_3=(1+3)\%16=4$ $4$ $27$ $27$ $4$ 。

$H_i$ 结果索引值指向位置关键字是空的，此时查找失败，但也要算作一次比较次数。所以在查找失败情况下，越早遇到空位置就可以越早确定查找失败，查找效率会提高。

删除关键字：删除关键字不能只是简单的删除还要标记删除

$1$ $27$

$H(27)=27\%13=1$ $1$ $H_1=(1+1)\%13=2$ $2$ 索引值指向位置关键字是空的，此时查找失败 $27$ 这个关键字真是存在，故采用"开放定址法"时，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径，可以做一个"删除标记"，进行逻辑删除。

$8$ $79$ ：

$8$ $9$ $79$ 这个关键字。所以这个哈希表看起来很满，但实际上很空。很多关键字在逻辑上被删除了。

查找成功平均查找长度：先算出每个关键字能被查找到的次数，再将关键字查找次数相加除关键字长度即可。

A S L_{成 功} = \frac{1 + 1 + 1 + 2 + 4 + 1 + 1 + 3 + 3 + 1 + 3 + 9}{12} = 2.5

$0$ $1$ $1$ $13$ $13$ 。故

A S L_{失 败} = \frac{1 + 13 + 12 + 11 + 10 + 9 + 8 + \dots + 2}{13} = 7

可以看出线性探测法查找效率很低，因为线性探测法很容易造成同义词、非同义词的"聚集(堆积)"现象，严重影响查找效率。出现这一现象根本原因是冲突后再探测一定是放在某个连续的位置。

平方探测法

平方探测法可以有效解决聚集的问题。

$d_i=0^2,1^2,-1^2,2^2,-2^2,\cdots,k^2,-k^2$ $k\le\frac{m}{2}$

$H(key)=key\%13$ $H_i=(H(key)+d_i)\%16$

$6$ $6$ ，产生冲突，采用平方探测法解决：

$19$ $H_1=(6+1)\%27=7$ $7$ 没有元素无冲突直接放入。
$32$ $6$ $7$ $H_2=(6-1)\%27=5$ $5$ 没有元素无冲突直接放入。
后序元素方法类似。
$45$ $H_3=(6+4)\%27=10$
$58$ $H_4=(6-4)\%27=2$
$71$ $H_5=(6+9)\%27=15$
$84$ $H_6=(6-9)\%27=-3$ $24$

$H_i$ 。

注意 $4i+3$ 表示的质数。只有满足这个条件才能探测到所有位置。

伪随机序列法

$d_i$ $d_i=0,5,24,11,\cdots$

$H-i$ $d_i$ 的值。

10.4 再哈希法

$H(key)$ 之外，多准备几个哈希函数，当哈希函数冲突时，用下一个哈希函数计算一个新地址，直到不冲突为止。

\begin{matrix} H_{i} = R H_{i} (k e y) \\ i = 1, 2, 3, \dots, k \end{matrix}

| E |

$|E|$ 表示是图的边 ↩

九. 图

1. 图的概念

2. 图的存储

2.1 邻接矩阵法

邻接矩阵存放普通图

邻接矩阵法存放带权图

邻接矩阵性能分析与性质

2.2 邻接表

2.3 邻接表与邻接矩阵对比

2.4 十字链表

2.5 邻接多重表

2.6 总结

3. 图的基本操作

4. 图的广度优先搜索

4.1 图的BFS实现

4.2 图BFS遍历非连通图

4.3 图的BFS算法复杂度分析

4.4 广度优先生成树与森林

广度优先生成树

广度优先生成森林

5. 图的深度优先搜索

5.1 图的DFS实现

5.2 图DFS遍历非连通图

5.3 图的DFS算法复杂度分析

5.4 深度优先生成树与森林

5.5 图的遍历与图的连通性

6. 图的应用

6.1 最小生成树

普利姆(Prim)算法

克鲁斯卡尔(Kruskal)算法

两个算法比较

6.2 最短路径问题

BFS算法解决最短路径

Dijkstra算法解决最短路径

Floyd算法解决最短路径

6.3 总结

7. 有向无环图(DAG图)

7.1 DAG应用——有向无环图表达式

7.2 DAG应用——拓扑排序

拓扑排序代码实现

逆拓扑排序

DFS实现逆拓扑排序

8. 关键路径

十. 查找

1. 查找算法评价指标

2. 顺序查找

2.1 代码实现

2.2 查找效率分析

2.3 顺序查找的优化(有序表)

3. 二分查找(折半查找)

3.1 查找步骤及实现

3.2 查找的效率分析

3.3 二分查找判定树构造

4. 分块查找

4.1 分块查找实现

4.2 分块查找效率分析

5. 二叉排序树

5.1 二叉排序树查找

5.2 二叉排序树的插入

5.3 二叉排序树的删除

5.4 二叉排序树查找效率分析

6. 平衡二叉树

6.1 调整最小不平衡子树

调整最小不平衡子树(LL)

调整最小不平衡子树(RR)

调整最小不平衡子树(LR)

调整最小不平衡子树(RL)

平衡二叉树查找效率分析

总结

6.2 平衡二叉树的删除

7. 红黑树

7.1 红黑树的插入

7.3 红黑树的删除

8. B树

8.1 B树的插入

8.2 B树的删除

9. B+B^+树

9.1 B+B^+树的查找

9.2 B+B^+树与BB树区别

10. 哈希表

$B^+$ 树

$B^+$ 树的查找

$B^+$ $B$ 树区别