《图的定义和术语》PPT课件.ppt

第七章图,图(Graph)是一种较线性表和树更为复杂的数据结构.在线性表中,数据元素之间仅有线性关系,每个元素只有一个直接前驱和一个直接后继;在树形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素(即其孩子结点)相关,但只能和上一层中一个元素(即其双亲结点)相关;而在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关.由此,图的应用极为广泛,特别是近年来的迅速发展,已渗入到诸如语言学逻辑学物理化学电讯工程计算机科学以及数学的其他分支中.,7.1图的定义和术语,7.2图的存储结构,7.3图的遍历,7.4图的连通性问题,7.5有向无环图及其应用,7.6最短路径,7.1图的定义和术语,（1）形式化定义Graph=(V,R)V=x|xdataobject/顶点的有穷非空集合R=VRVR=|P(v,w)(v,wV)/两个顶点之间的关系集合,（2）图形表示,图7.1图的示例,(b)无向图G2,(a)有向图G1,图由结点及边(弧)组成,与树的主要区别在于图可以有回路,（3）相关术语,顶点（Vertex）：图中的数据元素。,弧（Arc）：若VR，则表示从v到w的一条弧。,弧尾（Tail）或初始点（Initialnode）：弧的一个顶点v。,弧头（Head）或终端点（Terminalnode）：弧的一个顶点w。,有向图（Digraph）：由弧和顶点组成。,边（Edge）：若VR必有VR，即VR是对称的，则以无序对(v,w)代替这两个有序对，表示v和w之间的一条边。,无向图（Undigraph）：由边和顶点组成。,无向完全图（Completedgraph）：有条边的无向图。,有向完全图：有n(n1)条弧的有向图。,稀疏图（Sparsegraph）：有很少条边或弧（如enlogn）的图。反之称为稠密图（Densegraph）。,(a)图7.1中G1的子图,(b)图7.1中G2的子图,图7.2子图示例,对于无向图G=(V,E)，如果边(v,v)E，则称顶点v和v互为邻接点（Adjacent）。边(v,v)依附（Incident）于顶点v和v，或者说(v,v)和顶点v和v相关联。,度：指和顶点v相关联的边的数目，记为TD(v)。,对于有向图G=(V,A)，如果弧A，则称顶点v邻接到顶点v，顶点v邻接自顶点v。弧和顶点v、v相关联。,入度（InDegree）：以顶点v为头的弧的数目，记为ID(v)。,出度（OutDegree）：以顶点v为尾的弧的数目，记为OD(v)。,有向图中，顶点v的度为TD(v)ID(v)OD(v)。,路径（Path）：在无向图G=(V,E)中从顶点v到顶点v的一个顶点序列(v=vi,0,vi,1,vi,m=v)，其中(vi,j-1,vi,j)E，1jm。若G是有向图，则路径也是有向的，顶点序列满足E，1jm。,路径的长度：路径上的边或弧的数目。,简单回路或简单环：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。,回路或环（Cycle）：第一个顶点和最后一个顶点相同的路径。,简单路径：序列中顶点不重复出现的路径。,连通：在无向图G中，如果从顶点v到顶点v有路径，则称v和v是连通的。,连通图（ConnectedGraph）：对于图中任意两个顶点vi,vjV，vi和vj都是连通的图。,连通分量（ConnectedComponent）：指无向图中的极大连通子图。,(a)无向图G3,(b)G3的3个连通分量,图7.3无向图及其连通分量,强连通图：在有向图G中，如果对于每一对vi,vjV，vivj，从vi到vj都存在路径，则称G是强连通图。,强连通分量：有向图中的极大强连通子图。,生成树：一个连通图的生成树是一个极小连通子图。它含有图中全部顶点，但只有足以构成一棵树的n1条边。,图7.4G3的最大连通分量的一棵生成树,由生成树的定义易知：一棵有n个顶点的生成树有且仅有n1条边。如果一个图有n个顶点和小于n1条边，则是非连通图。如果一个图有n个顶点和大于n1条边，则一定有环。有n1条边的图不一定是生成树。,生成森林：一个有向图的生成森林由若干棵有向树组成，含有图中全部的结点，但只有足以构成若干棵不相交的有向树的弧。,图7.5一个有向图及其生成森林,由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。,例如:,G1=(V1,VR1),其中V1=A,B,C,D,EVR1=,若VR必有VR,则称(v,w)为顶点v和顶点w之间存在一条边。,由顶点集和边集构成的图称作无向图。,例如:G2=(V2,VR2)V2=A,B,C,D,E,FVR2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F),B,设图G=(V,VR)和图G=(V,VR),且VV,VRVR,则称G为G的子图。,15,9,7,21,11,3,2,弧或边带权的图分别称作有向网或无向网。,假设图中有n个顶点，e条边，则,含有e=n(n-1)/2条边的无向图称作完全图;,含有e=n(n-1)条弧的有向图称作有向完全图;,若边或弧的个数enlogn，则称作稀疏图，否则称作稠密图。,假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，,例如:,ID(B)=3,ID(A)=2,边(v,w)和顶点v和w相关联。和顶点v关联的边的数目定义为边的度。,右侧图中,顶点的出度:以顶点v为弧尾的弧的数目;,对有向图来说，,顶点的入度:以顶点v为弧头的弧的数目。,顶点的度(TD)=出度(OD)+入度(ID),例如:,ID(B)=2,OD(B)=1,TD(B)=3,由于弧有方向性，则有入度和出度之分,设图G=(V,VR)中的一个顶点序列u=vi,0,vi,1,vi,m=w中，(vi,j-1,vi,j)VR1jm,则称从顶点u到顶点w之间存在一条路径。路径上边的数目称作路径长度。,如:从A到F长度为3的路径A,B,C,F,简单路径:指序列中顶点不重复出现的路径。,简单回路:指序列中第一个顶点和最后一个顶点相同的路径。,若图G中任意两个顶点之间都有路径相通，则称此图为连通图;,若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。,若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。,对有向图，,否则，其各个强连通子图称作它的强连通分量。,假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。,对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。,（4）图的抽象数据类型定义,ADTGraph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VRVR=|v,wV且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息,基本操作：CreateGraph(初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”。,NextAdjVex(G,v,w);初始条件：图G存在，v是G中某个顶点，w是v的邻接点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。InsertVex(初始条件：图G存在，v和w是G中两个顶点。操作结果：在图G中删除弧，若G是无向的，则还删除对称弧。,