多7章离广义表
1
图( Graph)是一种较线性表和树更为复杂的数据结构。在 线性表中,数据元素之间仅有线性关系,即每个数据元素只有 个直接前驱和一个直接后继;在树形结构中,数据元素之间 有着明显的层次关系,虽然每一层上的数据元素可能和下一层 中多个元素(孩子)相关,但只能和上一层中一个元素(双亲 相关;而在图形结构中,结点之间的关系可以是任意的,任意 两个数据元素之间都可能相关。 图在各个领域都有着广泛的应用如电路网络分析、交通运输 管理与线路的铺设、印刷电路板与集成电路的布线等众多直接 与图有关的问题,它们必须用图的有关方法进行处理;另外像 工作的分配、工程进度的安排、课程表的制订、关系数据库的 设计等许多实际问题,如果间接地用图来表示,处理起来比较 方便。这些技术领域都是把图作为解决问题的主要数学手段来 使用,因此,如何在计算机中表示和处理图结构,就是计算机 科学需研究的一项重要课题
2
【学习国标】 1.领会图的类型定义 2.熟悉图的各种存储结构及其构造算法 了解各种存储结构的特点和选用原则 3.熟练掌握图的两种遍历算法 4.理解各种图的应用问题的算法 5了解广义表的结构和使用
3
【重点和点】 图的应用极为广泛,而且图的各种应用问 题的算法都比较经典,因此本章重点在于 理解各种图的算法及其应用场合。 【知识点】 图的类型定义、图的存储表示、图的深度 优先搜索遍历和图的广度优先搜索遍历 无向网的最小生成树、最短路径、拓扑排 序、关键路径
4
第七章习题 基础知识 -P47:717.5777.97107.11 °作业 P49:7227.237.247287.32 P50:7.367.41
5
第7章图和广义表 7.1图的定义和术语 7.2图的存储结构 7.3图的遍历 7.4连通内的最小生成树 7.5单源最短路径 7.6拓扑排序 7.7关键路径 7.8广义表
6
7。國的喜家术漫 V=vertex 图:记为G=(VE) E=edge 其中:V是O的顶点集合,是有穷非空集; E是的边集合,是有穷集。 问:当E(G)为空时,图G存在否? 答:还存在!但此时图G只有顶点而没有边 有向图:图G中的每条边都是有方向的; 无向图:图G中的每条边都是无方向的 完全图:图G任意两个顶点都有一条边相连接; 必若n个顶点的无向图有m(n-1)/2条边,称为无向完全图 心若n个顶点的有向图有m(m-1)条边,称为有向完全图
7 7.1 图的基本术语 n(n-1)/2 条边 无向完全图 n(n-1) 条边 有向完全图
①完全无向图有m(m1)/2条边。 证明:若是完全无向图,则顶点1必与所有其他顶点各有条连 线,即有n-1条边,顶点2有n-2条边,…,顶点n-1有1条边,顶点 n有0条边 总边数=n-1+n-2+…+1+0=(n-+0)n/2=m(-1)2 ②完全有向图有n(m1)条边。 证明:若是完全有向图,则顶点1必必与所有其他顶点各有2条 连线,即有2(n-1)条边,顶点2有2(n-2)条边,…,顶点n1有2 条边,顶点n有0条边 总边数=2(n-1+n-2+…+1+0)=2(n-1+0)n/2=m(-1)
8
例:判断下列4种图形各属什么类型? (3)④⑤⑥ (a)G1 (b)G2 (C)G3 (d)G4 无向完全图无向图(树) 有向图有向完全图 m(1)2条边 m(n-)条边 G的顶点集合为V(G1)=1{0,1,2,3} 边集合为E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}
9
例 ① G 图G中:Ⅴ(G1)={1,2,3,45,6} E(G1={,,,,,,} 例 图G2中:V(G2)={1,2,3,456,7} E(G1)={(1,2),(1,3),(2,3),(2,4),(25),(5,6),(5,7)
10
