数据结构课件第5章

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

1、第五章图第五章图5.1图的基本概念5.2图的存储结构5.3图的遍历5.4连通图与生成树5.5有向无环图及应用第五章图5.1图的概念一图的概念二图的应用三图的基本术语四图的基本操作§5.1图的基本概念一图的概念图的定义：图G由两个集合V,E构成，记作G=其中V是顶点的非空有限集合，E是边的有限集合（边是顶点的无序对或有序对集合）。G1=V1={v0,v1,v2,v3,v4}E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)}G1图示无序对(vi,vj)：用连接顶点vi、vj的线段表示，称为无向边；例V0V4V3

2、V1V2G2图示有序对：用以vi为起点、vj为终点的有向线段表示，称为有向边或弧；无向图：在图G中，若所有边是无向边，则称G为无向图；有向图：在图G中，若所有边是有向边，则称G为有向图；§5.1图的基本概念V0V1V2V3G2=V2={v0v1,v2,v3}E2={,,,}图的应用举例例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图如产品的生产流程图顶点

3、：工序边：各道工序之间的顺序关系§5.1图的基本概念V0V4V3V1V2V0V1V2V31邻接顶点及关联边邻接顶点：边e=(v,u)，则称顶点v、u相邻接关联边：边e=(v,u),则称边e关连顶点v、u2顶点的度、入度、出度顶点V的度=与V相关联的边的数目在有向图中：顶点V的出度=以V为起点的有向边数顶点V的入度=以V为终点的有向边数顶点V的度=V的出度+V的入度设图G的顶点数为n，边数为e图的所有顶点的度数和=2*e（每条边对图的所有顶点的度数和“贡献”2度）e图的基本术语§7.1图的基本概念V0V4V3V1V2V0V1V2V3路径、回路无向图G=（V，E）中的顶点序列v1,v2,

4、…,vk,若(vi,vi+1)E(i=1,2,…k-1),v=v1,u=vk,则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；有向图D=（V，E）中的顶点序列v1,v2,…,vk,若E(i=1,2,…k-1),v=v1,u=vk,则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；在图1中，V0,V1,V2,V3是V0到V3的路径；V0,V1,V2,V3,V0是回路；在图2中，V0,V2,V3是V0到V3的路径；V0,V2,V3,V0是回路；无向图G1有向图G2例§5.1图的基本概念V0V4V3V1V2V0V1V2V3简单路径和简单回路

5、在一条路径中,若除起点和终点外,所有顶点各不相同,则称该路径为简单路径；由简单路径组成的回路称为简单回路；在图1中，V0,V1,V2,V3是简单路径；V0,V1,V2,V4,V1不是简单路径；在图2中，V0,V2,V3,V0是简单回路；无向图G1有向图G2例V0V4V3V1V2V0V1V2V3连通图（强连通图）在无（有）向图G=中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）非连通图连通图强连通图非强连通图V0V1V2V3V0V4V3V1V2V0V1V2V3V0V2V3V1V5V4子图设有两个图G=（V，E）、G1=（V1，E1），若V1V，E1

6、E，E1关联的顶点都在V1中，则称G1是G的子图；例(b)、(c)是(a)的子图(a)(b)(c)V0V4V3V1V2V0V4V3V1V2V0V4V3V1V2连通分量（强连通分量）无向图G的极大连通子图称为G的连通分量极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通；连通分量非连通图§5.1图的基本概念V0V2V3V1V5V4V0V2V1非连通分量有向图D的极大强连通子图称为D的强连通分量极大强连通子图意思是：该子图是D强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的；强连通分量V0V1V2V3V0V2V3V17生成树包含无向图G所

7、有顶点的的极小连通子图称为G的生成树极小连通子图意思是：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通，若T是G的生成树当且仅当T满足如下条件T是G的连通子图T包含G的所有顶点T中无回路连通图G1G1的生成树§5.1图的基本概念V0V4V3V1V2V0V4V3V1V2V0V4V3V1V2四图的基本操作P156第五章图5.2图的存储结构一邻接矩阵二邻接表§5.2图的存储结构图的存储结构至少要保存两类信息：1)顶点的数据2)顶点间的