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

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

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

图的搜索（graghsearch）

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

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

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

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

BFS算法的访问过程XNiF{}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的操作

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

下面是一个stsequence的例子：

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

下面采用stsequence来生成BFS树：

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

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

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

BFS算法的访问过程依次访问的结点vus0a1c2e3e（回溯）4f5f（回溯）6c（回溯）7b8d9d（回溯）10b（回溯）11a（回溯）12s（回溯）13

记图中任意一条有向边为ei→ej其DFSnumber分别为：vi/ui，vj/uj，则：
crossedge：vi<vj且ui<uj或vi>vj且ui>uj
frontedge：vi<vj且ui>uj
backedge：vi>vj且ui<uj

保存DFSnumber的DFS算法如下：

topologicalsort

原理：

基于DFSnumber的环路检测：

higherorderDFS

由此可以导出以下算法：

基于STsequence实现的DFS

最短路径

Dijkstra’salgorithm

具体实现如下：

复杂度：

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

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

基于下面关系，可以得到BellmanFordalgorithm算法

每一层的复杂度为：

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

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

graphcontration

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

stargraph伪代码如下：

第六行的union操作具体为：

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

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

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

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

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

最小生成树（minimumspanningtree）

注：pdf中这部分限制了图的权值不允许出现重复，这个定理成立的条件便是在不出现重复权值，一旦权值重复则该定理不正确，因为最小生成树可