【数据结构与算法】图的搜索——广度优先遍历、最小生成树
图的表示
- 邻接链表: 用字典实现.有向图的邻接链表的总长度等于图的边个数;无向图的邻接链表的总长度等于图的边个数的2倍.
- 邻接矩阵:用于最短路径算法.
Disjoint Set 数据结构
该数据结构维护一个不相交动态集的集合，每个集合有一个代表，不关心谁做代表。
支持三种操作：
MAKE_SET(x)
FIND_SET(x)
UNION(x,y)
应用
确定无向图的连通分量：
MAKE_CONNECTED_COMPONENTS(G):for each v in G.V:MAKE_SET(v)for each (u,v) in G.E:if FIND_SET(u) != FIND_SET(v):UNION_SET(u,v)
判断无向图中两个结点是否在同一个连通分量：
IS_SAME_COMPONENTS(u,v):return FIND_SET(u) == FIND_SET(v)
链表表示
- 一个链表对应一个子集，链表头包含head和tail属性，head指向第一个对象，tail指向最后一个对象。
- 合并操作的耗时分析
struct Obj;struct LinkedList{LinkedList(char n) {}Obj* head;Obj* tail;
};struct Obj{char n;Obj* next;LinkedList* ll;
};
有根树表示
每棵树的根包含集合的代表。
使用启发式策略实现合并操作
首先，增加rank属性，
MAKE_SET(x):x.p = xx.rank = 0
UNION(x,y):LINK(FIND_SET(x), FIND_SET(y))
LINK(u,v):
if u.rank > v.rank:v.p = u
else:u.p = vif u.rank == v.rank:v.rank += 1
带有路径压缩的FIND_SET
FIND_SET(x):
if x.p != x:x.p = FIND_SET(x.p)
return x.p
图的搜索算法
图搜索算法是一些图算法的开始步骤,或被优化成其他的图算法.
广度优先遍历
使用队列，先进后出遍历节点，使用节点内的一个变量记录其是否已被遍历，图采用邻接链表形式输入
Col = enum.Enum("Color", ("White", "Gray", "Black"))class Vertex:def __init__(self, u, col, pi):self._cnt += 1self.u = uself.col = colself.pi = piself.d = math.infdef __repr__():return "%s"%self.u
def BFS(G, s):#初始化初节点s外，其他节点均标记为为被访问，深度设为无穷大s.col = Grays.d = 0s.pi = NoneQ = []while Q:u = Q.pop(0)for i in G[u]:if i.col == Col.White:i.col = Col.Grayi.d = u.d + 1i.pi = uQ.append(i)u.col = Col.Black
BFS同时生成广度优先搜索树,对于每个从源结点s到可以到达的结点v,广度优先搜索树中从源结点s到结点v的简单路径即图中从s到v的最短路径.该算法可以用于有向图\无向图.
注意权重图暂时无法求其最短路径.
最短路径
- 打印最短路径
使用广度优先搜索，记录每个节点的前驱
def PrintPath(G,s,e,path=[]):if e == s:path.append(e)print(e)returnif not e.pi:print("No path from",s,"to",e)else:PrintPath(G,s,e.pi,path)print(e)path.append(e)
深度优先搜索
发现时刻与完成时刻
强连通分量
其指内部两两结点可以相互到达的最大结点集合.
SCC(G):DFS(G)compute G.T按照结点的结束时刻降序遍历的DFS(G.T) 返回深度优先搜索森林中的树,即强连通分量
最小生成树
连接所有结点的最小权重的图边集合的子集
求MST的算法采用贪心策略,每一个时刻生长MST的一条边,贪心策略管理的边集合A遵循如下循环不变式:
每次循环前,A是某MST的子集.
安全边:这样的边,加入A后循环不变式仍成立的边.
切割:顶点集的一个划分
横跨切割:一条边的两个结点在两个集合中
轻量级边:满足某指定性质的权重最轻的边
尊重:边集合A中每条边未横跨一切割,称该切割尊重A
安全边定理:A是MST的一个子集,切割尊重A,某边是横跨该切割的轻量级边,则该边是A的安全边.
连通图G中权重最小的一条边(u, v)一定是G的某个最小生成树中的一条边。采用反证法实现，假设(u, v)不是任一个最小生成树中的一条边，设T是一个MST，其中有一个结点x连接u，设R=T-(x,u)，则
w ( T ) = w ( R ) + w ( x , u ) > w ( R ) + w ( u , v ) w(T)=w(R)+w(x,u)>w(R)+w(u,v) w(T)=w(R)+w(x,u)>w(R)+w(u,v)
可见T的权重不是最小的生成树，与已知矛盾。