《第七章 图的定义和术语优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第七章 图的定义和术语优秀PPT.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第七章第七章 图的定义和术图的定义和术语语 1现在学习的是第1页，共28页线性结构线性结构：是研究数据元素之间的一对一：是研究数据元素之间的一对一关系。在这种结构中，除第一个和最后一个元素关系。在这种结构中，除第一个和最后一个元素外，任何一个元素都有唯一的一个直接前驱和直外，任何一个元素都有唯一的一个直接前驱和直接后继。接后继。树结构树结构：是研究数据元素之间的一对多的：是研究数据元素之间的一对多的关系。在这种结构中，每个元素对下关系。在这种结构中，每个元素对下(层层)可以有可以有0个或多个元素相联系，对上个或多个元素相联系，对上(层层)只有唯一的一只有唯一的一个元素相关，数据元素之间有明显的
2、层次关系。个元素相关，数据元素之间有明显的层次关系。现在学习的是第2页，共28页图图(Graph)是一种比线性表和树更为复杂的是一种比线性表和树更为复杂的数据结构。数据结构。图结构图结构：是研究数据元素之间的多对多的关：是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。意元素之间都可能相关。现在学习的是第3页，共28页7.1 图的图的定义定义和术语和术语V1V3V2V4V1V2V5V4V3图图7.1 图的示例图的示例(a)有向
3、图有向图G1(b)无向图无向图G2(a)(b)现在学习的是第4页，共28页7.1.1 图的定义和术语图的定义和术语顶点顶点（Vertex)Vertex)：在图中的数据元素通常称：在图中的数据元素通常称为顶点（为顶点（Vertex)Vertex)。约定。约定V V表示顶点的有穷非空集表示顶点的有穷非空集合，合，VRVR表示两个顶点之间的关系的集合。表示两个顶点之间的关系的集合。弧弧（Arc）：表示两个顶点：表示两个顶点v和和w之间存在一之间存在一个关系，用个关系，用表示表示顶点顶点v到到w的一条弧的一条弧。且称且称v为为弧尾弧尾（Tail）或初始点，称）或初始点，称w为为弧头弧头（Head）或终
4、端点。此时的图称为或终端点。此时的图称为有向图有向图（Digraph）。）。其中，顶点偶对其中，顶点偶对的的v和和w之间是之间是有序有序的的。现在学习的是第5页，共28页无向图无向图(Undigraph)：若图关系集合中，顶若图关系集合中，顶点偶对点偶对的的v和和w之间是之间是无序无序的的，称图，称图G是无是无向图向图。若若属于属于VR，必有，必有属于属于VR，即，即VR是对称的。是对称的。那么用（那么用（v,w）代替这两个有序对，表示）代替这两个有序对，表示v和和w的一条的一条边边（Edge）。）。现在学习的是第6页，共28页如图如图7.1：设有向图：设有向图G1和无向图和无向图G2，形式化
5、定义，形式化定义分别是：分别是：G1=(V1，A1)V1=v1,v2,v3,v4A1=,G2=(V2，E2)V2=v1,v2,v3,v4,v5E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v1),(v3,v5)现在学习的是第7页，共28页V1V3V2V4V1V2V5V4V3图图7.1 图的示例图的示例(a)有向图有向图G1(b)无向图无向图G2(a)(b)现在学习的是第8页，共28页 完全无向图完全无向图：对于无向图，若图中顶点数为：对于无向图，若图中顶点数为n，用用e表示边的数目，则表示边的数目，则e 0，n(n-1)/2。具有。具有n(n-1)/2条边的无向
6、图称为完全无向图。条边的无向图称为完全无向图。完全无向图另外的定义是：完全无向图另外的定义是：对于无向图对于无向图G=(V，E)，若，若 vi，vj V，当，当vivj时，有时，有(vi,vj)E，即图中任意两个不同的顶点间都有，即图中任意两个不同的顶点间都有一条无向边，这样的无向图称为完全无向图。一条无向边，这样的无向图称为完全无向图。现在学习的是第9页，共28页完全有向图完全有向图：对于有向图，若图中顶点数为：对于有向图，若图中顶点数为n，用，用e表示弧的数目，则表示弧的数目，则e 0，n(n-1)。具有。具有n(n-1)条边的有向图称为完全有向图。条边的有向图称为完全有向图。完全有向图另
7、外的定义是：完全有向图另外的定义是：对于有向图对于有向图G=(V，E)，若，若 vi，vj V，当，当vi vj时，有时，有 E并且并且 E，即图中任，即图中任意两个不同的顶点间都有一条弧，这样的有向图意两个不同的顶点间都有一条弧，这样的有向图称为称为完全有向图完全有向图。现在学习的是第10页，共28页有很少边或弧的图（有很少边或弧的图（enn）的图称为）的图称为稀稀疏图疏图，反之称为，反之称为稠密图稠密图。权权(Weight)：与图的边和弧相关的数。权可：与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的距离或耗费。以表示从一个顶点到另一个顶点的距离或耗费。这种这种带权的图称为带权的图
8、称为网网。现在学习的是第11页，共28页 子图和生成子图子图和生成子图：设有图设有图G=(V，E)和和G=(V，E)，若，若V V且且E E，则称图，则称图G是是G的的子图子图；若；若V=V且且E E，则称图，则称图G是是G的一个的一个生成子图生成子图。P7.2现在学习的是第12页，共28页对于无向图对于无向图G=(V，E)，若边，若边(v,w)E，则，则称顶点称顶点v和和w 互为互为邻接点邻接点，即，即v和和w相邻接。边相邻接。边(v,w)依附依附(incident)于于顶点顶点v和和w，或者说，或者说(v,w)和和顶点顶点v和和w相关联相关联。图图G中中和和v相关联相关联的边的数目称为顶点
9、的边的数目称为顶点v的的度度(degree)，记为，记为TD(v)。例如例如无向图无向图G2。TD(V1)，TD(V2)，TD(V3)，TD(V4)，TD(V5)V1V2V5V4V3G2现在学习的是第13页，共28页对于有向图对于有向图G=(V，E)，若有向弧，若有向弧 E，则称顶点，则称顶点v“邻接到邻接到”顶点顶点w，顶点，顶点w“邻接自邻接自”顶点顶点v，弧，弧 与顶点与顶点v和和w“相关联相关联”。对有向图对有向图G=(V，E)，若，若 vi V，图，图G中中以以顶点顶点v作为尾或初始作为尾或初始的有向边的有向边(弧弧)的数目称为顶点的数目称为顶点v的的出度出度(Outdegree)，
10、记为，记为OD(v)；以以v作为头或作为头或终点终点的有向边的有向边(弧弧)的数目称为顶点的数目称为顶点v的的入度入度(Indegree)，记为，记为ID(v)。顶点。顶点v的的出度出度与与入度入度之之和称为和称为v的的度度，记为，记为TD(v)。即。即TD(v)=OD(v)+ID(v)现在学习的是第14页，共28页例如图例如图7.1所示的无向图。所示的无向图。OD(v1)，ID(,1)，TD(v1)；OD(v3)，ID(,3)，TD(v1)V1V3V2V4(G1)现在学习的是第15页，共28页 一般地一般地，如果顶点如果顶点vi在的度记为在的度记为TD(vi)，那，那么一个有么一个有n个顶点
11、，个顶点，e条边或弧的图，满足：条边或弧的图，满足：TD(vi)=2e现在学习的是第16页，共28页路径路径(Path)：对无向图对无向图G=(V，E)，若从顶，若从顶点点vi经过若干条边能到达经过若干条边能到达vj，称顶点，称顶点vi和和vj是是连通连通的，又称顶点的，又称顶点vi到到vj有有路径路径。对有向图对有向图G=(V，E)，从顶点，从顶点vi到到vj有有有向路有向路径径，指的是从顶点，指的是从顶点vi经过若干条有向边经过若干条有向边(弧弧)能到能到达达vj。现在学习的是第17页，共28页路径的长度路径的长度：路径上边或有向边路径上边或有向边(弧弧)的数目的数目称为该路径的长度。称为
12、该路径的长度。在一条路径中，若没有重复相同的顶点，该在一条路径中，若没有重复相同的顶点，该路径称为路径称为简单路径简单路径；第一个顶点和最后一个顶点；第一个顶点和最后一个顶点相同的路径称为相同的路径称为回路回路(环环)；在一个回路中，若除；在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现第一个与最后一个顶点外，其余顶点不重复出现的回路称为的回路称为简单回路简单回路(简单环简单环)。现在学习的是第18页，共28页 连通图、图的连通分量连通图、图的连通分量：对无向图：对无向图G=(V，E)，若，若 vi，vj V，又称顶点又称顶点vi到到vj有有路径路径，即即vi和和vj是连通的，则称
13、图是连通的，则称图G是是连通图连通图，否则称为，否则称为非非连通图连通图。若。若G是非连通图，则极大的连通子图称是非连通图，则极大的连通子图称为为G的的连通分量连通分量。例如例如图图7.1(b)中的中的G2就是一个连通图。再例就是一个连通图。再例如图如图7.3所示。所示。P159V1V2V5V4V3G2现在学习的是第19页，共28页对有向图对有向图G=(V，E)，若，若 vi，vj V，都有，都有以以vi为起点，为起点，vj 为终点以及以为终点以及以vj为起点，为起点，vi为终点为终点的有向路径，称图的有向路径，称图G是是强连通图强连通图，否则称为，否则称为非强非强连通图连通图。若。若G是非强
14、连通图，则极大的强连通子是非强连通图，则极大的强连通子图称为图称为G的的强连通分量强连通分量。“极大极大”的含义：指的是对子图再增加图的含义：指的是对子图再增加图G中中的其它顶点，子图就不再连通。的其它顶点，子图就不再连通。例如例如图图7.1(a)。V1V3V2V4(G1)V1V3V2V4强连通分量强连通分量现在学习的是第20页，共28页 生成树、生成森林生成树、生成森林：一个连通图：一个连通图(无向图无向图)的的生成树是一个极小连通子图，它生成树是一个极小连通子图，它含有图中全部含有图中全部n个顶点个顶点和只有足以构成一棵树的和只有足以构成一棵树的n-1条边条边，称为，称为图的图的生成树生成
15、树。如图如图7.5所示。所示。v1v3v2v4图图7-5 生成树生成树现在学习的是第21页，共28页关于无向图的生成树的几个结论：关于无向图的生成树的几个结论：一棵有一棵有n个顶点的生成树有且仅有个顶点的生成树有且仅有n-1条边；条边；如果一个图有如果一个图有n个顶点和小于个顶点和小于n-1条边，则是非条边，则是非连通图连通图；如果多于如果多于n-1条边，则一定有环；条边，则一定有环；有有n-1条边的图不一定是生成树。条边的图不一定是生成树。v1v3v2v4图图7-5 生成树生成树现在学习的是第22页，共28页如果一个有向图恰有一个顶点的入度为如果一个有向图恰有一个顶点的入度为0，其余，其余顶
16、点的入度均为顶点的入度均为1，则是一棵有向树，如图，则是一棵有向树，如图7-3所示。所示。有向图的生成森林是这样一个子图，由若干有向图的生成森林是这样一个子图，由若干棵有向树组成，含有图中全部顶点。棵有向树组成，含有图中全部顶点。网：每个边网：每个边(或弧或弧)都附加一个权值的图，称为带都附加一个权值的图，称为带权图。带权的连通图权图。带权的连通图(包括弱连通的有向图包括弱连通的有向图)称为网或称为网或网络。如图网络。如图7-4所示。所示。图图7-3 有向图及其生成森林有向图及其生成森林abcdedce(a)有向图有向图(b)生成森林生成森林acbcb354126abcde3图图7-4 带权有
17、向图带权有向图现在学习的是第23页，共28页7.1.2 图的抽象数据类型定义图的抽象数据类型定义图的抽象数据类型定义如下：图的抽象数据类型定义如下：ADT Graph数据对象数据对象V：具有相同特性的数据元素的集合，：具有相同特性的数据元素的集合，称为顶点集。称为顶点集。数据关系数据关系R：R=VRVR=|v,w V且且P(v,w)，表示表示 从从v到到w的弧，的弧，P(v,w)定义了弧定义了弧的信息的信息 现在学习的是第24页，共28页基本操作基本操作P：CreateGraph(&G,V,VR)：图的创建操作。图的创建操作。初始条件：无。初始条件：无。操作结果：按操作结果：按V和和VR的定义
18、构造树的定义构造树G。GetVex(G,v)：求图中的顶点求图中的顶点v的值。的值。初始条件：图初始条件：图G存在，存在，v是图中的一个顶点。是图中的一个顶点。操作结果：返回操作结果：返回v的值。的值。现在学习的是第25页，共28页LocateVex(G,u);初始条件：图初始条件：图G存在，存在，u和和G中顶点有相同特征。中顶点有相同特征。操作结果：若操作结果：若G中存在顶点中存在顶点u，则返回该顶点在，则返回该顶点在 图中图中“位置位置”；否则返回其它信息；否则返回其它信息PutVex(&G,v,value);初始条件：图初始条件：图G存在，存在，v是是G中某个顶点。中某个顶点。操作结果：
19、操作结果：对对 v 赋值赋值value。ADT Graph 详见详见p156157。现在学习的是第26页，共28页习 题 七 分析并回答下列问题：分析并回答下列问题：图中顶点的度之和与边数之和的关系图中顶点的度之和与边数之和的关系?有向图中顶点的入度之和与出度之和的关有向图中顶点的入度之和与出度之和的关系系?具有具有n个顶点的无向图，至少应有多少条个顶点的无向图，至少应有多少条边才能确保是一个连通图边才能确保是一个连通图?具有具有n个顶点的有向图，至少应有多少条个顶点的有向图，至少应有多少条弧才能确保是强连通图的弧才能确保是强连通图的?为什么为什么?现在学习的是第27页，共28页 设一有向图设一有向图G=(V,E)，其中，其中V=a,b,c,d,e，E=,请画出该有向图，并求各顶点的入度和出请画出该有向图，并求各顶点的入度和出度。度。现在学习的是第28页，共28页