资源描述：
《chapter 7 图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、14-Aug-211第七章图最复杂的数据结构，数据元素之间存在多对多的复杂关系14-Aug-212第一节图的基本概念图是一种常见的数据结构，通常用来表示元素之间多对多的关系比如：通信网络中通信节点之间的关系中国特有的复杂人际关系图定义：图是由顶点(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,VR)V={x
2、x某个数据对象}是顶点的有穷非空集合；VR={
3、v,wV}是顶点之间关系的有穷集合.表示从v到w的一条弧(Arc)。v被称为弧尾或初始点(Tail)，w被
4、称为弧头(head)或终端点，这样的弧称为有向弧。说明：图中的数据元素通常称为顶点（Vextex）顶点之间的关系称为弧（Arc）或边14-Aug-213有向图与无向图由有向弧构成的图称为有向图。如果在一个图中，对于任意的一条弧必然存在另外一条弧则用（v,w）来表示这两个有序对，并称（v,w）为顶点v,w之间的一条边(Edge)，此时的图称为无向图。在有向图中，顶点对是有序的在无向图中，顶点对(v,w)是无序的。14-Aug-214有向图和无向图示例(a),(b)无向图(c),(
5、d)有向图14-Aug-215本课程不讨论的图在本课程中我们不讨论下列两种图：有自环的图多重图14-Aug-216图的抽象数据类型定义ADTGraph{数据对象V：v是具有相同属性的数据元素的集合(顶点集合)。数据关系R：R是图中弧或边的集合。图的操作：1）CreateGraph(&G,V,VR)根据顶点和弧创建图2）DestoryGraph(&G)；如果图存在，则销毁图3)LocateVex(G,u)在图中寻找特性为u的顶点。4）GetVex(G,v)；返回图中顶点v的值5）PutVex(&G,v,val
6、ue)；给图中的顶点v赋值；6）FirstAdjVex(G,v)；寻找图中顶点v的第一个邻接顶点；14-Aug-217基本操作7）NextAdjVex(G,v,w)；返回图中相对于顶点w的顶点v的下一个顶点；8）InsertVex(&G,v)；插入顶点9）DeleteVex(&G,v)；删除顶点10）InsertArc(&G,v,w)；在顶点v，w之间插入一条弧11）DeleteArc(&G,v,w)删除顶点v，w之间的弧12）DFSTravese(&G,v,visit())；从顶点v开始，根据深度优先的原
7、则遍历图13）BFSTravese(&G,v,visit())；从顶点v开始，根据广度优先的原则遍历图}14-Aug-218有向图与无向图示例有向图无向图14-Aug-219顶点数目与弧或边数目的关系假定图中的顶点数目用n来表示，图中的边或弧的数目用e来表示，如果不考虑多重图和到自身的弧，则有对于无向图有：0≤e≤n(n-1)/2对于有向图有：0≤e≤n(n-1)完全图与有向完全图有n个顶点的无向图有n(n-1)/2条边,则此图为完全图。有n个顶点的有向图有n(n-1)条边,则此图为有向完全图14-Aug-
8、2110有向完全图与无向完全图示例213213有向完全图无向完全图14-Aug-2111稀疏图、网、子图稀疏图/稠密图:如果图中只有很少的弧或边，则称该图为稀疏图，反之则称为稠密图。权：与图的边或弧相关的数值叫做权网：带有权值的图称为网子图：设有两个图G＝(V,E)和G’＝(V’,E’)。若V’V且E’E,则称图G’是图G的子图。14-Aug-2112子图示例14-Aug-2113顶点的度顶点的度一个顶点v的度是与它相关联的边的条数。记作TD(v)。对于有向图：顶点v的入度是以v为头的弧的数目,记作ID
9、(v);顶点v的出度是以v为尾的弧的数目,记作OD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。14-Aug-2114有向图和无向图中顶点的度示例157324G26顶点5的度：3顶点2的度：4245136G1顶点2入度：1出度：3顶点4入度：1出度：014-Aug-2115邻接顶点与路径邻接顶点：如果(u,v)是E(G)中的一条边，则称u与v互为邻接顶点。路径：在图G＝(V,E)中,若从顶点vi出发,沿一些边经过一些顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vivp1vp2...
10、vpmvj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)...(vpm,vj)应是属于E的边。14-Aug-2116路径长度、简单路径与回路路径长度非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。简单路径若路径上各顶点v1,v2,...,vm均不互相重复,则称这样的路径为简单路径。回路若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的路径为回路
