ds_2010_71数据结构课件

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

1、第7章图主讲：林华7.17.1图的定义和术语7.27.2图的存储结构7.37.3图的遍历7.47.4图的连通性问题7.7.55有向无环图及其应用7.7.66最短路径学习目标1.掌握图的类型定义和术语。2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。3．熟练掌握图的两种遍历算法：深度优先搜索和广度优先搜索的算法4．理解和掌握各种图的应用问题的算法。重点和难点图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于图的遍历和理解掌握各种图的算法及其应用场合。知识点图的类型定义和术语、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍

2、历、无向网的最小生成树、拓扑排序、关键路径、最短路径7.17.1图的定义和术语图的抽象数据类型定义::ADTGraph{ADTGraph{数据对象：V是具有相同特性的数据元素的集合，称为顶点集。数据关系：R={VR}VR＝{

3、v,w∈V且P(v,w)，表示从v到w的一条弧，并称v为弧尾，w为弧头。谓词P(v,w)定义了弧的意义或信息}图是由一个顶点集VV和一个弧集RR构成的数据结构。Graph=(V,R)由于“弧”是有方向的，因此称由顶点集V和弧集R构成的图为有向图。例如:G1=(V1,VR1)其中AAV1={A,B,C,D,E}BEBEVR1

4、={,,,,,CDCD,}G1若∈VR必有∈VR,由顶点集和边则称(v,w)为顶点v和顶点集构成的图称w之间存在一条边。作无向图。例如:G2=(V2,VR2)BCBCV2={A,B,C,D,E,F}VR2={(A,B),(A,E),ADAD(B,E),(C,D),(D,F),(B,F),(C,F)}FEFEG2常用的名词和术语子图、网完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林15AA911弧或边带

5、权的图BB721EE分别称作有向网或3CCFF无向网。2GBB设图G=(V,{VR})和图AAG′=(V′,{VR′}),BBEE且V′⊆V,VR′⊆VR,则称G′为G的子图。CCFFG′假设图中有nn个顶点，ee条边，则含有e=n(n-1)/2e=n(n-1)/2条边的无向图称作完全图(无向完全图)；含有e=n(n-1)e=n(n-1)条弧的有向图称作有向完全图；若边或弧的个数e

6、点vv和ww互为邻接点，边(v,w)依附于顶点v和w，或边(v,w)(v,w)和顶点vv和ww相关联。和顶点vv关联的边的数目定义为顶点vv的度,BBCC记为TD(V)TD(V)。例如:AADDTD(B)=TD(B)=33TD(A)=TD(A)=22FFEE对有向图来说，AA顶点的出度:以顶点vBBEE为弧尾的弧的数目；CCFF顶点的入度:以顶点v例如:为弧头的弧的数目。OD(B)=OD(B)=11ID(B)=ID(B)=22顶点的度(TDTD)=TD(B)=TD(B)=33出度(ODOD)+入度(IDID)如果顶点Vi的度记为TD(vi)，一个有nn个顶点，ee条边或弧的

7、图，满足如下关系：n1e=∑TD(vi)i2i=1设图G=(V,{VR})中从顶点u到顶点w的路径是的一个顶点序列{u=vi,0,vi,1,…,vi,m=w}，其中对有向图，∈VR1≤j≤m,则称从顶点u到顶点w之间存在一条有向路径。对无向图，(vi,j-1,vi,j)∈VR1≤j≤m,则称从顶点u到顶点w之间存在一条无向路径。路径上边或弧的数目称作路径长度。序列中第一个顶点和最后一个顶点相同的路径称为回路或环。简单路径:序列中顶点不重复出现的路径。简单回路:序列中第一个顶点和最后一个顶点相同，除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路

8、。如:长度为3的路径AA{A,B,C,F}是简单路径BBEE{A,B,C,F,A}是简单回路CCFF{A,B,C,F,A,E}不是简单路径{E,C,F,B,C,F,A,E}不是简单回路若无向图G中任意两BBCC个顶点之间都存在一条无向路径，则称此AADD图为连通图；BBCCFFEE若无向图为非连通AADD图，则图中各个极大连通子图称作此图的FFEE连通分量。对有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。否则，其各个极大强连通子图称作它的强连通分量。AAAABBEEBBEECCFFCCFF例