并串数据结构学习笔记(三).doc

三）基于图的几个算法
图的相关概念参考最新版的PDF的preliminaries这一章节；
建议这一部分对比pdf一起读，里面涉及比较多的算法，算法里面有很多细节问题，pdf讲算法时很多小问题值得思考

基于图的相关函数及其复杂度

图的搜索（gragh search）

注：上面是图的搜索中如何从当前层的搜索进入下一层的搜索的流程，具体实现时可以有几步合并成一步进行。将上述过程完善就可得到图的搜索的一般流程：

注：上述算法中涉及一个选择的问题，正由于这个选择（后面的步骤会相应作出一点改变）才导致了许多不同的算法，基于不同的选择，介绍三种不同算法：

三种图的搜索算法：（PFS，BFS，DFS）
PFS(priority-first search)：基于一个自己定义的优先级搜索。

BFS(breadth-first search)：基于宽度优先的搜索。即每一层所有结点访问结束后才进入下一层结点的访问。

BFS算法的访问过程
X
N
i
F
{ }

0
{s}
{s}
{a,b}
1
{a,b}
{s,a,b}
{b,c,d}
2
{c,d}
{s,a,b,c,d}
{s,c,e,f}
3
{e,f}
{s,a,b,c,d,e,f}
{ }
4
{ }
复杂度的计算：

一、 三行基于树的操作可以直接得到类似于union的计算得到
第二行是基于table的操作

single threaded sequence(st sequence)：一种sequence sequence，即一个sequence中的每一个元素均为sequence，而每个sequence按找每个点的顺序存放，每个sequence中的元素为与该sequence对应的点的邻接点按顺序组成的sequence

下面是一个st sequence的例子：

注：st sequence访问其中的元素相对方便，速度也较快，而添加或删减一条边的复杂度均较高，因此在只访问不改变存储元素的情况下使用st sequence较为方便

下面采用st sequence来生成BFS树：

注：上面对比了X,F基于sequence和st sequence实现的复杂度

DFS（depth-first search)：基于深度优先的搜索。即优先沿着一条路径访问到叶结点再访问其他路径。

定义DFS number：v/u，v表示第一次访问到该结点所用的次数；u表示最后一次访问该结点所用的次数。

BFS算法的访问过程
依次访问的结点
v
u
s
0

a

1

c
2

e
3

e（回溯）

4
f
5

f（回溯）

6
c（回溯）

7
b
8

d
9

d（回溯）

10
b（回溯）

11
a（回溯）

12
s（回溯）

13

记图中任意一条有向边为ei→ej其DFS number分别为：vi/ui，vj/uj，则：
cross edge：vivj且ui>uj
front edge：viuj
back edge：vi>vj且ui

topological sort

原理：

基于DFS number的环路检测：

higher order DFS

由此可以导出以下算法：

基于ST sequence实现的DFS

最短路径

Dijkstra’s algorithm

具体实现如下：

复杂度：

注：该算法并行度不高，work和span统一数量级

Bellman Ford algorithm
表示从s点到t点用最多k条边的最短路径长度（每条边有权值）

基于下面关系，可以得到Bellman Ford algorithm算法

每一层的复杂度为：

由于最多为迭代n次，因此复杂度最大为：

注：逆向思考，从v点往前思考

graph contration

问题：收缩的时候会部分结点有可能重复，需要避免这个问题，于是有如下两种收缩方式：

star graph伪代码如下：

第六行的union操作具体为：

通过图的收缩来判断连通性

如果想将每个连通分支的结点都返回的话，做如下改进：

复杂度分析：
假设一次迭代后，点的个数由个变成了个，
由于，因此，
因此迭代的次数期望为级别。

下面计算一个high probability的work，即认为，迭代次数为级别
注：每次至少减少的边数不少于收缩的点数

故：
当G为树时，有：(span不改变)

最小生成树（minimum spanning tree）

注：pdf中这部分限制了图的权值不允许出现重复，这个定理成立的条件便是在不出现重复权值，一旦权值重复则该定理不正确，因为最小生成树可能不止一个，这是就无法根据局部性质判断出那一条边一定不在一个最小生成树里面，不过可以确定的是，仍然选取最小的权值一定在一个最小生成树里面，但其他的最小生成树里面可能没有这条边，并且每次并不是都选取的最短权值的边

Kruskal’s algorithm

insert 的复杂度基于不同的数据结构，但不超过，由于进行了O(m）次迭代，因此，span同理也为

Prim’s algorithm

Borůvka’s algorithm

对树进行contraction，基于sequence实现其work为，span为，而update操作的work为，故总的work为，由于最多进行次迭代，因此work为，span为，用star contraction改进最终work仍为，span降低为，下面用star contraction改进：

TSP与MST的关系
前提条件：图中无权值为负的边；任意三个点a，b，c，满足三角不等式：

注：满足这个三角不等式的TSP问题称为metric TSP问题

在一棵最小生成树中任意选取一点s，用DFS算法的访问路径来进行访问，最终又回到s点，任意两个点u，v必定会有从u访问到v，再从v访问到u两种情况，路径上的每条边都访问了两次，这时有部分点被重复访问了，如下图：

于是引进shortcut来进行调整（三角不等式保证了总权值不会增加），如下图：

这里给出了一种访问每个点的并回到起点的方案，而且其复杂度为MST算法复杂度的两倍，而最好的情况是MST为一条线且最后一步直接回到起点，因此有：