图的基本概念及基本操作.ppt
( 4.5 )《图的基本概念及基本操作.ppt》由会员分享，可在线阅读，更多相关《图的基本概念及基本操作.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、数据结构与算法-第十八讲北方民族大学计算机科学与工程学院王伦津 研究员图的基本概念及基本操作图的基本概念及基本操作118、图的基本概念、图的基本操作，、图的基本概念、图的基本操作，以及图的对象抽象模型以及图的对象抽象模型掌握图的定义、结点、边、弧、邻接、关掌握图的定义、结点、边、弧、邻接、关联、度、权、路径、子图、连通等有关术联、度、权、路径、子图、连通等有关术语及其图的检索、插入、删除、求邻接点、语及其图的检索、插入、删除、求邻接点、关联边、图的遍历等基本操作关联边、图的遍历等基本操作，了解图结，了解图结点抽象模型、图的边对象抽象模型和图对点抽象模型、图的边对象抽象模型和图对象的抽象模型象的
2、抽象模型2目目录录18.1图结构图结构18.2图的基本概念图的基本概念18.2.1图的概念图的概念18.2.2图的基本操作图的基本操作18.3图的对象抽象模型图的对象抽象模型18.3.1图结点抽象模型图结点抽象模型18.3.2图的边对象抽象模型图的边对象抽象模型18.3.3图抽象对象模型图抽象对象模型3这里的图，有时也称网络，是指由若干个结点与若这里的图，有时也称网络，是指由若干个结点与若干条边构成的结构，其中每个结点可有干条边构成的结构，其中每个结点可有多个前趋和多个前趋和多个后继，多个后继，结点是一些具体对象的抽象，而边是对结点是一些具体对象的抽象，而边是对象间的关系的抽象。值得注意的是，
3、与一般意义下象间的关系的抽象。值得注意的是，与一般意义下的图不同，这里的图只涉及图的拓扑结构，与图的的图不同，这里的图只涉及图的拓扑结构，与图的几何性质无关。图论重点讨论图的数学性质，而这几何性质无关。图论重点讨论图的数学性质，而这里的重点是图结点间的关系以及图的存贮结构与基里的重点是图结点间的关系以及图的存贮结构与基本操作的实现。图是一种复杂的非线性结构，它有本操作的实现。图是一种复杂的非线性结构，它有极强的表达能力，现实世界中许多问题均可用图结极强的表达能力，现实世界中许多问题均可用图结构描述。构描述。18.1图结构图结构418.2.1图的概念图的概念1图图图图(Graph)是是由由若若干
4、干个个结结点点和和若若干干条条边边构构成成的的结结构构，每每个个结结点点具具有有任任意意多多个个前前驱驱和和后后继继。这这种种结结构构的含意为：的含意为：结点集合结点集合V：结点代表对象：结点代表对象Vertex边边集集合合R：两两结结点点之之间间的的边边表表示示它它们们代代表表的的对对象象之间的关系之间的关系18.2图的基本概念图的基本概念5形式化地讲，图是形为形式化地讲，图是形为G=(V,R)的数据结构，其中，的数据结构，其中，V=x|x属于数据对象属于数据对象R=VRVR=|p(x,y)xVyV这这里里，p(x,y)是是V上上的的一一个个谓谓词词，p(x,y)为为真真当当且仅当且仅当x与
5、与y存在问题世界中的关系。存在问题世界中的关系。在具体应用中，结点与边要被赋予具体的含意。如在具体应用中，结点与边要被赋予具体的含意。如结点代表城市，而边代表城市之间的行程。结点代表城市，而边代表城市之间的行程。6若二元关系若二元关系VR中的每个型如中的每个型如的的成员中的成员中的x与与y是次序无关的，则称该图为无是次序无关的，则称该图为无向图向图(undirecyedgraph)，否则称为有向图，否则称为有向图(directedgraph)。无向图也可以看作。无向图也可以看作VR对称的图，即对任意对称的图，即对任意x与与y，若有，若有VR，则必有，则必有VR。对无向图，我们用。对无向图，我们
6、用(x,y)表示表示。2有向有向/无向图无向图73结点、边、弧结点、边、弧图中的数据元素称为结点（或顶点）图中的数据元素称为结点（或顶点）(vertice/node/point)，有时为了强调，对有向图，有时为了强调，对有向图，称称为弧为弧(arc)，x与与y分别为弧尾与弧头，或始分别为弧尾与弧头，或始点与终点，称点与终点，称y为为x的出点的出点/可达邻接点，称可达邻接点，称x为为y的的入点称入点称为为x的出边的出边/出弧，出弧，为为y的入边的入边/入弧。对无向图，入弧。对无向图，泛称泛称为边为边(edge)。在讨论。在讨论图中，为了方便，一般给图中，为了方便，一般给结点编号，用它们的编号代表
7、结点编号，用它们的编号代表它们。结点编号一般用自然数。它们。结点编号一般用自然数。1 12 25 54 43 3a ab bc cd d(a)有向图(b)无向图图181图示例8 例例18 1设设有有两两个个二二元元组组G1=(V1,R1)与与G2=(V2,R2)，其其中，中，V1=1,2,3,4,5R1=VR1VR1=,V2=a,b,c,dR2=VR2VR2=(a,b),(a,d),(b,d),(d,c)显然，它们不满足线性结构、广义表和树的定义，而显然，它们不满足线性结构、广义表和树的定义，而满足图的定义。满足图的定义。1 125 54 43 3a ab bc cd d94邻接、关联邻接、关
8、联对图中任意结点对图中任意结点x与与y，若它们之间存在边（即有，若它们之间存在边（即有，或，或），则称），则称x与与y邻接邻接(adjacent)，它们互为邻接点。同时称，它们互为邻接点。同时称x或或y与边与边（或（或或或(x,y)）关联）关联(incident)。5度度对任一结点对任一结点x，称以它为头的弧的个数为它的入度，称以它为头的弧的个数为它的入度(Indegree)；称以它为尾的弧的个数为它的；称以它为尾的弧的个数为它的出度出度(outdegree)；称它的入度与；称它的入度与出度之和为它的出度之和为它的度度(degree)。对无向图，无出度入度之分，直接。对无向图，无出度入度之分，
9、直接称与它关联的边的个数为它的度。称与它关联的边的个数为它的度。例如，图例如，图6-1(a)中的结点中的结点1的出的出度与入度都为度与入度都为2，结点，结点3的出度入度分别为的出度入度分别为1和和0，(b)中的结点中的结点a、b、度均为、度均为2，而，而d的度为的度为3 3，c的度为的度为1。106权权权权(Weight)与哈夫曼树中的概念相同，即权是一个数值量，与哈夫曼树中的概念相同，即权是一个数值量，是某些信息的数字化抽象。权分边权与结点权，分别是边与结点是某些信息的数字化抽象。权分边权与结点权，分别是边与结点的问题世界所关心的信息的数值化表示。例如，若结点代表城市，的问题世界所关心的信息
10、的数值化表示。例如，若结点代表城市，则边权可代表城市之间的交通费用。则边权可代表城市之间的交通费用。7路径（通路）路径（通路）对有向图，若存在弧序列对有向图，若存在弧序列，且且n1，则称从，则称从x0到到xn有通路（路径）有通路（路径）(Path)。上列序列称。上列序列称为为x0到到xn的路径。该路径也可表示为的路径。该路径也可表示为(x0,x1,xn)11对无向图，若有边序列对无向图，若有边序列(x0,x1)，(x1,x2)，(xn-1,xn)且且n1，则称，则称x0与与xn之间有路径（通路），该路径可用上列之间有路径（通路），该路径可用上列边序列表示，亦可用下列结点序列表示边序列表示，亦可
11、用下列结点序列表示(x0,x1,xn)路径中边的数目称为路径中边的数目称为路径长路径长。若若x0=xn，则称相应的路径为，则称相应的路径为回路回路/环路环路(loop)。若在路径若在路径(x0,x1,xn)中，除中，除x0与与xn外，任意其它外，任意其它结点均不相同，则称该路径为结点均不相同，则称该路径为简单路径简单路径(SimplePath)。起。起点与终点重合的简单路径称为点与终点重合的简单路径称为简单回路简单回路(SimpleLoop)。U U显然，简单路径中不含回路。显然，简单路径中不含回路。128子图子图/生成图生成图若若某某图图G的的结结点点集集合合与与边边集集合合分分别别是是另另
12、一一图图G的的结结点点集集合和边集合的子集，则称合和边集合的子集，则称G为为G的的子图子图(Subgraph)。设设有有两两个个图图G与与G，若若它它们们的的结结点点集集合合相相同同，但但G的的边边集集合合是是G的的边边集集合合的的子子集集，则则称称G是是G的的生生成成图图(SpanningGraph)。显然，生成图一定是子图，但反之未必。显然，生成图一定是子图，但反之未必。1310生成树生成树无无回回路路的的连连通通的的无无向向图图的的生生成成图图，称称为为该该无无向向图图的的生生成成树树(SpanningTree)。9连通连通若图中任意两结点若图中任意两结点x和和y，或，或x到到y有通路，
13、或有通路，或y到到x有通路，有通路，则称该图是则称该图是（弱）连通的（弱）连通的(Connected)；若；若x到到y有通路，且有通路，且y到到x有通路，则称该图是有通路，则称该图是强连通的强连通的(StronglyConnected)。若图。若图中某子图是连通的，则称该子图为一个中某子图是连通的，则称该子图为一个连通分量连通分量(ConnectedComponent)。若。若G的某子图的某子图G是连通的，并且，若将是连通的，并且，若将G中任中任意其他结点及其任意相关联的边加入到意其他结点及其任意相关联的边加入到G，都会导致，都会导致G不连通，不连通，那么称那么称G是一个是一个极大连通分量（极
14、大连通分量（MaximumConnectedComponent)。显然极大连通分量不唯一。显然极大连通分量不唯一。14证：先归纳证明，边的个数不能少于结点数减证：先归纳证明，边的个数不能少于结点数减1（否（否则图就不连通了）。再证明，边数必不大于结点数减则图就不连通了）。再证明，边数必不大于结点数减1，因为若有，因为若有n个结点，则有个结点，则有(n-1)条边就使这条边就使这n个结个结点连通了，若再添加一条边，则这条边关联的两结点点连通了，若再添加一条边，则这条边关联的两结点间的路径就多于间的路径就多于1条了，从而构成回路。综合这两个条了，从而构成回路。综合这两个方面，就证得了本定理。方面，就
15、证得了本定理。参见参见p9图图定理定理7 1生成树中边的个数为结点个数生成树中边的个数为结点个数减减1.1518.2.2图的基本操作图的基本操作 图是一种与具体应用密切相关的结构，有关它的基本图是一种与具体应用密切相关的结构，有关它的基本操作也往往随应用不同而出入很大操作也往往随应用不同而出入很大.检索：检索：按结点编号或内容检索结点位置按结点编号或内容检索结点位置按边的两顶点检索边按边的两顶点检索边插入：插入：插入结点插入结点插入边插入边删除：删除：删除结点及与其关联的边删除结点及与其关联的边删除边删除边16求邻接点、关联边求邻接点、关联边求度（入度与出度）求度（入度与出度）求路径求路径图的
16、遍历图的遍历求子图求子图求生成图求生成图求连通分量求连通分量求拓扑序列（有向图）求拓扑序列（有向图）求（最小）生成树求（最小）生成树求关键路径求关键路径求最短路径求最短路径1718.3 18.3 图的对象抽象模型图的对象抽象模型 这里，我们仅从逻辑关系出发，考虑这里，我们仅从逻辑关系出发，考虑图结点和整个图对象应具有的性质。由图结点和整个图对象应具有的性质。由于图结点的关系不象其他结构中结点那于图结点的关系不象其他结构中结点那样有限制，所以它的抽象结构比较复杂。样有限制，所以它的抽象结构比较复杂。18 为为了了后后面面的的使使用用，首首先先定定义义一一个个枚枚举举类类型型和常量：和常量：enu
17、mTTraverseModeDFS,WFS;/定义枚举类型，表示图遍历方式定义枚举类型，表示图遍历方式 constCNST_NumNodes=100;/定义常量，表示最大结点个数。实际定义常量，表示最大结点个数。实际结点个数可以小于该数结点个数可以小于该数1918.3.1图结点抽象模型图结点抽象模型 图结点抽象模型重点是描述图结图结点抽象模型重点是描述图结点的内容，隐蔽具体的图结点的结构。点的内容，隐蔽具体的图结点的结构。所以，图结点对象模型中，重点是关所以，图结点对象模型中，重点是关于结点信息的于结点信息的Get和和Set类操作。类操作。下面是图结点的描述：下面是图结点的描述：20templ
18、ate/结点内容的类型（可变类型）结点内容的类型（可变类型）structTGraphNode0/图结点类图结点类longno;/图结点的编号图结点的编号floatweight;/结点的权结点的权TEleminfo;/图结点的内容图结点的内容virtuallongGetNo()returnno;virtualvoidSetNo(longmNo)no=mNo;virtualTElem&GetElem()returninfo;virtualTElem&SetElem(TElem&e)info=e;returninfo;virtualfloatGetWeight()returnweight;virtu
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 基本概念 基本 操作
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内