- 设
G
=
(
V
,
E
)
G=(V,E)
G=(V,E)是具有n个顶点的网络，
T
=
(
U
,
T
E
)
T=(U,TE)
T=(U,TE)是
G
G
G的最小生成树，其中
U
U
U是
T
T
T的边集合，
T
T
T的初始状态是空树
- 从集合 V V V中任取一个顶点 V 0 V_0 V0放入 U U U中，此时 U = { V 0 } U={V_0} U={V0}， T E TE TE为空集
- 在所有两端各在 U U U和 V − U V-U V−U的边中，找出权最小的边 ( u , v ) (u,v) (u,v)，其中 u ∈ U , v ∈ V − U uin U,vin V-U u∈U,v∈V−U。将该边放入 T E TE TE，并将顶点 v v v放入集合 U U U
- 重复上述操作直到 U = V U=V U=V为止
- 结果 T E TE TE有 n − 1 n-1 n−1条边， T = ( U , T E ) T=(U,TE) T=(U,TE)就是 G G G的一棵最小生成树
- 生成的树用类似DFS生成树的数据表示，用vnum表示顶点数，用含有vnum个元素的表mst保存最小生成树的边
- mst[1] = ((1, 2), 10)表示边(1,2)在mst且权值为10
- mst[i] = None表示i不属于 U U U
- 用一个优先队列cands记录候选的最短边，元素形式为(w, i, j)，表示从顶点i到j的边为候选，权值为w
- 算法过程：
- 初始把(0, 0, 0)放入优先队列，表示从顶点0到自己的长度为0的边
- 循环的第⼀次迭代将把顶点 0 记⼊最⼩⽣成树顶点集 U，即设mst[0] = (0, 0, 0)。还会把顶点 0 到其余顶点的边按权值存⼊优先队列 cands，表示待考察的候选边集合
- 执⾏中反复选择cands⾥记录的最短边(u, v)。如确定它是连接
U
U
U 中顶点与
V
−
U
V-U
V−U
顶点的边（即发现 v v v 是 V − U V-U V−U的顶点），就把这条边及其权记⼊mst[v]，并把 v v v的出边存⼊ cands；否则直接丢掉 - 结束时mst中是最小生成树的 n n n条边（包括(0, 0)）
①
n
=
6
n=6
n=6，在只有顶点
v
0
v_0
v0的最小生成树中
mst[0] = (0, 0, 0) cands = [(0,1,10), (0,4,19), (0,5,21)]
②取出cands中权值最小的边(0, 1, 10)，将顶点 v 1 v_1 v1及边 ( v 0 , v 1 ) (v_0, v_1) (v0,v1)加入最小生成树，并将 v 1 v_1 v1的出边加入cands
mst[1] = (0,1,10) cands=[(1,2,5), (1,3,6), (1,5,11), (0,4,19), (0,5,21)]
③在cands中取出权值最小的边(1, 2, 5)，将顶点 v 2 v_2 v2及边 ( v 1 , v 2 ) (v_1, v_2) (v1,v2)加入最小生成树，并将 v 2 v_2 v2的出边加入cands
mst[2] = (1,2,5) cands=[(1,3,6), (2,3,6), (1,5,11), (0,4,19), (0,5,21)]
④在cands中取出权值最小的边(1, 3, 6)，将顶点 V 3 V_3 V3及边 ( v 1 , v 3 ) (v_1, v_3) (v1,v3)加入最小生成树，并将 v 3 v_3 v3的出边加入cands
mst[3] = (1,3,6) cands=[(2,3,6), (1,5,11), (3,5,14), (3,4,18), (0,4,19), (0,5,21)]
⑤权值最小的边 ( v 2 , v 3 ) (v_2, v_3) (v2,v3)不在生成树中，取出下一条权值最小的边(1, 5, 11)，将顶点 v 5 v_5 v5及边 ( v 1 , v 5 ) (v_1, v_5) (v1,v5)加入最小生成树，并将 v 5 v_5 v5的出边加入cands
mst[5] = (1,5,11) cands=[(3,5,14), (5,3,14), (3,4,18), (0,4,19), (0,5,21), (5,0,21), (5,4,33)]
⑥权值最小的边 ( v 3 , v 5 ) (v_3, v_5) (v3,v5)不在生成树中，取出下一条权值最小的边(3, 4, 18)，将顶点 v 4 v_4 v4及边 ( v 3 , v 4 ) (v_3, v_4) (v3,v4)加入最小生成树，并将 v 4 v_4 v4的出边加入cands
mst[4] = (3,4,18) cands=[(0,4,19), (4,0,19), (0,5,21), (5,0,21), (5,4,33), (4,5,33)]
此时cands中所有的边都不在最小生成树中。
def prim(graph):
vnum = graph.vertex_num() # 自定义图数据结构，取出总节点数
mst = [None] * vnum # 创建最小生成树容器
cands = PrioQueue([(0, 0, 0)]) # 边的缓存队列， 自定义数据结构 - 优先队列，见Lecture3,4
count = 0 # 计数缓存
while count < vnum and not cands.is_empty(): # 如果最小生成树的节点数小于总节点数，且边的缓存队列不为空则一直循环
w, u, v = cands.dequeue() # 取出优先队列权值最小的一项 （权值，起点，终点）
if mst[v]: # 如果终点在最小生成树中记录过，则必然不是最小生成树的边
continue # 取下一个权值最小的边
# 此时该边的起点在最小mst， 终点在graph - mst
mst[v] = ((u, v), w) # 存入最小生成树
count += 1 # 数量+1
for vi, w in graph.out_edges(v):
if not mst[vi]: # 对于终点未在最小生成树中记录过的出边
cands.enqueue((w, v, vi)) # 加入边的缓存队列
return mst
1.2 算法分析
- 时间复杂性： O ( ∣ E ∣ log ∣ E ∣ ) O(|E|log |E|) O(∣E∣log∣E∣)
- 空间复杂性： O ( ∣ E ∣ ) O(|E|) O(∣E∣)
- 如果图用邻接矩阵表示，那么时间复杂度为 O ( max ( ∣ V ∣ 2 , ∣ E ∣ log ∣ E ∣ ) ) O(max (|V|^2, |E|log |E|)) O(max(∣V∣2,∣E∣log∣E∣))
- Prim 算法的缺点是可能把没价值的边存⼊队列 cands
- 如果算法中只缓存连接
U
U
U和
V
−
U
V-U
V−U的边，那么保存的边不超过
∣
V
∣
|V|
∣V∣条，空间复杂度就是
O
(
∣
V
∣
)
O(|V|)
O(∣V∣)
- 获得这些边中权值最小的边 -> 采用堆结构，那么时间复杂度 O ( log ∣ V ∣ ) O(log |V|) O(log∣V∣)
- 获得这条边后高效更新。->在 O ( log ∣ V ∣ ) O(log |V|) O(log∣V∣)时间内从节点找到堆里的元素，修改原有的权值并恢复堆结构
- 即建立队列，支持：
- O ( n ) O(n) O(n)建堆； O ( log n ) O(log n) O(logn)获取最小值
- 从某个index（顶点序号）出发， O ( 1 ) O(1) O(1)时间内访问其weight；从某个id和w出发， O ( log n ) O(log n) O(logn)时间内减去权值dec_weight(idx, w)
- 称这种结构为可减权堆，定义为类DecPrioHeap，支持：
- DecPrioHeap(list)，其中list的项的形式为(w, index, other)，类的对象dec_heap是以list的项为元素、以w为权的小顶堆
- dec_heap.get_min()弹出堆中的最小元并恢复堆， O ( log n ) O(log n) O(logn)
- dec_heap.weight(idx)得到idx为index的元素的权值， O ( 1 ) O(1) O(1)
- dec_heap.dec_weight(idx, w, other)在w小于dec_heap里含有idx元素的权值时，将该元素改为(w, idx, other并恢复堆的结构， O ( log n ) O(log n) O(logn)
- dec_heap.is_empty()在dec_heap为空时返回True
def prim_advanced(graph):
vnum = graph.vertex_num()
wv_seq = [[graph.get_edge(0, v), v, 0] for v in range(vnum)]
# 只记录连接U和V－U的边列表，此时U中只有0，V-U是V
connects = DecPrioHeap(wv_seq) # 根据列表创建有序性的可减权堆
mst = [None] * vnum
while not connects.is_empty(): # 只要堆不空，就循环
w, mv, u = connects.get_min() # 取出最近的两个顶点，和连接边
if w == inf: # 如果和最近顶点不连通，说明没有生成树
break
mst[mv] = ((u, mv), w) # 存入最小生成树
for v, w in graph.out_edges(mv): # 检查mv顶点的邻接边
if not mst[v] and w < connects.weight(v): # 如果邻接节点不在树中，而且这条边的权值更小
connects.dec_weight(v, w, mv) # 修改堆
return mst
- 空间复杂度： O ( ∣ V ∣ ) O(|V|) O(∣V∣)
- 时间复杂度： O ( max ( ∣ V ∣ log ∣ V ∣ , ∣ E ∣ log ∣ V ∣ ) ) O(max (|V|log |V|, |E|log |V|)) O(max(∣V∣log∣V∣,∣E∣log∣V∣))
- 设 G = ( V , E ) G=(V,E) G=(V,E)是网络，最小生成树的初始状态是有 n n n个顶点但无边的非连通图 T = ( V , φ ) T=(V,varphi ) T=(V,φ)， T T T中每个顶点自己是一个连通分量（只有一个顶点）
- 将 E E E中的边按照权递增顺序排列，从小到大依次选择顶点分别在两个连通分量中的边加入 T T T，则原来的两个连通分量（单顶点）连接组成一个连通分量
- 类似地，直到 T T T中所有顶点都在一个连通分量上为止，则该连通分量就是 G G G的一棵最小生成树
如图所示，E中的边按照权递增排列为：
(
v
1
,
v
2
)
:
5
→
(
v
1
,
v
3
)
:
6
→
(
v
2
,
v
3
)
:
6
→
(
v
4
,
v
5
)
:
7
→
(
v
0
,
v
1
)
:
10
→
(
v
1
.
v
5
)
:
11
→
(
v
3
,
v
5
)
:
14
→
(
v
3
,
v
4
)
:
18
→
(
v
0
,
v
4
)
:
19
→
(
v
0
,
v
5
)
:
21
(v_1,v_2):5 to(v_1,v_3):6to(v_2,v_3):6to(v_4,v_5):7to(v_0,v_1):10to(v_1.v_5):11to(v_3,v_5):14to(v_3, v_4):18to(v_0, v_4):19to(v_0, v_5):21
(v1,v2):5→(v1,v3):6→(v2,v3):6→(v4,v5):7→(v0,v1):10→(v1.v5):11→(v3,v5):14→(v3,v4):18→(v0,v4):19→(v0,v5):21
①初始状态，
T
T
T是只有6个顶点的非连通图
②权最小的边
(
v
1
,
v
2
)
(v_1,v_2)
(v1,v2)的两个顶点分别属于两个连通分量（单顶点），将边
(
v
1
.
v
2
)
(v_1.v_2)
(v1.v2)加入
T
T
T
③同理，将边
(
v
1
,
v
3
)
(v_1,v_3)
(v1,v3)加入
T
T
T
④此时权最小的边是
(
v
2
,
v
3
)
(v_2,v_3)
(v2,v3)，都在同一个连通分量内，于是舍去；取下一条最小权边
(
v
4
,
v
5
)
(v_4,v_5)
(v4,v5)，加入
T
T
T
⑤同理，将
(
v
0
,
v
1
)
(v_0,v_1)
(v0,v1)、
(
v
1
,
v
5
)
(v_1,v_5)
(v1,v5)加入
T
T
T，这时
T
T
T中含有的边数为5，成为一个连通分量，就是
G
G
G的一棵最小生成树
这样的最小生成树不一定唯一，比如权值相同的边，排序不同，树的形状也可能相应不同。
while T 中所含的边数< n-1: 从E中选取当前最短边(u, v) 从E中删除(u, v) if (u, v)加入T中部产生回路： 边(u, v)加入T中
- 关键问题：判断两个顶点在
T
T
T中是否分别属于两个连通分量
- 判断是否有路径 → to →太费时间
- 考虑为每个连通分量确定一个“代表元”，在算法过程中对每个顶点记录并维护其连通分量归属
- 代表元相同的顶点相互连通
- 加入一条边，则需要选择一个顶点，让合并的两个连通分量中的所有顶点都以它为代表元；因此需要更新这些顶点的代表元
- 用表reps记录代表元关系，在初始状态中各顶点以自己为代表元；在算法过程中更新resps[v]
def kruskal(graph):
vnum = graph.vertex_num() # 总节点数
reps = [i for i in range(vnum)] # 各顶点以自己为代表元
mst, edges = [], []
for vi in range(vnum):
for v, w in graph.out_edges(vi):
edges.append((w, vi, v)) # 取出所有边，(权，起点，终点)
edges.sort() # 按权值从小到大排序， O(nlogn)
for w, vi, vj in edges: # 取出权值最小的边
if reps[vi] != reps[vj]: # 如果边的两个顶点拥有两个不同的代表元，则属于两个不同的连通分量
mst.append(((vi, vj), w)) # 存入最小生成树
if len(mst) == vnum - 1: # 存入的边数恰好等于顶点数-1，则生成完毕
break
rep, orep = reps[vi], reps[vj] # 取出两个顶点的代表元
for i in range(vnum): # 在T的所有顶点中
if reps[i] == orep: # 代表元更改为起点的代表元
reps[i] = rep
return mst
2.3 算法分析
- 时间复杂性：
- 建立边表edges需要 O ( ∣ E ∣ ) O(|E|) O(∣E∣)，按照权值大小排序需要 O ( ∣ E ∣ log ∣ E ∣ ) O(|E|log|E|) O(∣E∣log∣E∣)
- 循环：
- 遍历取出最短边不超过 O ( ∣ E ∣ ) O(|E|) O(∣E∣)
- 修改代表元 O ( n 2 ) O(n^2) O(n2)
- 循环过程中的时间复杂度 O ( max ( ∣ E ∣ log ∣ E ∣ , ∣ V ∣ 2 ) O(max(|E|log|E|, |V|^2) O(max(∣E∣log∣E∣,∣V∣2)
- 总时间复杂度是 O ( max ( ∣ E ∣ log ∣ E ∣ , ∣ V ∣ 2 ) O(max(|E|log|E|, |V|^2) O(max(∣E∣log∣E∣,∣V∣2)
- 空间复杂性： O ( max ( ∣ E ∣ , ∣ V ∣ ) O(max(|E|,|V|) O(max(∣E∣,∣V∣)，可以认为是 O ( ∣ E ∣ ) O(|E|) O(∣E∣)
- 如果用邻接矩阵表示图，则建立边表需要 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)
- 如果图中从⼀个顶点可以到达另⼀个顶点，则称这两个顶点间存在⼀条路径
- 从⼀个顶点到另⼀个顶点间可能存在多条路径，⽽每条路径上经过的边数并不⼀定相同
- 如果图是⼀个带权图，则路径⻓度为路径上各边的权值的总和
- 两个顶点之间路径⻓度最短的那条路径称为两个顶点间的最短路径，其路径⻓度称为最短路径⻓度
- 如何求解最短路径？
- Dijkstra算法求解从顶点 v 0 v_0 v0出发到其它各顶点最短路径。
- 按路径⻓度递增的次序产⽣最短路径，该算法假设所有边的权都⼤于等于零
- 设置 U U U存放已经求出最短路径的顶点， V − U V-U V−U是尚未确定最短路径的顶点集合
- 每一个顶点对应一个距离值，集合 U U U中顶点的距离值是从顶点 v 0 v_0 v0到该顶点的最短距离长度
- V − U V-U V−U中顶点的距离值是从顶点 v 0 v_0 v0到该顶点的只包含 U U U中顶点为中间顶点的最短路径长度
- U U U的初始状态为 { v 0 } {v_0} {v0}
- 按照路径长度递增的次序逐个产生 v x v_x vx的最短路径，把 v x v_x vx加入 U U U中，直到 U = V U=V U=V时终止
- 如何为
U
U
U扩充顶点，在
V
−
U
V-U
V−U中找到下一个能确定最短路径的顶点？
- v i ∈ V − U v_iin V-U vi∈V−U的已知最短距离定义为：若存在 v j ∈ U v_jin U vj∈U有边 ( v j , v i ) (v_j,v_i) (vj,vi)，则 c d i s ( v i ) = min { d i s ( v j ) + w ( v j , v i ) ∣ v j ∈ U } cdis(v_i)=min {dis(v_j)+w(v_j,v_i)|v_jin U} cdis(vi)=min{dis(vj)+w(vj,vi)∣vj∈U}，其中 d i s ( v j ) dis(v_j) dis(vj)表示从 v 0 v_0 v0到 v j v_j vj的距离， w ( v j , v i ) w(v_j,v_i) w(vj,vi)是 ( v j , v i ) (v_j,v_i) (vj,vi)的权；如果没有这样的 v j v_j vj，定义 c d i s ( v i ) = ∞ cdis(v_i)=infty cdis(vi)=∞
- 若v_i是 V − U V-U V−U中 c d i s cdis cdis最小的节点，那么 d i s ( v i ) = c d i s ( v i ) dis(v_i)=cdis(v_i) dis(vi)=cdis(vi)，那么从 v 0 v_0 v0到 v i v_i vi的最短路径已知，可以把 v i v_i vi加入集合 U U U
- 初始状态： U U U中只有顶点 v o v_o vo，顶点 v o v_o vo对应的距离值为0； V − U V-U V−U中顶点 v i v_i vi的距离值为边 ( v 0 , v i ) , i = 1 , 2 , . . . , n − 1 (v_0,v_i),i=1,2,...,n-1 (v0,vi),i=1,2,...,n−1的权，如果 v 0 v_0 v0和 v i v_i vi无边直接相连，则 v i v_i vi的距离值为 ∞ infty ∞
- 处理流程：
- ①在集合 V − U V-U V−U中选择距离值最小的顶点 v m i n v_{min} vmin加入 U U U
- ②由于 v m i n v_{min} vmin加入， V − U V-U V−U中某些顶点的已知最短路径长度可能发生改变，于是对 V − U V-U V−U中各顶点的距离值进行修正：如果加入顶点 v m i n v_{min} vmin为中间顶点后，使 v 0 v_0 v0经过 v m i n v_{min} vmin到 v i v_i vi的距离值比原来的距离值更小，则修改 v i v_i vi的距离值，该路径为新的最短路径
- ③重复①、②操作，直到从
v
0
v_0
v0出发可以到达的所有顶点都在
U
U
U中为止
绿⾊为从 U U U到 V － U V－U V－U的边，选 ( v 0 , v 2 ) (v_0, v_2) (v0,v2)把 v 2 v_2 v2加⼊ U U U
选 ( v 2 , v 3 ) (v_2,v_3) (v2,v3)，把 v 3 v_3 v3加入 U U U
选 ( v 3 , v 1 ) (v_3,v_1) (v3,v1)，把 v 1 v_1 v1加入 U U U
选 ( v o , v 4 ) (v_o,v_4) (vo,v4)，把 v 4 v_4 v4加入 U U U
- 性质：如果 v ′ v' v′是初始点 v 0 v_0 v0到 v v v的最短路径 p p p上 v v v前一个顶点，那么 p p p去掉最后顶点 v v v得到的路径 p ′ p' p′也是 v 0 v_0 v0到 v ′ v' v′的最短路径
- 所以，记录 v 0 v_0 v0到 v v v的最短路径，只需记录 v 0 v_0 v0到 v v v最短路径上的前一顶点
- 即，记录所有最短路径只需要一个 n − 1 n-1 n−1元的边集合
- 拥有vnum个元素的paths表用于记录从 v 0 v_0 v0到顶点 v i v_i vi的最短路径和路径长度，paths[i]=(v',p)； v ′ v' v′是 v 0 v_0 v0到 v i v_i vi最短路径上 v i v_i vi的前一顶点， p p p是最短路径长度。此外，paths[v]=None表示 v ∉ U vnotin U v∈/U
- 最短路径的候选边集按照路径长度记录在优先队列cands中，元素(p,v,v')表示从 v 0 v_0 v0经 v v v到 v ′ v' v′的距离值为 p p p。按 p p p值在cands中排序。如果最短侯选边的终点 v ′ v' v′在 V − U V-U V−U，将其加入paths，并将经由 v ′ v' v′可达的其它顶点及其路径长度记录cands
def dijkstra_shortest_paths(graph, v0):
vnum = graph.vertex_num()
assert 0 <= v0 < vnum
paths = [None] * vnum
count = 0
cands = PrioQueue([(0, v0, v0)])
while count < vnum and not cands.is_empty():
plen, u, vmin = cands.dequeue()
if paths[vmin]:
continue
paths[vmin] = (u, plen)
for v, w in graph.out_edges(vmin):
if not paths[v]:
cands.enqueue((plen + w, vmin, v))
count += 1
return paths
①初始状态， U = { v 0 } U={v_0} U={v0}，
paths[0] = (0,0) cands＝[(10, 0, 2), (45, 0, 4), (50, 0, 1)]
②在集合 V － U V－U V－U中找出距离值最⼩的顶点 v 2 v2 v2，将 v 2 v2 v2加⼊ U U U中，然后调整 V － U V－U V－U中顶点的距离值，将边 ( v 2 , v 3 ) (v_2,v_3) (v2,v3)放⼊优先队列。
paths[2]＝(0, 10) cands＝[(25, 2, 3), (45, 0, 4), (50, 0, 1)]
③同理在集合 V － U V－U V－U中找出当前距离值最⼩的顶点v3，加⼊ U U U中，并调整集合 V － U V－U V－U中顶点的距离值。
paths[3]＝(2, 25) cands＝[(41,3,1), (45, 0, 4), (50, 0, 1), (60, 3, 4)]
④在集合 V － U V－U V－U中找出当前距离值最⼩的顶点 v 1 v_1 v1，加⼊ U U U中，并调整集合 V － U V－U V－U中顶点的距离值。
paths[1]＝(3, 41) cands＝[(45, 0, 4), (46, 1, 4), (50, 0, 1) , (60, 3, 4)]
⑤在集合 V － U V－U V－U中找出当前距离值最⼩的顶点 v 4 v_4 v4，将 v 4 v_4 v4加⼊ U U U中，并调整集合 V － U V－U V－U中顶点的距离值。
paths[4]＝(0, 45) cands＝[(46, 1, 4), (50, 0, 1) , (60, 3, 4)]
⑥ cands中各元素依次出队，没有可以再加⼊集合 U U U的顶点了，说明从顶点 v 0 v_0 v0到顶点 v 5 v_5 v5之间⽆路径相通。过程结束
函数返回的结果paths可以得到 v 0 v_0 v0到各个顶点的最短路径
paths = [(0, 0), (3, 41), (0, 10), (2, 25), (0, 45), None]
- 如果取出从 v 0 v_0 v0到 v 1 v_1 v1的最短路径，由paths[1]=(3, 41)可知，最短路径上 v 1 v_1 v1的前一个顶点是 v 3 v_3 v3
- 由paths[3] = (2, 25)可知， v 3 v_3 v3的前一个顶点是 v 2 v_2 v2
- 由paths[2] = (0, 10)可知， v 2 v_2 v2的前一个顶点是 v 0 v_0 v0
- 即最短路径 v 0 → v 2 → v 3 → v 1 v_0to v_2to v_3to v_1 v0→v2→v3→v1，路径长度为41
- 时间复杂度：
- 初始化： O ( ∣ V ∣ ) O(|V|) O(∣V∣)
- 主体部分与 P r i m Prim Prim算法类似， O ( ∣ E ∣ log ∣ E ∣ ) O(|E|log|E|) O(∣E∣log∣E∣)
- 空间复杂度：
O
(
max
(
∣
E
∣
,
∣
V
∣
)
)
=
O
(
∣
E
∣
)
O(max(|E|,|V|))=O(|E|)
O(max(∣E∣,∣V∣))=O(∣E∣)
- 算法需要找到更短的路并更新相关信息，与Prim算法类似，可以采用“可减权堆”给出 O ( ∣ V ∣ ) O(|V|) O(∣V∣)空间复杂度的算法
- 如何求出图中各对顶点之间的最短路径？
- 构造最⼩⽣成树的Prim 算法和Kruskal算法
- Prim 算法和Kruskal算法的设计都是贪⼼法。为什么贪⼼法在这⾥都能够构造出（最⼩⽣成树）最优解？
- 考虑反证法
- 最短路径概念
- Dijkstra 算法基于类似于最⼩⽣成树的想法，或者说是⼀种“宽度优先搜索”。其中⽤到了类似 MST 的性质
- 它逐个找出可以确定最短路径的顶点，同时也找到了到新确定最短路径的顶点的路径
- 做完前⼀步后更新信息，保证记录的都是⾄今已知的最短路径
- 是典型的动态规划
