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.edu7 } 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/