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

《《数据结构的第八讲》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1引言现实世界存在许多不同类型的模拟系统。例如：交通流量就是其中一个实例。顶点表示街道的十字路口，同时边表示街道本身。加权边可以用来表示车速限制或者车道数量。模型可以使用系统来确定最佳路线和可能遭受交通堵塞的街道。例如：航空公司的飞行系统。每一个飞机场就是一个顶点，而从一个顶点到另一个顶点的航线就是一条边。加权的边可以表示从一个机场到另一个机场飞行的费用，或者表示从一个机场到另一个机场的大概距离，这取决于模拟的内容。由图模拟真实世界系统第八讲图和图的算法主要内容8.1图的定义8.2图的存储表示8.3图的第一个应用：拓扑排序8.4图的搜索8.5最小生

2、成树8.6查找最短路径8.1图的定义5图的定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中：V={vi

3、vi某个数据对象}是顶点的有穷非空集合；E={(vi,vj)

4、vi,vjV}或E={

5、vi,vjV&&Path(vi,vj)}是顶点之间关系的有穷集合，也叫做边(edge)集合。Path(vi,vj)表示从vi到vj的一条单向通路,它是有方向的。0213图是由一组顶点和一组边构成的6图的定义无向图:(vi,vj)=(vj,vi)同一条边.有向图:::=

6、i>不同边vivjtailhead7图的定义vivjvi和vj是互为邻接顶点;(vi,vj)依附于vi和vjvivjvi邻接到vj;vj邻接自vi;相关联于viandvj子图G’G:V(G’)V(G)&&E(G’)E(G)0123子图01301230238图的定义路径（path）：图中顶点的序列，所有的顶点由边连接在一起。在图G＝(V,E)中,若从顶点vi出发,沿一些边经过一些顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vivp1vp2...vpmvj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(

7、vp1,vp2)、...、(vpm,vj)应是属于E的边。9图的定义路径的长度：从路径中第一个顶点到最后一个顶点的边的数量。讨论的图对象的限制:(1)自身环不讨论.(2)与两个特定顶点相关联的边不能多于一条，多重图也不讨论。0101210图的定义简单路径：若路径上各顶点v1,v2,...,vm均不互相重复,则称这样的路径为简单路径。回路：若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的路径为回路或环（loop）。环的长度为0。在有向图中路径至少为1以便于初始定点也是结束定点。在有向图中，边可能是相同的，但是在无向图中，边必须是不同的。11图

8、的定义权：某些图的边具有与它相关的数值,称之为权。这种带权图叫做网络。代价：顶点还可以有权值，被称为代价。12图的定义顶点v的入度：以v为终点的有向边的条数,记作ID(v)。顶点v的出度：以v为始点的有向边的条数,记作OD(v)。顶点的度：一个顶点v的度是与它相关联的边的条数，记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。13图的定义vID(v)=3OD(v)=1TD(v)=4注意图G有n个顶点和e条边,那么14图的定义路径长度：非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。ABECF从A到F长度

9、为3的路径{A,B,C,F}15图的定义连通图与连通分量：在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。强连通图与强连通分量：在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。16图的定义无向图，若图中任意两个顶点之间都有路径相通，则称此图为连通图;若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。BACDFEBACDFE17图的定义

10、有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。否则，其各个强连通子图称作它的强连通分量。ABECFABECF18图的定义如果存在从任意顶点到其他任意顶点的路径，就认为无向图是连通的（connected）在有向图中，这个条件被称为是强连通（stronglyconnected）如果有向图不是强连通的，但是又认为连通了，这就被称为弱连通（weaklyconnected）19图的定义完全图:边数最大的图02130213每组顶点之间都有边20图的定义生成树：一个连通图的生成树是其极小连通子图。在n个顶点的情形下，有n-1条边。假设一个

11、连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。在极小连通子图