《第七章 图》由会员分享，可在线阅读，更多相关《第七章 图（105页珍藏版）》请在金锄头文库上搜索。
1、目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习第1页7.1 图的相关概念7.2 图的存储结构7.3 图的遍历7.4 最小生成树7.5 拓扑排序7.6 最短路径7.7 知识点总结目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念1. (有向)图是由一个顶点集 V 和一个弧集 E 构成的数据结构G = (V, E)，其中：
2、E| v,wV 且 P(v,w)表示从 v 到 w 的一条弧，v 为弧尾，w 为弧头。谓词 P(v,w) 定义了弧 的意义或信息。第2页EACBD例1. G1 = (V1, E1)，其中：V1=A, B, C, D, E E1=, , , , , , 目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念2. 若E，必有E,则称 (v,w) 为顶点v和顶点w之间存在一条边。由顶点集和边集构成的图称作无向图。第3页例2. G2 = (V2, E2)，其中
3、：V2=A, B, C, D, E, F E2 =(A, B), (A, E), (B, E), (C, D), (D, F), (B, F), (C, F)BCAFED目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念3. 假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，边(v,w) 和顶点v 和w相关联。和顶点v相关联的边的数目定义为顶点v的度，记为TD（v）。第4页例3.右图中：TD（B）=3 TD（D）=2BCAFED目录退出目
4、录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念对有向图来说，由于弧有方向性，则有入度和出度之分顶点的出度: 以顶点v为弧尾的弧的数目;顶点的入度: 以顶点v为弧头的弧的数目。顶点的度(TD)=出度(OD)+入度(ID)第5页例4.右图中：OD（B）=1 ID（B）=2TD（B）=3ABECD目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改
5、革强军梦学习7.1 图的相关概念思考：在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？在具有n个顶点、e条弧的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与弧数之和的关系？第6页目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念4. 权：是指对弧或边赋予的有意义的数值量。网：弧或边上带权的图，也称网图。弧或边带权的图分别称作有向网或无向网。第7页V1V2V3V42785目录退出目录第七章 图六年级数学上册课件-比的基本
6、性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念5. 子图：若图G=（V，E），G=（V，E），如果VV且E E ，则称图G是G的子图。第8页V1V2V3V4V5V1V2V1V3V4V3V4V5目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习6. 无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有向完全图：在有向图中，如果任意两个顶点之间都
7、存在方向相反的两条弧，则称该图为有向完全图。含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？ 第9页V1V2V3V4V1V2V3目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念7. 路径：在无向图G=(V, E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2, ,vim=vq)，(vij-1,vij)E （1jm）。若G是有向图，则路径也是有方向的，顶点序列满足E。第10页V1V2V3V4V
8、5例5.右图中V1 到V4的路径： V1 V4V1 V2 V3 V4V1 V2 V5V3 V4v一般情况下，图中的路径不惟一。目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念路径长度：第11页V1V2V3V4V5右图中V1 到V4的路径： V1 V4：长度为1V1 V2 V3 V4：长度为3V1 V2 V5V3 V4：长度为4非带权图路径上边的个数带权图路径上各边的权之和目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市
9、田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念路径长度：第12页V1V2V3V4V5右图中V1 到V4的路径： V1 V4：长度为8V1 V2 V3 V4：长度为7V1 V2 V5V3 V4：长度为15非带权图路径上边的个数带权图路径上各边的权之和282365目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念回路（环）：第一个顶点和最后一个顶点相同的路径 。简单路径：序列中
10、顶点不重复出现的路径。简单回路（简单环）：除第一个顶点和最后一个顶点 外，其余顶点不重复出现的回路。第13页V1V2V3V4V5V1V2V3V4目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念8. 连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(ij)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。连通分量：非连通图的极大连通子图称为连通分 量。 第14页如何求得一个非连通图的连通分量?1.含有极大顶
11、点数；2. 依附于这些顶点的所有边。目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念第15页v连通分量是对无向图的一种划分。V1V2V3V4V5V6V7V1V2V4V5V3V6V7连通分量1 连通分量2目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念9. 强连通图：在有向图中，对图中任意一对顶点vi
12、 和vj (ij)，若从顶点vi到顶点vj和从顶点vj 到顶点vi均有路径，则称该有向图是强连通图。强连通分量：非强连通图的极大强连通子图。 第16页如何求得一个非连通图的强连通分量?1.含有极大顶点数；2. 依附于这些顶点的所有弧。目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念第17页V1V2V3V4V1V3V4V2强连通分量1 强连通分量2目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物
13、进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念10. 生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。 含有n-1条边第18页多构成回路少不连通生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。 目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.1 图的相关概念第19页V1V2V3V4V5V1V2V3V4V5生成树V1V2 V3V
14、4V5V6V7V1V2V3V4V5V6V7生成森林目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习图的抽象数据类型的基本操作第20页CreatGraph(typedef struct ArcCell / 弧的定义VRType adj; / VRType是顶点关系类型。/ 对无权图，用1或0表示相邻否；/ 对带权图，则为权值类型。InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAXMAX;第33页目录退出目录第七章 图六年
15、级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习邻接矩阵存储表示typedef struct / 图的定义VertexType vexsMAX; / 顶点信息 AdjMatrix arcs; / 弧的信息 int vexnum, arcnum; / 顶点数，弧数 GraphKind kind; / 图的种类标志 MGraph;第34页目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节主题教育活动PPT模板军队国防改革强军梦学习7.2 图的存储结构2. 邻接表第35页基本思想：对于图的每个顶点vi，将所有邻接于vi的顶 点链成一个单链表，称为顶点vi的边表（对于有向图则 称为出边表），所有边表的头指针和存储顶点信息的 一维数组构成了顶点表。图的邻接矩阵存储结构的空间复杂度？ 如果为稀疏图则会出现什么现象？假设图G有n个顶点e条边，则邻接矩阵存储该图需要O(n2) 。目录退出目录第七章 图六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一
