623最小生成树 有n个乡村,眢村间道路的长度是已知的,如何敷设光 缆线路使n个乡村连通且总长度最短 显然,这要求在已知边长度的网路图中找最小生成树 最小生成树的算法 Kruskal算法:将图中所有边按权值从小到大排列,依次 选所剩最小的边加入边集T,只要不和前面加入的边构 成回路,直到T中有n-1条边,则T是最小生成树 Kruskal算法基于下述定理 定理3指定图中任一点v,如果v是距v最近的相邻节点, 则关联边e;必在某个最小生成树中。 推论将网路中的节点划分为两个不相交的集合吃和V2, V2=VV,则V和V2权值最小的边必定在某个最小生 成树中
11 6.2.3 最小生成树 • 有n 个乡村，各村间道路的长度是已知的，如何敷设光 缆线路使 n 个乡村连通且总长度最短 • 显然，这要求在已知边长度的网路图中找最小生成树 最小生成树的算法： • Kruskal 算法：将图中所有边按权值从小到大排列，依次 选所剩最小的边加入边集 T，只要不和前面加入的边构 成回路，直到 T 中有 n−1 条边，则 T 是最小生成树 • Kruskal 算法基于下述定理 定理 3 指定图中任一点vi，如果 vj 是距 vi 最近的相邻节点， 则关联边 eij 必在某个最小生成树中。 推论 将网路中的节点划分为两个不相交的集合V1和V2， V2=V−V1，则V1和V2间权值最小的边必定在某个最小生 成树中
623最小生成树 最小生成树不一定唯一 定理3推论是一个构造性定理,它指示了找最小生成树 的有效算法 Prim算法:不需要对边权排序,即可以直接在网路图上 操作,也可以在边权矩阵上操作,后者适合计算机运算 边权短阵上的Prim算法 根据网路写出边权矩阵,两点间若没有边,则用∞表示 2、从v1开始标记,在第一行打√,划去第一列; 3、从所有打V的行中找出尚未划掉的最小元素,对该元素画圈 划掉该元素所在列,与该列数对应的行打V; 4、若所有列都划掉,则已找到最小生成树(所有画圈元素所对应 的边):否则,返回第3步。 该算法中,打√行对应的节点在中,未划去的列在中
12 6.2.3 最小生成树 • 最小生成树不一定唯一 • 定理 3 推论是一个构造性定理，它指示了找最小生成树 的有效算法 • Prim 算法：不需要对边权排序，即可以直接在网路图上 操作，也可以在边权矩阵上操作，后者适合计算机运算 边权矩阵上的 Prim 算法： 1、根据网路写出边权矩阵，两点间若没有边，则用表示； 2、从 v1 开始标记，在第一行打 ，划去第一列； 3、从所有打 的行中找出尚未划掉的最小元素，对该元素画圈， 划掉该元素所在列，与该列数对应的行打 ； 4、若所有列都划掉，则已找到最小生成树(所有画圈元素所对应 的边)；否则，返回第 3 步。 • 该算法中，打 行对应的节点在 V1中，未划去的列在 V2中
623最小生成树 16111017 √o Q5中19.5 7 √|1695 7∞1 √n如h (⑦ 9.5 10 √|i719.51279 Prim算法是多项式算法 Prim算法可以求最大生成树 网路的边权可以有多种解释,如效率 次数受限的最小生成树尚无有效算法 最小 Steiner树尚无有效算法
13 6.2.3 最小生成树 − − − − − − 17 19.5 12 7 9 10 8 9 11 7 8 7 16 9.5 7 12 10 9.5 19.5 10 16 11 10 17 • Prim算法是多项式算法 • Prim算法可以求最大生成树 • 网路的边权可以有多种解释，如效率 • 次数受限的最小生成树—尚无有效算法 • 最小 Steiner 树—尚无有效算法 v1 v 4 v 6 v 3 v5 v2 10 10 8 11 7 7 16 9.5 17 12 9 19.5 v1 v 4 v 6 v 3 v5 v2 10 8 7 7 9.5
6.3最短路问题 631狄克斯特拉算法( Dijkstra algorithm1959) 计算两节点之间或一个节点到所有节点之间的最短路 令表示v到v的直接距离(两点之间有边),若两点之间 没有边,则令=,若两点之间是有向边,则4n=∞; 令dn=0,s表示始点,t表示终点 0、令始点T=0,并用框住,所有其它节点临时标记T= 1、从v岀发,对其相邻节点v进行临时标记,有T=dn 2、在所有临时标记中找出最小者,并用框住,设其为v。若 此时全部节点都永久标记,算法结束;否则到下一步; 3、从新的永久标记节点v出发,对其相邻的临时标记节点进行 再标记,设v为其相邻节点,则Tn-min{T,Tr+ln2},返回 第2步
14 6.3 最短路问题 6.3.1 狄克斯特拉算法 (Dijkstra algorithm, 1959) • 计算两节点之间或一个节点到所有节点之间的最短路 令 dij 表示 vi 到 vj 的直接距离(两点之间有边)，若两点之间 没有边，则令 dij = ，若两点之间是有向边，则 dji = ； 令 dii = 0，s 表示始点，t 表示终点 0、令始点Ts=0，并用 框住，所有其它节点临时标记 Tj= ； 1、从 vs 出发，对其相邻节点 vj1 进行临时标记，有 Tj1=ds,j1 ； 2、在所有临时标记中找出最小者，并用 框住，设其为 vr 。若 此时全部节点都永久标记，算法结束；否则到下一步； 3、从新的永久标记节点 vr 出发，对其相邻的临时标记节点进行 再标记，设 vj2 为其相邻节点，则 Tj2=min{Tj2 , Tr+dr,j2 }，返回 第2步
例1狄克斯特拉算法 8 20 9 15 8 30 4) 8
15 例1 狄克斯特拉算法 2 s 5 t 6 3 4 10 7 4 9 1 8 8 15 2 20 2 30 0 8 15 10 12 15 11 31 13 2 s 5 t 6 3 4 10 7 4 9 1 8 8 15 2 20 2 30