PDF《数据结构》

14 6 v2

6 v4

18 v3 v0

10 v1

21 11

5 v5

19 33

14 6 v2

6 v4

18 v3 v0

10 v1

21 11

5 v5

19 33

14 6 v2

6 v4

18 v3

15 数据结构 算法思想 ? 生成树用类似构造 DFS 生成树的数据表示,用vnum 个元素(vnum 为顶点数)的表 mst 保存最小生成树的边,mst[1] = ((1, 2), 10) 表示顶 点1到2的边在 mst 且权值为 10,mst[i] = None 表示 i 不属于 U ? 用一个优先队列 cands 记录候选的最短边,元素形式为 (w, i, j),表示 从顶点 i 到j的边为候选,其权值为 w ? 算法过程: C 初始把 (0, 0, 0) 放入优先队列,表示从顶点

0 到自身的长

0 的边 C 循环的第一次迭代将把顶点

0 记入最小生成树顶点集 U,方法是设mst[0] = (0, 0, 0).还会把顶点

0 到其余顶点的边按权值存入优先队列 cands,表 示待考察的候选边集合 C 执行中反复选择 cands 里记录的最短边 (u, v) .如确定它是连接 U 中顶点 与V-U 顶点的边(发现 v 是V-U 的顶点),就把这条边及其权记入 mst[v],并把 v 的出边存入 cands;

否则直接丢掉 C 结束时 mst 中是最小生成树的 n 条边(包括 (0, 0) 边以方便实现)

16 数据结构 数组mst的计算 ? ①.n=6,只有顶点v0在最小生成树中. mst[0] = (0,0,0) cands=[(0,1,10), (0,4,19), (0,5,21)] ? ②.在cands中取出权值最小的边(0,1,10), 将顶点v1及边(v0, v1)加入最小生成树,并将 v1的出边加入cands. mst[1] = (0,1,10) cands=[(1,2,5), (1,3,6), (1,5,11), (0,4,19), (0,5,21)]

17 数据结构 ? ③.在cands中取出权值最小的边(1,2,5),将顶点v2 及边(v1, v2)加入最小生成树,并将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),将顶点v3 及边(v1, v3)加入最小生成树,并将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)] 数组mst和cands的调整1

18 数据结构 数组mst和cands的调整2 ? ⑤. 边(v2, v3)不在生成树中,在cands中取出下一 条权值最小的边为(1,5,11),将顶点v5及边(v1, v5)加 入最小生成树,并将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)]

19 数据结构 数组mst和cands的调整3 ? ⑥.边(v3, v5)不在生成树中,在cands中取出下一条 权值最小的边为(3,4,18),将顶点v4及边(v3, v4)加入 最小生成树,并将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中所有的边都不在最小生成树中,直接丢掉 即可.

20 数据结构 Prim算法

21 数据结构 Prim算法的时间代价 ? 时间复杂性:初始化部分是 O(|V|),算法时间主要用在选 择最小生成树的边.循环次数与考察和加入优先队列的元 素个数有关,也与顶点个数 |V| 有关.考虑到每条边至多 进入弹出队列一次,这个角度的时间开销是 O(|E| log |E|);

构造 O(|V|) 条边的时间开销不低于 O(|V|).一般而言前 者大于后者,所以时间复杂性为 O(|E| log |E|) ? 空间复杂度:算法里用了一个表 mst 和一个优先队列,大 小是 O(|V|) 和O(|E|).对连通图一般有 |E| >

|V|,由此 空间复杂度是 O(|E|) ? 注意:如果图用邻接矩阵表示,提取一个顶点的邻接边就 是O(n) 操作,整个算法的时间开销将为 O(max(|V|2, |E| log |E|))

22 数据结构

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

4 8

7 9

8 11

7 2

6 1

2 4

14 10