数据结构笔记

数组、向量和链表

数组

在C和C++中都学过，因此不细写。回忆一种数组动态分配内存方法

char* a;
a = new char[5];

和

char a[5];

这两种方法区别是

向量

向量本质上与数组无异，C++标准库中新增了一些功能，如向向量后方添加一个元素

push_back();

去掉最后一个元素

pop_back();

清除、插入中间的元素

vec.erase(vec.begin()+1);
vec.insert(vec.end(), 1, 'a');

这种方法比较慢，因为时间复杂度为$O_{(n)}$

链表

C++中链表的元素访问不能通过方括号访问，需要一个迭代器iterator，具体方法如下

list<char>::iterator iter = list.begin();
cout << *iter;

同样链表中也有push_back、push_front、pop_back、pop_front等用法，功能顾名思义。

二分查找 Binary Search

主要思想是先取中间值、与目标值比较、取中间值、比较，以此类推….

跳跃链表 Skip List

跳跃链表的结构

假设一个单向链表，在每个节点上方都增加了若干层L1、L2、L3…第二层中，对于每一个节点，有二分之一概率会将第一层向上增加到第二层。第三层则是增加到第二层的节点有二分之一概率从第二层增加到第三层，以此类推，这样形成的链表即时跳跃链表 跳跃链表牺牲了空间换取时间，因此相较于普通链表可以快速到达中间节点。 推荐层数选为n因为这样查找和插入的时间复杂度都是$O_{log(n)}$?

跳跃链表的查找

跳跃链表查找数据首先从最高的层开始。首先将目标数据与sentinel节点和其在最高层指向的下一节点的数据相比较，在哪个区间便在进入下一层时取哪个数据段，以此类推。

跳跃链表的插入

从sentinel开始，将其作为基准节点，跳跃链表的插入首先找到目标节点的左右两边节点，然后像普通链表一样插入。接着从第二层开始判断是否增加到下一层，若增加，则将该层的连接处指针进行调换，直到插入的节点不增加层数

矩阵

• Dense matrix：稠密矩阵，大部分是非0元素

• Sparse matrix：稀疏矩阵，非0元素远远小于总元素数

矩阵的存储

• 按行存储：将矩阵每一行按顺序存储到一个数组中
• 按列存储：将矩阵每一列按顺序存储到一个数组中

区别：对于行存储，按行访问的速度快，按列访问速度慢（空间的局部性）

图 Graph

图是由节点、边组成的数据结构

• 有向图：存在边是单向的
• 无向图：所有边都是双向的
• 有权图：边存在权重
• 无权图：边的权重全部相等

邻接表

邻接矩阵

邻接表和邻接矩阵都是描述图的一种数据结构。当图是无向的，邻接矩阵对称，反之不对称。当图是无权的，图的所有边相等，都以1表示，反之则不相等。

路径

路径可以表示为节点的序列，从路径的起点到终点组成的序列，也可以表示为边的序列

对于无权图，路径的长度是边的序列长度；对于有权图，路径的长度要考虑权重（路径上的长度加和）

简单路径：路径不会绕圈

最短路径：输入图$G=(\nu,\epsilon)$和起点s，任务是找到从起点s出发的长度最短路径

单元最短路问题

通过下图这样一个表，可以获得以s为起点（图中为$v_3$）的最短路。因此单元最短路问题就是得到这样一个表。

无权图中的最短路

准备工作：准备一个队列（先入先出），和一个表（初始值如下）

其中，visit代表是否经过该节点，dist代表路径长度，path用来记录路径。

初始时，将起点（$v_3$）放入队列中，准备工作完成

一轮循环：开始时，先检查队列。由于$v_3$在最前列，把$v_3$取出。然后处理$v_3$指向的$v_1$和$v_6$。

处理$v_1$：由于含$v_1$的一行visit为no，即没有被处理过（若处理过则直接跳过），因此将visit标注为yes，dist标记为$v_3$到$v_1$的路径长度1，记录$v_1$的path为$v_3$。 处理$v_6$：与处理$v_1$相同。此时队列中有两个元素$v_1$和$v_6$。

二轮循环：由于队列最前端是$v_1$，$v_1$通向$v_2$和$v_4$，由于没有被处理过，因此处理$v_2$和$v_4$。$v_2$的dist为2，path为$v_1$。然后处理$v_6$，由于$v_6$没有指向的节点，因此仅从队列中取出，循环结束

三轮循环：从队列顶端取出$v_2$，其指向$v_4$和$v_5$，由于$v_4$被访问过，因此跳过，然后处理$v_5$。

后面的循环以此类推

算法的时间复杂度为$O_{(\nu+\epsilon)}$

无权图中的最短路（Dijkstra算法）

该算法需要一个优先队列，即哪个节点距离初始节点（$v_3$）最近，哪个节点先出队列。 准备一个优先队列和一个表如下图：

由于距离初始都是正无穷，因此对于途径某一个节点，距离小于当前距离即需要进行更新（大于则直接忽略），并且更新后的节点需要根据优先级插入队列（距离越小优先级越高）。

一轮循环：取出队列中的$v_3$，找到$v_3$指向的两个节点$v_1$和$v_6$，更新表中的距离和路径。对于$v_1$，dist=4，path=$v_3$。 然后更新$v_6$的路径，将dist=5，path=$v_3$，将$v_1$和，并将$v_1$和$v_6$插入队列

二轮循环：取出队列中的$v_1$，找到其指向的节点$v_2$和$v_4$。更新表中的$v_2$和$v_4$。更新了则插入队列，未更新就跳过。

之后的循环以此类推

算法的时间复杂度为$O_{((| \nu|+|\epsilon|)\cdot log|\nu|)}$

最小生成树

树是特殊的图。一个图满足三个条件即是树：

• 连通的
• 无环的
• 无向的

有n个节点的树一定有n-1个节点

生成树（Spanning Trees）指的是保留全部的节点和一部分边的子图，并满足树的要求。

最小生成树指的是生成树中所有边权重和最小的。

Prim算法

算法输入：一张无向有权图。

一轮循环：首先随机找一个节点，假定为$v_1$，将其加入到集合U中。

二轮循环：找到$v_1$连接的点中边的权重最小的节点$v_4$，将其加入到U中

三轮循环：找到U中包含节点所连接的点中边的权重最小的节点$v_2$（$v_3$与之相等，取哪个都可以），将其加入到U中

四轮循环：找到U中包含节点所连接的点中边的权重最小的节点$v_3$，将其加入到U中

以此类推，由于在加入U的过程中始终保持连通性和无环性两个性质，因此当所有节点都被加入到U中时，即找到了最小生成树。

Kruskal算法

该算法的思想是维持一个森林，包含着很多树

算法输入：一张无向有权图。

准备操作：创建一个队列，存储所有的边，队列按照边的权重做排序。用T表示被选中的边

一轮循环：从队列中退出权重最小的边（1，4），判断$v_1$和$v_4$是否在同一棵树中（即是否通过已经在T中的边相连），不在则放入T中。

二轮循环：从队列中退出权重最小的边（6，7），$v_6$和$v_7$不在同一棵树中，因此放入T中。

三轮循环：从队列中退出权重最小的边（1，2），$v_1$和$v_2$不在同一棵树中，因此放入T中

以此类推，由于在边的遍历过程始终判断是否通过已经在T中的边相连（即保持了无环性），因此当选中的边数量为n-1（连通性）之后，即找到了最小生成树。

• 判断两个节点是否在同一颗树中：使用并查集，将每一次边的加入都进行一次节点集合的分类

算法的时间复杂度为$O_{(m\cdot log m)}+m\cdot O_{(1)}$，m为边的数量

最大流问题

可以如此理解最大流问题：在图示的有向有权图中，S为起点，t为终点，将水从起点通过管道（边）运输到终点，边的权重为管的容量（$m^3 / s$）。求运输水的最大流量。

• 容量（capacity）：最大的流量
• 流量（flow）：当前水的流量
• 空闲量（risidual）：容量-流量

Naive算法

此算法不能找出最大流，因为最终获得的流量取决于寻找路径的先后顺序，因此找到的是阻塞流。

算法输入：有向有权图

算法运行时，需要一个空闲量图，即将权重全都换成空闲量。初始时，空闲量图和原图相同。

一轮循环：首先找到空闲量图中的一条路径（$s - v_2 - v_4 t$），顺着这条路径水可以从起点流到终点，这一条路径中边的权重最小为2，由于最短板效应，水的流量只能为2。随后将这条路线上的空闲量全部减去2，去掉为空闲量0的边

二轮循环：找到空闲量图中的一条路径（$s - v_1 - v_3 t$），顺着这条路径水可以从起点流到终点，这一条路径中边的权重最小为2，由于最短板效应，水的流量只能为2。随后将这条路线上的空闲量全部减去2，去掉为空闲量0的边

以此类推，直到没有一条路径从s到t即找到了阻塞流

Ford-Fulkerson算法

此算法可以找到最大流，与Naive算法相同，此算法也需要空闲量图。此算法的特殊之处是可以撤销导致最大流量减少的路径选择顺序造成的影响。

一轮循环：与Naive算法相同，假设首先选取的路径为（$s - v_1 - v_4 t$）。将这条路线上的空闲量全部减去3，去掉为空闲量0的边。然后增加一条反向的流道，为后面路径撤销做准备。

二轮循环：找到空闲量图中的一条路径（$s - v_1 - v_3 - t$），同理，减去流量，去掉无空闲的边，然后加上反向的流道。由于与一轮循环中生成的反向流道有重合的边，因此将（$v_1 - s$）的流道进行合成。

三轮循环：若按照Naive算法，此时找不到可以从s通向t的流道了，但由于反向流道的存在，可以找到一条路径：（s - v_2 - v_4 - v_1 - v_3 - t），然后同理，减去流量，去掉无空闲的边，加上反向的流道，合成反向流道。

四轮循环：由于找不到可以通向$v_3$与t的边，因此无法找到一条路径，循环结束。

这种算法中，每一个反向流道都可以当成一个正常的流道去使用，因此消除了由于路径寻找顺序造成的对流道阻塞的影响，可以找到最大流。但是一些特殊情况（如下图），这种算法速度会很慢，最坏情况时间复杂度很高。循环次数$<=$最大流量

令边的数量为m，则每一轮循环的时间复杂度为$O_{(m)}$，令最大流的数量为f，则最坏情况的时间复杂度为$O_{(f \cdot m)}$

Edmonds-Karp算法

该算法为Ford-Fulkerson算法的一个特例，因为Ford-Fulkerson算法在寻找路径时可以采用任何算法，而Ford-Fulkerson算法采用最短路算法。

该算法的时间复杂度为$O_{(m^2 \cdot n)}$,m为边的数量，n为节点的数量。因为该算法时间复杂度不依赖于最大流f，而实际问题中f可能会非常大，因此该算法时间复杂度会更好。

Dinic算法

此算法不仅需要空闲量图，还需要一种层图。层图的绘制方法如下：

对于下图，右侧为原图，左侧为根据原图绘制出的层图。首先起点s为第一层，第二层为s只通过一条边指向的节点（$v_1和v_2$），第三层为第二层的节点只通过一条边指向的节点（$v_3和v_4$），第四层为第三层的节点只通过一条边指向的节点（t）。 只保留从上一层指向下一层的边，其他边都去掉而形成的图便是层图。

一轮循环：根据第一次生成的层图按照Naive算法找到阻塞流，然后在空闲量图中减去阻塞流，并增加反向流。

二轮循环：根据新的空闲量图生成新的层图，并根据新的层图找到新的阻塞流，然后在空闲量图中减去阻塞流，并增加反向流，然后合并反向流。

以此类推，直到新生成的层图的终点的层数为无穷大时（即无法找到路径通往终点），退出循环

此算法的最坏情况时间复杂度为$O_{(m\cdot n^2)}$，比Edmonds-Karp算法要更小。

最小割问题

S-T Cut

将所有节点分成两个集合S和T,起点s在S中，终点t在T中。S-T Cut就是将所有节点切成两个部分。将从S到T的边割断，则s的水将不能流到t。

容量Capacity（S，T）：是所有从S通向T的边的权重之和

最小割Min-Cut：最小的S-T Cut容量，即$min{Capacity(S,T)}$，其不唯一

最大流最小割定理

在网络流问题中，最大流的流量等于最小割的容量。

因此最大流问题等价于最小割问题，求解最小割问题可以先使用求最大流问题的算法Edmonds-Karp算法或Dinic算法

• 首先，通过求最大流问题的算法获得空闲量图，并将那些反向边都去掉。

• 有了空闲量图，便可以找到最小的S-T Cut

二部图 Bipartite Graph

将图中的节点化为U和V两个集合，U和V的内部都不能有边。

判定是否为二部图：

1. 将随机一个节点放入U中
2. 将其相邻节点放入V中
3. 重复2的操作，直到所有节点都加入到集合中，或存在两个相邻的节点在同一个集合中。

匹配Matching：将一些边放到一个集合S中，并且每两条边都不连接同一节点。

最大匹配 Maxmum-Cardinality Bipartite Matching(MCBM)

MCBM:含有边数量最多的S匹配，可能不唯一。

贪心算法

对于集合U中的一个节点，根据与其相连的边随机分配一个加入到S中，U中的其他节点也是如此，如果没有满足要求的边则不添加。

此算法找到的不一定是最大匹配

无权图中最大匹配

无权图的最大匹配问题可以转换成最大流问题，并用最大流求解算法的Edmonds-Karp算法或Dinic算法来求解最大匹配问题。

假设将二部图的边都变成有向的，边的方向从U的节点指向V的节点，新增加两个节点s和t，并新增若干边使s指向U中的所有节点，V中的所有节点指向t。

由于是无权图，因此图中所有边的流量都是1，转换成最大流问题即可获得最多的匹配边。

有权图中的最大匹配

有权图中的最大匹配问题是将匹配的边的权重和最大。最大匹配和最小匹配是可以相互转化的，即将所有权重加上符号则转化成最小匹配问题

匈牙利算法可以解决最小匹配问题（因此可以解决最大匹配问题）

匈牙利算法 Hungarian

匈牙利算法要求U和V的节点数量相同。

首先，使用一个$n \times n$的矩阵来表示边的权重。矩阵的行是U中的节点，列是V中的节点。此矩阵为邻接矩阵，匈牙利算法就是在邻接矩阵上进行操作。

对于一个邻接矩阵，找到每一行的最小值（8、35、22），然后让每一行减去对应的最小值。然后对于列也是如此。这样一来，每一行、每一列都至少有一个0。

下面开始循环，每轮循环需要按照如下步骤进行：

1. 用尽量少的线覆盖住矩阵所有0元素

1. 判断是否需要终止循环：假如需要n条线覆盖所有0元素，则停止循环；加入需要的线少于n，则继续循环。

2. 对矩阵中的元素做变换，得到更多的0元素：找到没有被线覆盖住的元素中最小的元素，然后将所有没有被线覆盖住的元素减去此最小元素，并将两条线交叉的元素加上此最小元素。

最终获得了一个需要被n条线才能覆盖住所有0的矩阵，这些0代表这最小边，需要从这些最小边中取n个才能得到最小匹配。

这个问题与数独比较相似，选取一行（或一列）只有一个0的一条边，然后其所在的行和列都可以被划掉了，以此类推

此算法的时间复杂度为$O_{(n^3)}$

稳定婚配问题 Stable Marrige

稳定婚配问题是二部图匹配问题中的一种，但是二部图中边的权重没有量化，只有大小排序。

可以用Gale-Shapley算法解决稳定婚配问题。

Gale-Shapley 算法

Gale-Shapley算法按照如下步骤循环：

• 让每个单身男生向他最喜欢的女生求婚，哪怕他最喜欢的女生已经求婚了也没关系。

• 每个女生接受她最心仪的求婚的男生。假如她已经结婚了，判断一下向他求婚的男生是否比她的现任丈夫更好，再做选择。

• 所有男生都划掉其已经求婚过的女生的名字

这种方式倾向于让男生找到更心仪的女生，对女生会更不公平。 算法的时间复杂度为$O_{(n^2)}$

• Previous
  机电系统控制基础笔记
• Next
  数字图像处理笔记