本章内容
- 通用深度优先DFS算法
- 单源最短路径问题
- 最小生成树
一、通用深度优先DFS算法
一般的深度优先搜索目标是在图上进行尽量深的搜索，连接尽量多的顶点，必要时可以进行分支（创建了树） 有时候深度优先搜索会创建多棵树，称为“深度优先森林”。深度优先搜索同样要用到顶点的“前驱” 属性，来构建树或森林，另外要设置“发现时间”和“结束时间”属性。
- 前者是在第几步访问到这个顶点（设置灰色）
- 后者是在第几步完成了此顶点探索（设置黑色）
与BFS的区别在于，在添加兄弟节点之前，先添加层次。
代码实现：
class DFSGraph(Graph):
def __init__(self):
super().__init__()
self.time = 0
def dfs(self):
'''
可能会生成多个深度优先搜索森林
'''
#颜色初始化
for aVertex in self:#父类已经实现了iter()方法
aVertex.setColor('White')
aVertex.setPred(-1)
#如果还有未包括的顶点，则建森林
for aVertex in self:
if aVertex.getColor() == 'White':
self.dfsvisit(aVertex)
def dfsvisit(self, rootVertex):
'''
不同于BTS中的队列，这里的递归隐式使用了栈
'''
rootVertex.setColor('Gray')
self.time += 1
rootVertex.setDiscovery(self.time)
for nextVertex in rootVertex.getconnections():
if nextVertex.getColor == 'White':
nextVertex.setPred(rootVertex)
self.dfsvisit(nextVertex)
rootVertex.setColor('Black')
self.time += 1
rootVertex.setFinish(self.time)
即一个顶点的“发现时间”总小于所有子顶点的“发现时间” 而“结束时间”则大于所有子顶点“结束时间” 比子顶点更早被发现，更晚被结束探索，类比括号和子括号的关系。
DFS算法分析：
dfs函数中有两个循环，每个都是|V|次，所以 是O(|V|)。而dfsvisit函数中的循环则是对当前顶点所连接的顶点进行，而且仅有在顶点为白色的情况下才进行递归调用，所以对每条边来说只会运行一 步，所以是O(|E|) 加起来就是和BFS一样的O(|V|+|E|)。
DFS算法的应用：
1、拓扑排序
拓扑排序处理一个DAG，输出顶点的线性序列，使得两个顶点v,w，如果G中有(v,w)边，在线性序列中v就出现在w之前。
在如上所示的DFS之中，进行拓扑排序非常方便按照vertex中finish从大到小的顺序，即可快速完成拓扑排序。
2、强连通分支
定义：
图G的一个子集C，C中的任意两个顶点v,w之间都有路径来回，即 (v,w)(w,v)都是C的路径， 而且C是具有这样性质的最大子集。
在图中发现高度聚集节点群的算法，即寻找“强连通分支Strongly Connected Components”算法。一旦找到强连通分支，可以据此对图的顶点进行分类，并对图进行化简。
示例：
先熟悉一个概念：Transposition转置
一个有向图G的转置GT，定义为将图G的所有边的顶点交换次序，如将(v,w)转换为(w,v) 可以观察到图和转置图在强连通分支的数量和划分上，是相同的。
Kosaraju算法:
对G进行DFS，获得每个vertex的finish
G进行转置得到GT
对GT使用DFS（注意在每个顶点的搜索循环中，要以顶点的结束时间倒序顺序进行搜索）得到深度优先森林，那么其中的每一棵树都是一个强连通分支
示例：
第一趟：
第二趟：
结果：
二、单源最短路径问题
目标：获得从一个节点出发到达图中任意顶点的最短距离。
解决带权图的最短路径问题，与使用BFS解决词梯问题非常相似，只不过边中带了权重。这里使用Dijkstra算法，迭代得出一个顶点到所有顶点的最短路径。实现上在Vertex类中添加dist来存储起点到本结点的最短权重之和，顶点的访问次序由优先队列控制。队列中作为优先级的是dist，具有最小dist的结点出队，计算其它结点的权重和，引起堆的重排，随后根据更新dist优先级再依次出队。注意Dijkstra只能处理权值为正的带权图。
代码实现：
def dijkstra(graph, start):
#对所有顶点建堆形成优先队列
pq = PriorityQueue()
start.setDistance(0)
pq.buildHeap([(v.getDistance(), v) for v in graph])
while not pq.empty():
#优先队列出队
currentVert = pq.delmin()
#修改邻接顶点dist，并逐个重排队列
for nextVertex in currentVert.getconnections():
newDist = currentVert.getDistance() + currentVert.getweight(nextVertex)
if newDist < nextVertex.getDistance():
nextVertex.setDistance(newDist)
nextVertex.setPred(currentVert)
pq.decreaseKey(nextVertex, newDist)
Dijkstra算法需要具备整个图的数据，涉及巨大数据量的问题，同时动态变化的数据特性也使得保存全图缺乏现实性。
Dijkstra算法分析：
首先，将所有顶点加入优先队列并建堆，时间复杂度为O(|V|) 。其次，每个顶点仅出队1次，每次delMin 花费O(log|V|)，一共就是O(|V|log|V|) 。另外，每个边关联到的顶点会做一次 decreaseKey操作（O(log|V|))，一共是O(|E|log|V|) 。上面三个加在一起，数量级就是O((|V|+|E|)log|V|)。
三、最小生成树
生成树：
拥有图中所有的顶点和最少数量的边， 以保持连通的子图。
图G(V,E)的最小生成树，指包含所有节点v，以及E的无圈子集，并且边的权重之和最小。
解决：
最小生成树问题的Prim算法，属于 “贪心算法” ，即每步都沿着最小权重的边向前搜索。
思路：
if T还不是生成树：
则反复做：
找到一条最小权重的可以安全添加的边
将边添加到树T
“可以安全添加”的边:
定义为一端顶点在树中，另一端不在树中的边，以便保持树的无圈特性。
代码实现：
def prim(G,start):
pq = PriorityQueue()
# 节点初始化
for v in G:
v.setDistance(sys.maxsize)
v.setPred(None)
start.setDistance(0)
pq.buildHeap([(v.getDistance(), v) for v in G])
while not pq.empty():
currentVert = pq.delmin()
# distsance仅代表从current到next的距离，根据distance进行重排
for nextVert in currentVert.getconnections():
newCost = currentVert.getweight(nextVert)
if nextVert in pq and newCost < nextVert.getDistance():
nextVert.setPred(currentVert)
nextVert.setDistance(newCost)
pq.decreasekey(nextVert, newCost)
网友评论