第7章-[兼容模式].pdfVIP

第七章 图 数据结构 本章说明 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 生成树 7.5 拓扑排序 7.6 最短路径 本章小结 返回主目录 1 第七章 图 本章说明 学习目标 领会图的类型定义。 熟悉图的各种存储结构及其构造算法，了 解各种存储结构的特点及其选用原则。 熟练掌握图的两种遍历算法。 理解各种图的应用问题的算法。 2 第七章 图 本章说明 重点和难点 图的应用极为广泛，而且图的各种应用问 题的算法都比较经典，因此本章重点在于 理解各种图的算法及其应用场合。 知识点 图的类型定义、图的存储表示、图的深度 优先有哪些信誉好的足球投注网站遍历和图的广度优先有哪些信誉好的足球投注网站遍历、 无向网的最小生成树、最短路径、拓扑排 序、关键路径 3 第七章 图 7.1 图的定义和术语 图(Graph)—— 图G是由两个集合V和VR组成 的，记为G=(V,VR) 其中：V是顶点的有穷非空有限集 VR是两个顶点之间关系的有限集合， 即边集合，边是顶点的无序对或有序对 无序对——无向图 有序对——有向图 4 第七章 图 7.1 图的定义和术语 有向图——有向图G是由两个集合V和VR组成 其中：V是顶点的有穷非空有限集 VR是有向边 （也称弧）的有限集合， 弧是顶点的有序对，记为v,w ，v,w是 顶点，v为弧尾，w为弧头 G = (V , VR ) 1 1 1 1 2 其中: V ={1, 2, 3, 4} 1 VR ={1,2, 1,3, 3 4 1 有向图G1 3,4, 4,1} 5 第七章 图 7.1 图的定义和术语 无向图—— 由顶点集和边集构成的图。 若v,