数据结构与算法“图”教学设计 北京大学信息科学技术学院王腾蛟 1.图在课程中的定位和前测知识点 图是比线性表、数和集合更一般、更复杂的数据结构,在线性结构中,每个数据元素只 有一个直接前驱和一个直接后继结点。在树结构中,数据元素之间有着明显的层次关系,同 层的每个数据元素可以与它下一层的零个或多个元素相关,但只能与上一层中的一个元素相 关。集合结构中,数据元素间除了同属于一个集合的联系之外没有其他关系。然而在图结构 中,数据元素之间的关系是任意的,每个元素都可以和任何其他元素相关。 图这一章阐述了图的基本概念以及图的存储结构:相邻矩阵表示法、邻接表表示法,并 讨论了图的深度优先周游和广度优先周游。此外提出了最小支撑树的概念,并讨论了生成最 小支撑树的Prim算法和 Kruskal算法。 前测知识点要求如下,可以根据需要给学生补充: 图的顶点与边的概念。 2.学习目标 (1)理解并掌握图的基本概念。 (2)能写出图的抽象数据类型。 (3)理解图的各种存储结构,并能设计基于图的存储结构的算法。 4)重点掌握图的周游、最短路径和最小支撑树的相关算法 (5)了解图的相关知识。 3.知识点和学时分配 理论授课4学时,建议安排实验8学时。 各知识点建议授课时间如下: 图的基本概念0.5小时 图的存储结构 1小时 图的周游 1小时 最短路径问题 0.5小时
1 数据结构与算法“图”教学设计 北京大学信息科学技术学院 王腾蛟 1. 图在课程中的定位和前测知识点 图是比线性表、数和集合更一般、更复杂的数据结构，在线性结构中，每个数据元素只 有一个直接前驱和一个直接后继结点。在树结构中，数据元素之间有着明显的层次关系，同 层的每个数据元素可以与它下一层的零个或多个元素相关，但只能与上一层中的一个元素相 关。集合结构中，数据元素间除了同属于一个集合的联系之外没有其他关系。然而在图结构 中，数据元素之间的关系是任意的，每个元素都可以和任何其他元素相关。 图这一章阐述了图的基本概念以及图的存储结构：相邻矩阵表示法、邻接表表示法，并 讨论了图的深度优先周游和广度优先周游。此外提出了最小支撑树的概念，并讨论了生成最 小支撑树的 Prim 算法和 Kruskal 算法。 前测知识点要求如下，可以根据需要给学生补充： 图的顶点与边的概念。 2．学习目标 （1） 理解并掌握图的基本概念。 （2） 能写出图的抽象数据类型。 （3） 理解图的各种存储结构，并能设计基于图的存储结构的算法。 （4） 重点掌握图的周游、最短路径和最小支撑树的相关算法。 （5） 了解图的相关知识。 3. 知识点和学时分配 理论授课 4 学时，建议安排实验 8 学时。 各知识点建议授课时间如下： 图的基本概念 0.5 小时 图的存储结构 1 小时 图的周游 1 小时 最短路径问题 0.5 小时
最小支撑树 0.5小时 图知识点总结0.5小时 4.重点和难点 (1)图的存储结构以及各种存储结构的优缺点 (2)图的周游算法。 (3)解决图的最短路径问题的各种算法。 (4)图的最小支撑树的两种典型算法:Pim算法和 Kruskal算法 5.授课提示 采用灵活的教学方式,通过提出问题、分析问题、解决问题这样的基本流程,加深学生 对重难点知识的理解,并培养其创新意识和创新能力 下面是图这一章的重点和难点内容的讲授注意事项 (1)邻接表、十字链表 邻接表 adjacency list)表示法是一种链式存储结构,由一个顺序存储的顶点表和n个链 接存储的边表组成。顶点表目有两个域:顶点数据域和指向此顶点边表指针域。边表把依附 于同一个顶点v的边(即相邻矩阵中同一行的非0元素)组织成一个单链表。边表中的每 一个表目都代表一条边,由两个主要的域组成:与顶点v1邻接的另一顶点的序号、指向边 表中下一个边表目的指针。 十字链表( Orthogonal list)是有向图的另一种链式存储结构,可以看成是邻接表和逆 邻接表的结合。表中对应于有向图的每一条弧有一个表目,共有5个域:头 headvex)和尾 ( tailvex)分别表示弧头(终点)和弧尾(始点)顶点序号; tailnextarc链接指针指向下一条顶 点以 tailvex为弧尾的弧; headnextarc指针指向下一条以顶点 headvex为弧头的弧;此外还 有一个表示弧权值等信息的 info域。顶点表目由3个域组成:data域存放顶点的相关信息 firstinarc链接指针指向第一条以该顶点为终点的弧; firstoutarc链接指针指向第一条以该顶 点为始点的弧。所有的顶点也可以放在顺序存储结构中 图的存储结构这一部分,需要多用图片进行展示。 (2)深度优先周游 深度优先周游方法的特点是尽可能先对纵深方向进行搜索。 对于给定的图G=<V,E,初始状态是V中的所有顶点都未被访问。首先选取一个顶 点开始搜索。设v∈V是源点,访问顶点vo并标记为Ⅴ SITED,然后访问v邻接到的未被 访问过的顶点ⅵ1,再从v出发递归地按照深度优先的方式周游。当遇到一个所有邻接顶点 都被访问过了的顶点w时,则回到己访问顶点序列中最后一个拥有未被访问的相邻顶点的 顶点u,再从u出发递归地按照深度优先的方式周游。重复上述过程直至从v0出发的所有边 都已检测过为止,此时,图中所有由源点有路径可达的顶点都己被访问过。若图G是连通 图,则周游过程结束;否则选择一个尚未访问的顶点作为新的源点进行深度优先搜索,直至
2 最小支撑树 0.5 小时 图知识点总结 0.5 小时 4．重点和难点 （1） 图的存储结构以及各种存储结构的优缺点。 （2） 图的周游算法。 （3） 解决图的最短路径问题的各种算法。 （4） 图的最小支撑树的两种典型算法：Prim 算法和 Kruskal 算法。 5．授课提示 采用灵活的教学方式，通过提出问题、分析问题、解决问题这样的基本流程，加深学生 对重难点知识的理解，并培养其创新意识和创新能力。 下面是图这一章的重点和难点内容的讲授注意事项。 （1）邻接表、十字链表 邻接表(adjacency list)表示法是一种链式存储结构，由一个顺序存储的顶点表和 n 个链 接存储的边表组成。顶点表目有两个域：顶点数据域和指向此顶点边表指针域。边表把依附 于同一个顶点 vi 的边（即相邻矩阵中同一行的非 0 元素）组织成一个单链表。边表中的每 一个表目都代表一条边，由两个主要的域组成：与顶点 vi 邻接的另一顶点的序号、指向边 表中下一个边表目的指针。 十字链表（Orthogonal List）是有向图的另一种链式存储结构，可以看成是邻接表和逆 邻接表的结合。表中对应于有向图的每一条弧有一个表目，共有 5 个域：头(headvex)和尾 (tailvex)分别表示弧头（终点）和弧尾（始点）顶点序号；tailnextarc 链接指针指向下一条顶 点以 tailvex 为弧尾的弧；headnextarc 指针指向下一条以顶点 headvex 为弧头的弧；此外还 有一个表示弧权值等信息的 info 域。顶点表目由 3 个域组成：data 域存放顶点的相关信息； firstinarc 链接指针指向第一条以该顶点为终点的弧；firstoutarc 链接指针指向第一条以该顶 点为始点的弧。所有的顶点也可以放在顺序存储结构中。 图的存储结构这一部分，需要多用图片进行展示。 （2）深度优先周游 深度优先周游方法的特点是尽可能先对纵深方向进行搜索。 对于给定的图 G = ，初始状态是 V 中的所有顶点都未被访问。首先选取一个顶 点开始搜索。设 v0∈V 是源点，访问顶点 v0 并标记为 VISITED，然后访问 v0邻接到的未被 访问过的顶点 v1，再从 v1 出发递归地按照深度优先的方式周游。当遇到一个所有邻接顶点 都被访问过了的顶点 w 时，则回到已访问顶点序列中最后一个拥有未被访问的相邻顶点的 顶点 u，再从 u 出发递归地按照深度优先的方式周游。重复上述过程直至从 v0 出发的所有边 都已检测过为止，此时，图中所有由源点有路径可达的顶点都已被访问过。若图 G 是连通 图，则周游过程结束；否则选择一个尚未访问的顶点作为新的源点进行深度优先搜索，直至
图中所有顶点均被访问。事实上,深度优先搜索的结果是沿着图的某一分支搜索,直到它的 末端,然后回溯,沿着另一分支进行同样的搜索,依此类推。 (3)广度优先周游 广度优先周游的过程是:从图中的某个顶点ⅴ出发,访问并标记了顶点ⅴ之后,横向搜 索v的所有邻接点u1,u2,…,u。在依次访问v的各个未被访问的邻接点之后,再从这些 邻接点出发,依次访问与它们邻接的所有未曾访问过的顶点。重复上述过程直至图中所有与 源点ⅴ有路径相通的顶点都被访问为止。若G是连通图,则周游完成;否则,在图G中选 一个尚未访问的顶点作为新源点继续广度优先搜索。广度优先搜索是个非递归的过程,而深 度优先搜索是个递归的过程 (4)拓扑排序 有向图拓扑排序的步骤 (1)从有向图中选出一个没有前驱(入度为0)的顶点并输出它。 (2)删除图中该顶点和所有以它为起点的弧 不断重复上述两个步骤,会出现两种情形:要么有向图中顶点全部被输出,要么当前图 中不存在没有前驱的顶点。当图中的顶点全部输出时,就完成了有向无环图的拓扑排序;当 图中还有顶点没有输出时,说明有向图中含有环。可见拓扑排序可以检查有向图是否存在环。 (5)求所有顶点对之间最短路径的 Dijkstra算法 Dijkstra算法的基本思想是:把图的顶点集合化分成两个集合S和VS。第一个集合S 表示最短距离已经确定的顶点集,即一个顶点如果属于集合S当且仅当从源点s到该顶点的 最短路径已知。其余的顶点放在另一个集合VS中。初始时,集合S只包含源点,即S={s} 这时只有源点到自己的最短距离是已知的。设ⅴ是V中的某个顶点,把从源点s到顶点v 且中间只经过集合S中顶点的路径称为从源点到ⅴ的特殊路径,并用数组D来记录当前所 找到的从源点s到每个顶点的最短特殊路径长度。D的初始状态为:如果从源点s到顶点ⅴ 有弧则DⅣv]记为弧的权值;否则将DⅣ置为无穷大。 Dijkstra算法每次从尚未确定最短路径 长度的集合VS中取出一个最短特殊路径长度最小的顶点u,将u加入集合S,同时修改数 组D中由s可达的最短路径长度:若加进u做中间顶点,使得v的最短特殊路径长度变短 则修改v;的距离值(即当Du+W[u,v]<Dv时,令DIv]=Du]+W[uv)。然后重复上 述操作,一旦S包含了所有Ⅴ中的顶点,D中各顶点的距离值就记录了从源点s到该顶点 的最短路径长度。 对于n个顶点e条边的图,图中的任何一条边都可能在最短路径中出现,因此最短路径 算法对每条边至少都要检查一次。 Dijkstra算法采用最小堆来选择权值最小的边,那么每次 改变最短特殊路径长度时需要对堆进行一次重排,此时的时间复杂度为O(n+e)loge),适合
3 图中所有顶点均被访问。事实上，深度优先搜索的结果是沿着图的某一分支搜索，直到它的 末端，然后回溯，沿着另一分支进行同样的搜索，依此类推。 （3）广度优先周游 广度优先周游的过程是：从图中的某个顶点 v 出发，访问并标记了顶点 v 之后，横向搜 索 v 的所有邻接点 u1，u2，„，ut。在依次访问 v 的各个未被访问的邻接点之后，再从这些 邻接点出发，依次访问与它们邻接的所有未曾访问过的顶点。重复上述过程直至图中所有与 源点 v 有路径相通的顶点都被访问为止。若 G 是连通图，则周游完成；否则，在图 G 中选 一个尚未访问的顶点作为新源点继续广度优先搜索。广度优先搜索是个非递归的过程，而深 度优先搜索是个递归的过程。 （4）拓扑排序 有向图拓扑排序的步骤： (1) 从有向图中选出一个没有前驱（入度为 0）的顶点并输出它。 (2) 删除图中该顶点和所有以它为起点的弧。 不断重复上述两个步骤，会出现两种情形：要么有向图中顶点全部被输出，要么当前图 中不存在没有前驱的顶点。当图中的顶点全部输出时，就完成了有向无环图的拓扑排序；当 图中还有顶点没有输出时，说明有向图中含有环。可见拓扑排序可以检查有向图是否存在环。 （5）求所有顶点对之间最短路径的 Dijkstra 算法 Dijkstra 算法的基本思想是：把图的顶点集合化分成两个集合 S 和 V-S。第一个集合 S 表示最短距离已经确定的顶点集，即一个顶点如果属于集合 S 当且仅当从源点 s 到该顶点的 最短路径已知。其余的顶点放在另一个集合 V-S 中。初始时，集合 S 只包含源点，即 S = {s}， 这时只有源点到自己的最短距离是已知的。设 v 是 V 中的某个顶点，把从源点 s 到顶点 v 且中间只经过集合 S 中顶点的路径称为从源点到 v 的特殊路径，并用数组 D 来记录当前所 找到的从源点 s 到每个顶点的最短特殊路径长度。D 的初始状态为：如果从源点 s 到顶点 v 有弧则 D[v]记为弧的权值；否则将 D[v]置为无穷大。Dijkstra 算法每次从尚未确定最短路径 长度的集合 V-S 中取出一个最短特殊路径长度最小的顶点 u，将 u 加入集合 S，同时修改数 组 D 中由 s 可达的最短路径长度：若加进 u 做中间顶点，使得 vi的最短特殊路径长度变短， 则修改 vi的距离值（即当 D[u] + W[u, vi] < D[vi]时，令 D[vi] = D[u] + W[u, vi]）。然后重复上 述操作，一旦 S 包含了所有 V 中的顶点，D 中各顶点的距离值就记录了从源点 s 到该顶点 的最短路径长度。 对于 n 个顶点 e 条边的图，图中的任何一条边都可能在最短路径中出现，因此最短路径 算法对每条边至少都要检查一次。Dijkstra 算法采用最小堆来选择权值最小的边，那么每次 改变最短特殊路径长度时需要对堆进行一次重排，此时的时间复杂度为 O((n + e)loge)，适合
于稀疏图。如果像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 首先将G中的n个顶点看成是独立的n个连通分量,这时的状态是有n个顶点而无边的森 林,可以记为T=。然后在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] ， 首先将 G 中的 n 个顶点看成是独立的 n 个连通分量，这时的状态是有 n 个顶点而无边的森 林，可以记为 T = 。然后在 E 中选择代价最小的边，如果该边依附于两个不同的连 通分支，那么将这条边加入到 T 中，否则舍去这条边而选择下一条代价最小的边。依此类 推，直到 T 中所有顶点都在同一个连通分量中为止，此时就得到图 G 的一棵最小生成树。 在 Kruskal 算法中，把连通分量中的顶点作为集合元素，采用并查集的 Find 算法确定边 的两个关联顶点所属的连通分支，采用 Union 算法合并两个连通分量。 在 Kruskal 算法中，需要按边权值递增的顺序依次查看边，可以把按边的权值组织优先 队列，权值越小，优先级就越高。用最小堆来实现这个优先队列。 6．课后练习和实习
将书本上的理论知识与最前沿的技术知识融为一体,设计验证型、探索型、应用型的 实习题和上机题,帮助同学更好的理解书本上的基本原理,锻炼学生的思维能力、实践能力。 图这一章可以安排8-10道书面作业,1-2道综合上机实习题。安排一次习题讲评。 例如:算法方面的考察 (1)写出一个算法确定一个有n个顶点e条边的图(有向图或者无向图)是否包含回 路,所设计的算法的时间代价应该是O(n+e) (2)设计算法找图(有向图或无向图)的所有连通分量(对于有向图则是强连通分 量)。提示:第一个连通分量的所有顶点使用第一分量的标记,第二个连通分量的所有 顶点使用第二分量的标记,依此类推。 (3)设计一个程序,输入一个图(有向图或者是无向图)G=以及一对顶点v v∈V,输出的结果是:如果从v到v存在一条简单路径,则输出从v到v所有简单路 径:如果不存在,则输出空 .教学案例 构造最小生成树的Prim算法 设G=是一个联通的带权图,其中V是顶点的集合,E是边的集合,TE为最小 生成树的边的集合。则Prim算法通过以下步骤得到最小生成树 (1)初始状态:U={uo},TE={}。其中υ是顶点集合Ⅴ中的某一个顶点 (2)在所有u∈U,v∈VU的边(uv)∈E中找一条权值最小的边(u,vo),将这条边加进 集合TE中,同时将此边的另一顶点v并入U。这一步骤的作用是在边集E里找一条两个 顶点分别在集合U和VU中且权值最小的边,把这条边添加到边集TE中,并把这条边上 不在U中的那个顶点加入到U中。 (3)如果U=V,则算法结束:否则重复步骤2。 算法结束时,TE中包含了G中的n-1条边。经过上述步骤选取到的所有边恰好就构成 了图G的一棵最小生成树 例如,对于左图中的带权图,按照Prim算法选取边的过程如右图所示
5 将书本上的理论知识与最前沿的技术知识融为一体，设计验证型、探索型、应用型的 实习题和上机题，帮助同学更好的理解书本上的基本原理，锻炼学生的思维能力、实践能力。 图这一章可以安排 8-10 道书面作业，1-2 道综合上机实习题。安排一次习题讲评。 例如：算法方面的考察 （1） 写出一个算法确定一个有 n 个顶点 e 条边的图（有向图或者无向图）是否包含回 路，所设计的算法的时间代价应该是 O(n+e)。 （2） 设计算法找图（有向图或无向图）的所有连通分量（对于有向图则是强连通分 量）。提示：第一个连通分量的所有顶点使用第一分量的标记，第二个连通分量的所有 顶点使用第二分量的标记，依此类推。 （3） 设计一个程序，输入一个图（有向图或者是无向图）G = 以及一对顶点 vi、 vj∈V，输出的结果是：如果从 vi到 vj 存在一条简单路径，则输出从 vi到 vj 所有简单路 径；如果不存在，则输出空。 7．教学案例 构造最小生成树的 Prim 算法 设 G = 是一个联通的带权图，其中 V 是顶点的集合，E 是边的集合，TE 为最小 生成树的边的集合。则 Prim 算法通过以下步骤得到最小生成树： (1) 初始状态：U = {u0}，TE = {}。其中 u0是顶点集合 V 中的某一个顶点。 (2) 在所有 u∈U，v∈V-U 的边(u,v)∈E 中找一条权值最小的边(u0，v0)，将这条边加进 集合 TE 中，同时将此边的另一顶点 v0 并入 U。这一步骤的作用是在边集 E 里找一条两个 顶点分别在集合 U 和 V-U 中且权值最小的边，把这条边添加到边集 TE 中，并把这条边上 不在 U 中的那个顶点加入到 U 中。 (3) 如果 U = V，则算法结束；否则重复步骤 2。 算法结束时，TE 中包含了 G 中的 n-1 条边。经过上述步骤选取到的所有边恰好就构成 了图 G 的一棵最小生成树。 例 如 ， 对 于 左 图 中 的 带 权 图 ， 按 照 Prim 算 法 选 取 边 的 过 程 如 右 图 所 示
带权图 (d) Prim算法构造左图中带权图的最小生成树的步骤 Prim算法 void prim(raph& G int s,Edge·&MST){∥s是开始顶点,数组MST用于保存最小生成树的边 int MSTtag=0 ∥最小生成树的边计数 MST=new Edge[G Vertices Num0-1]; 为数组MST申请空间 D=new Dist[G VerticesNumoI ∥为数组D申请空间 for(int i=0; ieweight))i .length=e weight; DIGTo Vertex(e)pre =v min Vertex(G D) ∥在D数组中找最小值记为v SITE ∥标记访问过 Edge edge(DIv]pre,DⅣv]ndex,DIv] length);,∥保存边 Add EdgetoMST(edge, MST. MSTtag++,∥将边edge加到MST中
6 v0 v1 v4 v3 v2 v5 v6 1 v0 v1 v4 v3 v2 v5 v6 1 15 v0 v1 v4 v3 v2 v5 v6 1 15 10 v0 v1 v4 v3 v2 v5 v6 1 15 10 2 v0 v1 v4 v3 v2 v5 v6 1 15 10 2 6 v0 v1 v4 v3 v2 v5 v6 1 15 10 2 4 6 (a) (b) (c) (d) (e) (f) Prim 算法构造左图中带权图的最小生成树的步骤 Prim 算法： void Prim(Graph& G, int s, Edge* &MST) { // s 是开始顶点，数组 MST 用于保存最小生成树的边 int MSTtag = 0; // 最小生成树的边计数 MST = new Edge[G.VerticesNum()-1]; // 为数组 MST 申请空间 Dist *D; D = new Dist[G. VerticesNum()]; // 为数组 D 申请空间 for (int i = 0; i e.weight)) { D[G.ToVertex(e)].length = e.weight; D[G.ToVertex(e)].pre = v; } v = minVertex(G, D); // 在 D 数组中找最小值记为 v G.Mark[v] = VISITED; // 标记访问过 Edge edge(D[v].pre, D[v].index, D[v].length); // 保存边 AddEdgetoMST(edge,MST,MSTtag++); // 将边 edge 加到 MST 中 } 带权图 v0 v1 v4 v3 v2 v5 v6 20 1 2 4 6 8 15 12 10
int min Vertex( Graph& Gi Dist*& D)i ∥在Dst数组中找最小值 fori=0; i<GVerticesNum0: 1++) if(MArk[= UNVISITED)i ∥让v为随意一个未访问的顶点 (=0; i<GVerticesNum(; 1++) if((MArk[= UNVISITED)&& (Do<DvD) 保存当前发现的具有最小距离的顶点 可以看出,Pτim算法非常类似于 Dijkstra算法,但Prim算法中的距离值不需要累积, 直接采用离集合最近的边距。Prim算法的时间复杂度也与 Dijkstra算法相同。本算法通过直 接比较D数组元素,确定代价最小的边就需要总时间O(n2):取出权最小的顶点后,修改D 数组共需要时间O(e),因此共需要花费O(n2)的时间,此算法适合于稠密图。 8.总结 本章介绍了图的基本概念、存储结构和图相关的算法。在与图相关的算法中,主要分为 (1)图的周游算法。例如,深度优先搜索、广度优先搜索。 (2)计算最短路径算法。例如,计算单源最短路径算法、计算每对顶点间的最短路径。 (3)计算最小支撑树算法。例如,Pim算法、 Kruskal算法。 在本章介绍的内容中,图的存储结构和图的相关算法是本章的重点。要求掌握图的基本概 念、图的存储结构,并可以写出基于图的存储结构的各种算法,掌握计算最短路径算法和计 算最小支撑树的算法 参考文献 1.张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年6月。—普 通高等教育“十一五”国家级规划教材 2.张铭、赵海燕、王腾蛟、宋国杰、高军,北京大学“数据结构与算法”教学设计,《计 算机教育》2008第20期。获得“英特尔杯2008年全国计算机教育优秀论文评比”一等 奖 3.北京大学《数据结构与算法》精品课程网站(2008年北京市“精品课程”暨国家“精品 课程),http://www.jpk.pku.edu
7 } int minVertex(Graph& G, Dist* & D) { // 在 Dist 数组中找最小值 int i, v; for (i = 0; i < G.VerticesNum(); i++) if (G.Mark[i] == UNVISITED) { v = i; // 让 v 为随意一个未访问的顶点 break; } for (i = 0; i < G.VerticesNum(); i++) if ((G.Mark[i] == UNVISITED) && (D[i] < D[v])) v = i; // 保存当前发现的具有最小距离的顶点 return v; } 可以看出，Prim 算法非常类似于 Dijkstra 算法，但 Prim 算法中的距离值不需要累积， 直接采用离集合最近的边距。Prim 算法的时间复杂度也与 Dijkstra 算法相同。本算法通过直 接比较 D 数组元素，确定代价最小的边就需要总时间 O(n2 )；取出权最小的顶点后，修改 D 数组共需要时间 O(e)，因此共需要花费 O( n 2 )的时间，此算法适合于稠密图。 8．总结 本章介绍了图的基本概念、存储结构和图相关的算法。在与图相关的算法中，主要分为： (1) 图的周游算法。例如，深度优先搜索、广度优先搜索。 (2) 计算最短路径算法。例如，计算单源最短路径算法、计算每对顶点间的最短路径。 (3) 计算最小支撑树算法。例如，Prim 算法、Kruskal 算法。 在本章介绍的内容中，图的存储结构和图的相关算法是本章的重点。要求掌握图的基本概 念、图的存储结构，并可以写出基于图的存储结构的各种算法，掌握计算最短路径算法和计 算最小支撑树的算法。 参考文献： 1. 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008 年 6 月。——普 通高等教育“十一五”国家级规划教材。 2. 张铭、赵海燕、王腾蛟、宋国杰 、高军，北京大学“数据结构与算法”教学设计，《计 算机教育》2008 第 20 期。获得“英特尔杯 2008 年全国计算机教育优秀论文评比”一等 奖。 3. 北京大学《数据结构与算法》精品课程网站（2008 年北京市“精品课程”暨国家“精品 课程”）， http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/