资源描述：
《数据结构第7章图ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第7章图已经学习的数据结构线性结构：线性表、栈、队列、串、数组、广义表树形结构：二叉树、树、森林图更一般、更复杂图中的结点(即：顶点)之间的关系是任意的，即结点的前驱和后继结点个数不再限制。1计算机网络交通网络电话网络人际关系网……ABCFDE2342/31/1,21学生选课网27.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第7章图37.1图的定义和术语一．图的定义图是由顶点集合及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V---顶点集E---关系的集合4图的抽象数据类型定义：A
2、DTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={
3、v，w∈V且P(v，w)，表示从v到w的弧，谓词P(v，w)定义了弧的意义或信息}基本操作P：CreateGraph(&G，V，VR)；初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。DestroyGraph(&G)；初始条件：图G存在。操作结果：销毁图G。LocateVex(G，u)；初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其它
4、信息。GetVex(G，v)；初始条件：图G存在，v是G中某个顶点。操作结果：返回v的值。PutVex(&G，v，value)；初始条件：图G存在，v是G中某个顶点。操作结果：对v赋值value。FirstAdjVex(G，v)；初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”。NextAdjVex(G，v，w)；初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的(相对于w的)下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。InsertVex(&G，v)；初始条件：图G
5、存在，v和图中顶点有相同特征。操作结果：在图G中增添新顶点v。DeleteVex(&G，v)；初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的弧。InsertArc(&G，v，w)；初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添弧，若G是无向的则还增添对称弧。DeleteArc(&G，v，w)；初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧，若G是无向的则还删除对称弧。DFSTraverse(G，v，Visit())；初始条件：图G存在，v是G中某个顶点，Visit
6、是顶点的应用函数。操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。BFSTraverse(G，v，Visit())；初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数。操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。}ADTGraph二．有关图的常用术语边(v,w)弧ＶＷＶＷ边弧弧头弧尾有向图与无向图在有向图中，顶点对是有序的。在无向图中，顶点对(x,y)是无序的。v1v2v4v3v4v5v3v2v1G1=(V1,A1)其中：V1={v1,v2,v3,v4}A1
7、={,,,}G2=(V2,A2)其中V2={v1,v2,v3,v4,v5}A2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}1000001111222265433完全图若有n个顶点的无向图有n(n-1)/2条边,则此图为无向完全图。有n个顶点的有向图有n(n-1)条边,则此图为有向完全图。11邻接顶点若(v,w)是E(G)中的一条边，则称v与w互为邻接顶点。若是E(G)中的一条弧，则称顶点v邻接到顶点ｗ，顶点w邻接自顶点v。子图设有两个图G＝(
8、V,E)和G‘＝(V’,E‘)。若V’V且E‘E,则称图G’是图G的子图。权某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。0123子图013012302312顶点的度一个顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。ABECFTD(B)=OD(B)+ID(B)=3思考：边数与顶点的度的和之间有什么关系？TD(v)=ID(v)+OD(v)13路径是一个顶点序列，并且相邻的两个顶点有边或弧
9、相连。路径长度非带权图的
