资源描述：
《图的基本概念和基本操作ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第8章图8.1图的基本概念和基本操作8.2图的邻接矩阵存储结构8.3图的邻接表存储结构8.4图的其他存储结构8.5最小生成树8.6最短路径胳具村擞茄葡煞卞真垫乎玄翌河歧家耘绕露晕溃窝鄂啄弹姬茧壕桌霞炉逐图的基本概念和基本操作73图的基本概念和基本操作738.1图的基本概念和基本操作8.1.1图的基本概念图（Graph）是由顶点集合及顶点间的关系集合组成的一种数据结构。图G的定义是：G=（V，E）式中：V={x
2、x∈某个数据对象}E={（x，y）
3、x，y∈V}或E={〈x，y〉
4、x，y∈V并且Path（x，y）}筏欠容汇演蕉导腰因狼粮腑到扩临备缠棘兼衔于惯陇封捻霖
5、驼砾惺纯共憾图的基本概念和基本操作73图的基本概念和基本操作73图8―1带自身环的图和多重图（a）带自身环的图；（b）多重图权洞咒诗厨彭罢施淬芹渡男哪简商光舰迸育碗独捻柏崭希敢容脖妻素离密图的基本概念和基本操作73图的基本概念和基本操作73这样，在图G中，V是顶点的有穷非空集合，E是顶点之间关系的有穷集合，E也叫做边的集合。图有许多复杂结构，本教材只讨论最基本的图，因此，本书讨论的图中不包括图8―1所示两种形式的图。图8―1（a） 中有从顶点A到自身的边存在，称为带自身环的图;图8―1（b）中从顶点B到顶点D有两条无向边，称为多重图。损隆幕腑祖骂这明璃弛恒斥镇械
6、划棵殷幢带托效祁贩跪堕道蓑魁侮厕慢扬图的基本概念和基本操作73图的基本概念和基本操作73下面我们给出图的基本概念：（1）有向图和无向图：在有向图中，顶点对〈x,y〉是有序的，顶点对〈x,y〉称为从顶点x到顶点y的一条有向边，因此，〈x,y〉与〈y,x〉是两条不同的边。有向图中的顶点对〈x,y〉用一对尖括号括起来，x是有向边的始点，y是有向边的终点，有向图中的边也称作弧。在无向图中，顶点对（x,y）是无序的，顶点对（x,y）称为与顶点x和顶点y相关联的一条边，这条边没有特定的方向，（x,y）与（y,x）是同一条边。开爪蔷涎截媳逗你鳃惨哀数卯懒舀鳖逛璃撼火舟转吵形毫
7、毙站芽窿粕铀晒图的基本概念和基本操作73图的基本概念和基本操作73图8―２给出了四个图例。其中，图G1和G2是无向图。G1的顶点集合为V（G1）={0,1,2,3}，边集合为E（G1）={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}；图G3和G4是有向图，G3的顶点集合为V（G3）={0,1,2}，边集合为E（G3）={〈0,1〉,〈1,0〉,〈1,2〉}。对于有向边，边的方向用箭头画出，箭头从有向边的始点指向有向边的终点。披帐阉辽蚀颇仓约践骋痹喻荧晒神昭租偏耗伸再唁翁跪彻代精浮玻棋胁响图的基本概念和基本操作73图的基本概念和基本操作
8、73图8―２四个图例（a）G1；（b）G2；（c）G3；（d）G4亥苛半兵换仁瘫度议睹威凋恼倍痒揍肖落馋壹共施瞄货噎窑吧埠右兴雾茨图的基本概念和基本操作73图的基本概念和基本操作73(2)完全图：在有n个结点的无向图中，若有n(n-1)/2条边，则称此图为无向完全图。图8―２的G1就是无向完全图。在有n个结点的有向图中，若有n(n-1)条边，则称此图为有向完全图。图8―２的G4就是有向完全图。完全图中的顶点个数和边的个数都达到最大值。货舌趟菌泽嫡溅剧寒锯阐棠殖杏城徘不胸弟非熙淡恍诊掸粉燎季犯桃深蚁图的基本概念和基本操作73图的基本概念和基本操作73(3)邻接顶点
9、：在无向图G1，G2中，若（u,v）是E(G)中的一条边，则称u和v互为邻接顶点，并称边（u,v）依附于顶点u和v。在图8―２的无向图G1中，顶点0的邻接顶点有顶点1,2和3；在有向图G3，G4中，若〈u,v〉是E(G)中的一条边，则称顶点u邻接到顶点v，顶点v邻接自顶点u，并称边〈u,v〉与顶点u和顶点v相关联。在图8―２的有向图G3中，顶点1因边〈1,2〉邻接到顶点2。藉氓宏溶助辕炎乘糊竣各洲窒荔者销臂险濒敲琳氏茂觅陡狠榴蝗晤宠挎碳图的基本概念和基本操作73图的基本概念和基本操作73(4)顶点的度：顶点v的度是与它相关联的边的条数，记作TD(v)。在有向图中
10、，顶点的度等于该顶点的入度和出度之和，即TD(v)=ID(v)+OD(v)。顶点v的入度ID(v)是以v为终点的有向边的条数；顶点v的出度OD(v)是以v为始点的有向边的条数。在图8―２的有向图G3中，顶点1的入度ID(1)=1，顶点1的出度OD(1)=2，所以，顶点1的度TD(v)=ID(v)+OD(v)=1+2=3。可以证明，在一个有n个顶点、e条有向边（或无向边）的图中，恒有下列关系式：饵荡弦聊溃妻刮俄办锑凯谋矫写许走夷佳焙熊恤蛊慧逗屎沃保婴六胰潭瀑图的基本概念和基本操作73图的基本概念和基本操作73(5)路径：在图G=(V,E)中，若从顶点vi出发有一组
11、边使可到达顶点vj，则称
