PDF《数据结构》

24 数据结构 a d c b e f g h i

4 8

7 9

8 11

7 2

6 1

2 4

14 10

25 数据结构 a d c b e f g h i

4 8

7 9

8 11

7 2

6 1

2 4

14 10

26 数据结构 a d c b e f g h i

4 8

7 9

8 11

7 2

6 1

2 4

14 10

27 数据结构 a d c b e f g h i

4 8

7 9

8 11

7 2

6 1

2 4

14 10

28 数据结构 a d c b e f g h i

4 8

7 9

8 11

7 2

6 1

2 4

14 10

29 数据结构 a d c b e f g h i

4 8

7 9

8 11

7 2

6 1

2 4

14 10

30 数据结构 a d c b e f g h i

4 8

7 9

8 11

7 2

6 1

2 4

14 10

31 数据结构 a d c b e f g h i

4 8

7 9

8 11

7 2

6 1

2 4

14 10 Prim算法的改进 ? 前面 Prim 算法的缺点是可能把没价值的边存入队列 cands 空间复杂性达到 O(|E|)(通常大于 O(|V|)) 在实际中加入队列的边可能不同,可以做些试验研究有关的情况 ? 如果算法里能只记录连接 U 和V-U 的边,那么在整个计算中,需要保 存的边不超过 |V| 条,就可以把空间开销降到 O(|V|) .为保证效率, 要求算法中使用的数据结构能有效支持下面操作 C 获得这些边中的最短边.显然,采用堆结构,复杂性为 O(log|V|) C 发现了到 V-U 中顶点的更短边时高效更新.要求在 O(log|V|) 时间内从结 点找到堆里的元素,修改原有的权值并恢复堆结构 ? 也就是说,需要一种类似优先队列的结构,支持(以元素个数为 n): C O(n) 的建堆,O(log n) 的getmin 操作(堆支持这些) C 从某种 index(这里是顶点标号)出发的 O(1) 的weight(ind),从id 和新 权值出发的 O(log n) 的减权值操作 dec_weight(ind, w)

32 数据结构 Prim算法的改进 ? 称这种结构为 可减权堆 ,设定义的类是 DecPrioHeap, 支持: C DecPrioHeap(list),其中 list 的项形式为 (w, index, other),这个类 的对象 decheap 是以 list 的项为元素以 w 为权的小顶堆 C decheap.getmin() 弹出堆中最小元并恢复堆,O(log n) 复杂性 C decheap.weight(ind) 得到 ind 为index 的元素权值,O(1) C decheap.dec_weight(ind, w, other) 在w小于 decheap 里具有 ind 的 元素的权值时,将该元素改为 (w, ind, other) 并恢复堆的结构,复 杂性为 O(log n) C decheap.is_empty() 在decheap 为空时返回 True 有了这个类,改造 Prim 算法的工作就可以完成 ? 这种结构是可以实现的,但有点复杂

33 数据结构 Prim算法的改进 ? 修改后的算法: def Prim(graph): vnum = graph.vertex_num() wv_seq = [[graph.get_edge(0, v), v, 0] for v in range(vnum)] connects = DecPrioHeap(wv_seq) # 最近连接的顶点堆,|V| 个元素 mst = [None]*vnum while not connects.is_empty(): w, mv, u = connects.getmin() # 取得最近顶点和连接边 if w == infinity: break # 最近顶点已不连通,说明该图没有生成树 mst[mv] = ((u, mv), w) # 这就是新的 MST 边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(max(|V| log |V|, |E| log |V|))

34 数据结构 构造最小生成树的Kruskal算法 ? 设G=(V,E)是网络,最小生成树的初始状态为只 有n个顶点而无边的非连通图T=(V,φ),T中每个 顶点自成为一个连通分量. ? 将集合E中的边按权递增顺序排列,从小到大依次 选择顶点分别在两个连通分量中的边加入图T,则 原来的两个连通分量由于该边的连接而成为一个 连通分量. ? 依次类推,直到T中所有顶点都在同一个连通分量 上为止,该连通........