写出求解过程中堆、并查集和最小生成树的变化。 8-18利用 Dijkstra算法的思想,设计一个求最小生成树的算法 8-19以右图为例,按 Dijkstra算法计算得到的从顶点 ①到其它各个顶点的最短路径和最短路径长度 5 OC 8-20在以下假设下,重写 Dijkstra算法 1)用邻接表表示带权有向图G,其中每个边结点有3个域:邻接顶点 vertex,边上 的权值 length和边链表的链接指针lmke (2)用集合T=I(G)-S代替S(已找到最短路径的顶点集合),利用链表来表示集合T 试比较新算法与原来的算法,计算时间是快了还是慢了,给出定量的比较。 8-22使用 Floyd算法计算8-19题所用的带权有向图的各对顶点之间的最短路径。 23下面是基于元素0到4的一些优先关系的集合,试问它们是否定义了一个偏序关 ?为什么? 0<1;1<3;1<2;2<3;2<4;4<0 8-24试证明:对于一个无向图G=(VE),若G中各顶点的度均大于或等于2,则G中 必有回路 【解答】反证法:对于一个无向图G=(V,E),若G中各顶点的度均大于或等于2,则 G中没有回路。此时从某一个顶点出发,应能按拓扑有序的顺序遍历图中所有顶点。但 当遍历到该顶点的另一邻接顶点时,又可能回到该顶点,没有回路的假设不成立。 8-25设有一个有向图存储在邻接表中。试设计一个 算法,按深度优先搜索策略对其进行拓扑排序。并 以右图为例检验你的算法的正确性 【解答】 (1)定义邻接表结构 const n=.. (顶点个数} type pointer= t node node= record adi: integer; 邻接顶点号} cost: real 边上的权值}写出求解过程中堆、并查集和最小生成树的变化。 8-18 利用 Dijkstra 算法的思想，设计一个求最小生成树的算法。 8-19 以右图为例，按 Dijkstra 算法计算得到的从顶点 ①到其它各个顶点的最短路径和最短路径长度。 8-20 在以下假设下，重写 Dijkstra 算法： (1) 用邻接表表示带权有向图 G，其中每个边结点有 3 个域：邻接顶点 vertex，边上 的权值 length 和边链表的链接指针 link。 (2)用集合 T = V(G) - S 代替 S(已找到最短路径的顶点集合)，利用链表来表示集合 T。 试比较新算法与原来的算法，计算时间是快了还是慢了，给出定量的比较。 8-22使用 Floyd 算法计算 8-19 题所用的带权有向图的各对顶点之间的最短路径。 8-23 下面是基于元素 0 到 4 的一些优先关系的集合，试问它们是否定义了一个偏序关 系？为什么？ 0<1;1<3; 1<2;2<3;2<4; 4<0 8-24 试证明：对于一个无向图 G = (V, E)，若 G 中各顶点的度均大于或等于 2，则 G 中 必有回路。 【解答】反证法：对于一个无向图 G=（V，E），若 G 中各顶点的度均大于或等于 2，则 G 中没有回路。此时从某一个顶点出发，应能按拓扑有序的顺序遍历图中所有顶点。但 当遍历到该顶点的另一邻接顶点时，又可能回到该顶点，没有回路的假设不成立。 8-25 设有一个有向图存储在邻接表中。试设计一个 算法，按深度优先搜索策略对其进行拓扑排序。并 以右图为例检验你的算法的正确性。 【解答】 (1) 定义邻接表结构 const n = ……; {顶点个数} type pointer = ↑node node = record adj : integer; {邻接顶点号} cost : real; {边上的权值} link : pointer;