数据结构第7单元.pptVIP

课前思考 1、如何确定一项工程的工期？最佳工期如何计算？（关键路径问题） 2、如何以最低造价架构城市之间的通信网？几个小区之间要建一个供水站，建在什么位置最合适？（最小生成树问题） 3、如何合理安排大一到大四的教学计划？（拓扑排序问题） 课前导学 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 知识点小结 【学习目标】 　　1．领会图的类型定义。　　2．熟悉图的各种存储结构， 了解各种存储结构的特点及其选用原则。　　3．熟练掌握图的两种遍历算法。　　4．理解各种图的应用问题的算法。 【重点和难点】 　理解各种图的算法及其应用场合。? 【知识点】　　图的类型定义、图的存储表示、图的深度优先有哪些信誉好的足球投注网站遍历和广度优先有哪些信誉好的足球投注网站遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径. 7.1 图的定义和术语 1. 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(Vertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的,v0,v2）。 有向图(Digraph)—— 有向图G是由两个集合V(G)和E(G)组成的，其中：V(G)是顶点的非空有限集，E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为v,w，v,w是顶点，v为弧尾，w为弧头 无向图(Undigraph)—— 无向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集，E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v) 有向完备图——n个顶点的有向图最大边数是n(n-1) 无向完备图——n个顶点的无向图最大边数是n(n-1)/2 顶点的度 无向图中，顶点的度为与每个顶点相连的边数 有向图中，顶点的度分成入度与出度 入度：以该顶点为头的弧的数目 出度：以该顶点为尾的弧的数目 子图——如果图G(V,E)和图G’(V’,E’),满足：V’?V E’?E 则称G‘为G的子图 权(Weight)——与图的边或弧相关的数,可以表示两个顶点之间的距离或耗费 网——带权的图 上海→北京 怎么走最优?　 路径——路径是顶点的序列V={Vi，0,Vi，1,……Vi，n}，满足(Vi，j-1,Vi，j)?E 或 Vi，j-1,Vi，j?E,(1j?n) 路径长度——沿路径边的数目或沿路径各边权值之和 回路——第一个顶点和最后一个顶点相同的路径 简单路径——序列中顶点不重复出现的路径 简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路 连通——从顶点V到顶点W有一条路径，则说V和W是连通的 连通图——图中任意两个顶点都是连通 连通分量——非连通图的每一个连通部分（连通的子图） 强连通图——有向图中，如果对每一对Vi,Vj?V, Vi?Vj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是~ 2. 图的抽象数据类型ADT Graph {数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R＝{VR} VR＝{v,w| v,w∈V且P(v,w)，v,w表示从v到w的弧，谓词P(v,w)定义了弧v,w的意义或信息 } 基本操作P：结构的建立和销毁: CreateGraph(G,V,VR); // 按V和VR的定义构造图G DestroyGraph(G); // 销毁图G 对顶点的访问操作: LocateVex(G, u); // 若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。 GetVex(G, v); // 返回v的值 PutVex(G, v, value); // 对v赋值value 对邻接点的操作: FirstAdjVex(G, v); // 返回v的第一个邻接点。若该顶点在G中没有邻接点，则返回“空”  NextAdjVex(G, v, w); //返回v的（相对于w的）下一个邻接点若w是v的最后一个邻接点，则返回“空” 插入或删除顶点: InsertVex(G, v); // 在图G中增添新顶点v DeleteVex(G, v); // 删除G中顶点v及其相关的弧 插入和删除弧: InsertArc(G, v, w); // 在G中增添弧v,w，若G是无向的，则还增添对称弧w,v DeleteArc(G,