《数据结构的第八讲》PPT课件.ppt

*引言现实世界存在许多不同类型的模拟系统。例如:交通流量就是其中一个实例。顶点表示街道的十字路口,同时边表示街道本身。加权边可以用来表示车速限制或者车道数量。模型可以使用系统来确定最佳路线和可能遭受交通堵塞的街道。例如:航空公司的飞行系统。每一个飞机场就是一个顶点,而从一个顶点到另一个顶点的航线就是一条边。加权的边可以表示从一个机场到另一个机场飞行的费用,或者表示从一个机场到另一个机场的大概距离,这取决于模拟的内容。:*图的定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构:Graph=(V,E)其中:V={vi|vi某个数据对象}是顶点的有穷非空集合;E={(vi,vj)|vi,vjV}或E={<vi,vj>|vi,vjV&&Path(vi,vj)}是顶点之间关系的有穷集合,也叫做边(edge)集合。Path(vi,vj)表示从vi到vj的一条单向通路,它是有方向的。0213图是由一组顶点和一组边构成的*图的定义无向图:(vi,vj)=(vj,vi):<vi,vj>::=<vj,vi>不同边vivjtailhead*图的定义vivjvi和vj是互为邻接顶点;(vi,vj)依附于vi和vjvivjvi邻接到vj;vj邻接自vi;<vi,vj>相关联于viandvj子图G’G:V(G’)V(G)&&E(G’)E(G)0123子图0130123023*图的定义路径(path):图中顶点的序列,所有的顶点由边连接在一起。在图G=(V,E)中,若从顶点vi出发,沿一些边经过一些顶点vp1,vp2,…,vpm,到达顶点vj。则称顶点序列(vivp1vp2...vpmvj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应是属于E的边。*图的定义路径的长度:从路径中第一个顶点到最后一个顶点的边的数量。讨论的图对象的限制:(1)自身环不讨论.(2)与两个特定顶点相关联的边不能多于一条,多重图也不讨论。01012*图的定义简单路径:若路径上各顶点v1,v2,...,vm均不互相重复,则称这样的路径为简单路径。回路:若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的路径为回路或环(loop)。环的长度为0。在有向图中路径至少为1以便于初始定点也是结束定点。在有向图中,边可能是相同的,但是在无向图中,边必须是不同的。