于稀疏图。如果像Prim算法那样,通过直接比较D数组元素,确定代价最小的边就需要总 时间O(n2);取出最短特殊路径长度最小的顶点后,修改最短特殊路径长度共需要时间Oe), 因此共需要花费O(n2)的时间,这种方法适合于稠密图 (6)求所有顶点对之间最短路径的 Floyd算法 Floyd算法用相邻矩阵ad来表示带权有向图,该算法的基本思想是:初始化adj0为相 邻矩阵adj,在矩阵adj上做n次迭代,递归地产生一个矩阵序列adj"),…,adj,…,ad"。 其中经过第k次迭代,ad伍,j的值等于从顶点v到顶点v路径上所经过的顶点序号不大 于k的最短路径长度。由于进行第k次迭代时已求得矩阵ad,那么从顶点v到顶点y 中间顶点的序号不大于k的最短路径有两种情况:一种是中间不经过顶点v,那么此时就 有adj[i,j=adki,j:另一种是中间经过顶点v,此时ady[,j<ad[i,j,那么 这条由顶点v经过v到顶点v的中间顶点序号不大于k的最短路径由两段组成:一段是从 顶点v到顶点v的中间顶点序号不大于k-1的最短路径,另一段是从顶点v到顶点v的中 间顶点序号不大于k1的最短路径,路径长度应为这两段长度之和,用下面的公式计算:ad [,j=adj{i,k]+adjk"lk,jl。综合这两种情况有 adj[i,j]=min( adj -[i, j], adjk-[i, k]+adjk-lk,jl 这样ad",j等于从顶点v到顶点v中间顶点序号不大于n的最短路径长度,也就是 所要求的从顶点v到顶点v的最短路径。 (7) Kruskal算法 Kruskal算法的构造思想是:给定含有n个顶点和e条边的无向连通带权图G=<V,E> 首先将G中的n个顶点看成是独立的n个连通分量,这时的状态是有n个顶点而无边的森 林,可以记为T=<V,{}>。然后在E中选择代价最小的边,如果该边依附于两个不同的连 通分支,那么将这条边加入到T中,否则舍去这条边而选择下一条代价最小的边。依此类 推,直到T中所有顶点都在同一个连通分量中为止,此时就得到图G的一棵最小生成树。 在 Kruskal算法中,把连通分量中的顶点作为集合元素,采用并查集的Find算法确定边 的两个关联顶点所属的连通分支,采用Unon算法合并两个连通分量。 在 Kruskal算法中,需要按边权值递增的顺序依次查看边,可以把按边的权值组织优先 队列,权值越小,优先级就越高。用最小堆来实现这个优先队列。 6.课后练习和实习4 于稀疏图。如果像 Prim 算法那样，通过直接比较 D 数组元素，确定代价最小的边就需要总 时间 O(n2 )；取出最短特殊路径长度最小的顶点后，修改最短特殊路径长度共需要时间 O(e)， 因此共需要花费 O( n 2 )的时间，这种方法适合于稠密图。 （6）求所有顶点对之间最短路径的 Floyd 算法 Floyd 算法用相邻矩阵 adj 来表示带权有向图，该算法的基本思想是：初始化 adj(0)为相 邻矩阵 adj，在矩阵 adj(0)上做 n 次迭代，递归地产生一个矩阵序列 adj(1)，„，adj(k)，„，adj(n)。 其中经过第 k 次迭代，adj(k)[i，j]的值等于从顶点 vi到顶点 vj 路径上所经过的顶点序号不大 于 k 的最短路径长度。由于进行第 k 次迭代时已求得矩阵 adj(k-1)，那么从顶点 vi 到顶点 vj 中间顶点的序号不大于 k 的最短路径有两种情况：一种是中间不经过顶点 vk，那么此时就 有 adj(k) [i，j] = adj(k-1)[i，j]；另一种是中间经过顶点 vk，此时 adj(k) [i，j] < adj(k-1)[i，j]，那么 这条由顶点 vi经过 vk 到顶点 vj 的中间顶点序号不大于 k 的最短路径由两段组成：一段是从 顶点 vi到顶点 vk 的中间顶点序号不大于 k-1 的最短路径，另一段是从顶点 vk到顶点 vj的中 间顶点序号不大于 k-1 的最短路径，路径长度应为这两段长度之和，用下面的公式计算：adj(k) [i，j] = adj(k-1)[i，k] + adj(k-1)[k，j]。综合这两种情况有 adj(k) [i，j] = min { adj(k-1)[i，j]，adj(k-1)[i，k] + adj(k-1)[k，j] } 这样 adj(n)[i，j]等于从顶点 vi到顶点 vj 中间顶点序号不大于 n 的最短路径长度，也就是 所要求的从顶点 vi到顶点 vj 的最短路径。 （7）Kruskal 算法 Kruskal 算法的构造思想是：给定含有 n 个顶点和 e 条边的无向连通带权图 G = <V，E>， 首先将 G 中的 n 个顶点看成是独立的 n 个连通分量，这时的状态是有 n 个顶点而无边的森 林，可以记为 T = <V，{}>。然后在 E 中选择代价最小的边，如果该边依附于两个不同的连 通分支，那么将这条边加入到 T 中，否则舍去这条边而选择下一条代价最小的边。依此类 推，直到 T 中所有顶点都在同一个连通分量中为止，此时就得到图 G 的一棵最小生成树。 在 Kruskal 算法中，把连通分量中的顶点作为集合元素，采用并查集的 Find 算法确定边 的两个关联顶点所属的连通分支，采用 Union 算法合并两个连通分量。 在 Kruskal 算法中，需要按边权值递增的顺序依次查看边，可以把按边的权值组织优先 队列，权值越小，优先级就越高。用最小堆来实现这个优先队列。 6．课后练习和实习