数据结构第07章图

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

1、第七章图本章介绍另一种非线性数据结构——图图：是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继；第七章图7.1图的概念7.2图的存储结构7.3图的遍历7.4生成树7.5最短路径7.6拓扑排序第七章图学习要点1．熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系；2．熟练掌握图的两种遍历：深度优先遍历和广度优先遍历的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略3．理解

2、各种图的算法；7.1图的概念一图的概念二图的应用三图的基本术语第七章图§7.1图的基本概念一图的概念图的定义图G由两个集合构成，记作G=其中V是顶点的非空有限集合，E是边的有限集合，其中边是顶点的无序对或有序对集合。G1=V={v0,v1,v2,v3,v4}E={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)}G1图示无序对(vi,vj)：用连接顶点vi、vj的线段表示，称为无向边；例V0V4V3V1V2G2图示有序对：用以vi起点、以vj为

3、终点的有向线段表示，称为有向边或弧；称vi为弧尾，vj为弧头无向图：在图G中，若所有边是无向边，则称G为无向图；有向图：在图G中，若所有边是有向边，则称G为有向图；混和图：在图G中，既有无向边也有有向边，则称G为混合图；§7.1图的基本概念V0V1V2V3G2=V={v0v1,v2,v3}E={,,,}图的应用举例例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路

4、例3通讯线路图顶点：地点边：地点间的连线例4各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系§7.1图的基本概念V0V4V3V1V2V0V1V2V31邻接点及关联边邻接点：边的两个顶点,v、u互为邻接点关联边：若边e=(v,u),则称顶点v、u关联边e2顶点的度、入度、出度在无向图中：顶点V的度=与V相关联的边的数目在有向图中：顶点V的出度=以V为起点有向边数顶点V的入度=以V为终点有向边数顶点V的度=V的出度+V的入度设图G的顶点数为n，边数为e图的所有顶点的度数和=2*e（每条边对图的所有顶点的度数和“

5、贡献”2度）e图的基本术语§7.1图的基本概念V0V4V3V1V2V0V1V2V3完全图、权、网有向完全图——具有n(n-1)条弧的n个顶点的有向图称为~无向完全图——有n(n-1)/2条边的n个顶点的无向图称为~权——与图的边或弧相关的数叫~网——带权的图叫~例213213有向完全图无向完全图例1452375318642§7.1图的基本概念4路径、回路路径——路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)E或E,(1

6、权值之和回路——第一个顶点和最后一个顶点相同的路径叫~在图G1中，V0,V1,V2,V3是V0到V3的路径；V0,V1,V2,V3,V0是回路；在图G2中，V0,V2,V3是V0到V3的路径；V0,V2,V3,V0是回路；无向图G1有向图G2例§7.1图的基本概念V0V4V3V1V2V0V1V2V35简单路径和简单回路在一条路径中,序列中顶点不重复出现的路径称为简单路径；由简单路径组成的回路称为简单回路；在图G1中，V0,V1,V2,V3是简单路径；在图G2中，V0,V2,V3,V0是简单回路；无向图G1有向图G2例§7.

7、1图的基本概念V0V4V3V1V2V0V1V2V36连通图（强连通图）在无（有）向图G=中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）§7.1图的基本概念非连通图连通图强连通图非强连通图V0V1V2V3V0V4V3V1V2V0V1V2V3V0V2V3V1V5V47子图设有两个图G=（V，E）、G1=（V1，E1），若V1V，E1E，则称G1是G的子图；例(b)、(c)是(a)的子图(a)(b)(c)§7.1图的基本概念V0V4V3V1V2V0V4V3V1V2V0V4V3V1V28连

8、通分量（强连通分量）无向图G的极大连通子图称为G的连通分量极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通；连通分量非连通图§7.1图的基本概念V0V2V3V1V5V4有向图D的极大强连通子图称为D的强连通分量极大强连通子图意思是：该子图是D强连通子图，将D的任何不