图的基本概念及基本操作幻灯片.ppt

《图的基本概念及基本操作幻灯片.ppt》由会员分享，可在线阅读，更多相关《图的基本概念及基本操作幻灯片.ppt（36页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1第1页，共36页，编辑于2022年，星期五18、图的基本概念、图的基本操作，、图的基本概念、图的基本操作，以及图的对象抽象模型以及图的对象抽象模型掌握图的定义、结点、边、弧、邻接、关掌握图的定义、结点、边、弧、邻接、关联、度、权、路径、子图、连通等有关术联、度、权、路径、子图、连通等有关术语及其图的检索、插入、删除、求邻接点、语及其图的检索、插入、删除、求邻接点、关联边、图的遍历等基本操作关联边、图的遍历等基本操作，了解图结，了解图结点抽象模型、图的边对象抽象模型和图对点抽象模型、图的边对象抽象模型和图对象的抽象模型象的抽象模型2第2页，共36页，编辑于2022年，星期五目目录录18.1图结

2、构图结构18.2图的基本概念图的基本概念18.2.1图的概念图的概念18.2.2图的基本操作图的基本操作18.3图的对象抽象模型图的对象抽象模型18.3.1图结点抽象模型图结点抽象模型18.3.2图的边对象抽象模型图的边对象抽象模型18.3.3图抽象对象模型图抽象对象模型3第3页，共36页，编辑于2022年，星期五这里的图，有时也称网络，是指由若干个结点与若干这里的图，有时也称网络，是指由若干个结点与若干条边构成的结构，其中每个结点可有条边构成的结构，其中每个结点可有多个前趋和多个多个前趋和多个后继，后继，结点是一些具体对象的抽象，而边是对象间的关系的结点是一些具体对象的抽象，而边是对象间的关

3、系的抽象。值得注意的是，与一般意义下的图不同，这里的图只抽象。值得注意的是，与一般意义下的图不同，这里的图只涉及图的拓扑结构，与图的几何性质无关。图论重点讨论图涉及图的拓扑结构，与图的几何性质无关。图论重点讨论图的数学性质，而这里的重点是图结点间的关系以及图的存贮的数学性质，而这里的重点是图结点间的关系以及图的存贮结构与基本操作的实现。图是一种复杂的非线性结构，它有结构与基本操作的实现。图是一种复杂的非线性结构，它有极强的表达能力，现实世界中许多问题均可用图结构描述。极强的表达能力，现实世界中许多问题均可用图结构描述。18.1图结构图结构4第4页，共36页，编辑于2022年，星期五 18.2.

4、1 图的概念图的概念1图图 图图(Graph)是是由由若若干干个个结结点点和和若若干干条条边边构构成成的的结结构构，每个结点具有任意多个前驱和后继。这种结构的含意为：每个结点具有任意多个前驱和后继。这种结构的含意为：结点集合结点集合V：结点代表对象：结点代表对象Vertex 边边集集合合R：两两结结点点之之间间的的边边表表示示它它们们代代表表的的对对象象之之间间的关系的关系 18.2图的基本概念图的基本概念5第5页，共36页，编辑于2022年，星期五 形式化地讲，图是形为形式化地讲，图是形为 G=(V,R)的数据结构，其中，的数据结构，其中，V=x|x属于数据对象属于数据对象 R=VR VR=

5、|p(x,y)xVyV 这这里里，p(x,y)是是V上上的的一一个个谓谓词词，p(x,y)为为真真当当且且仅仅当当x与与y存在问题世界中的关系。存在问题世界中的关系。在具体应用中，结点与边要被赋予具体的含意。如结在具体应用中，结点与边要被赋予具体的含意。如结点代表城市，而边代表城市之间的行程。点代表城市，而边代表城市之间的行程。6第6页，共36页，编辑于2022年，星期五若二元关系若二元关系VR中的每个型如中的每个型如的成的成员中的员中的x与与y是次序无关的，则称该图为无向图是次序无关的，则称该图为无向图(undirecyedgraph)，否则称为有向图，否则称为有向图(directedgra

6、ph)。无向图也可以看作。无向图也可以看作VR对称对称的图，即对任意的图，即对任意x与与y，若有，若有 VR，则必有，则必有 VR。对无向图，我们用。对无向图，我们用(x,y)表示表示。2有向有向/无向图无向图7第7页，共36页，编辑于2022年，星期五 3结点、边、弧结点、边、弧 图中的数据元素称为结点（或顶点）图中的数据元素称为结点（或顶点）(vertice/node/point)，有时为了强调，对有向图，称，有时为了强调，对有向图，称为弧为弧(arc)，x与与y分别为弧尾与弧头，或始点与终点，称分别为弧尾与弧头，或始点与终点，称y为为x的出点的出点/可可达邻接点，称达邻接点，称x为为y的

7、入点称的入点称为为x的出边的出边/出弧，出弧，为为y的入边的入边/入弧。对无向图，入弧。对无向图，泛称泛称为边为边(edge)。在讨论。在讨论图中，为了方便，一般给图中，为了方便，一般给结点编号，用它们的编号代表结点编号，用它们的编号代表它们。结点编号一般用自然数。它们。结点编号一般用自然数。1 12 25 54 43 3a a b bc cd d(a)有向图(b)无向图图 181 图示例8第8页，共36页，编辑于2022年，星期五 例例 181设有两个二元组设有两个二元组G1=(V1,R1)与与G2=(V2,R2)，其中，其中，V1=1,2,3,4,5 R1=VR1 VR1=,V2=a,b,

8、c,d R2=VR2 VR2=(a,b),(a,d),(b,d),(d,c)显然，它们不满足线性结构、广义表和树的定义，而满足图显然，它们不满足线性结构、广义表和树的定义，而满足图的定义。的定义。1 125 54 43 3a a b bc cd d9第9页，共36页，编辑于2022年，星期五4邻接、关联邻接、关联 对图中任意结点对图中任意结点x与与y，若它们之间存在边（即有，若它们之间存在边（即有，或，或），），则称则称x与与y邻接邻接(adjacent)，它们互为邻接点。同时称，它们互为邻接点。同时称x或或y与边与边（或（或或或(x,y)）关联）关联(incident)。5度度 对任一结点对

9、任一结点x，称以它为头的弧的个数为它的入度，称以它为头的弧的个数为它的入度(In degree)；称以；称以它为尾的弧的个数为它的它为尾的弧的个数为它的出度出度(out degree)；称它的入度与出度之和为；称它的入度与出度之和为它的它的度度(degree)。对无向图，无出度入度之分，直接称与它关联的边的个。对无向图，无出度入度之分，直接称与它关联的边的个数为它的度。数为它的度。例如，图例如，图6-1(a)中的结点中的结点1的出度与入度都为的出度与入度都为2，结点，结点3的出的出度入度分别为度入度分别为1和和0，(b)中的结点中的结点a、b、度均为、度均为2，而，而d的度为的度为3 3，c的

10、度的度为为1。10第10页，共36页，编辑于2022年，星期五6权权权权(Weight)与哈夫曼树中的概念相同，即权是一个数值量，是某与哈夫曼树中的概念相同，即权是一个数值量，是某些信息的数字化抽象。权分边权与结点权，分别是边与结点的问题世些信息的数字化抽象。权分边权与结点权，分别是边与结点的问题世界所关心的信息的数值化表示。例如，若结点代表城市，则边权可代界所关心的信息的数值化表示。例如，若结点代表城市，则边权可代表城市之间的交通费用。表城市之间的交通费用。7路径（通路）路径（通路）对有向图，若存在弧序列对有向图，若存在弧序列，且且n1，则称从，则称从x0到到xn有通路（路径）有通路（路径）

11、(Path)。上列序列称为。上列序列称为x0到到xn的路径。该路径也可表示为的路径。该路径也可表示为(x0,x1,xn)11第11页，共36页，编辑于2022年，星期五对无向图，若有边序列对无向图，若有边序列 (x0,x1)，(x1,x2)，(xn-1,xn)且且n1，则称，则称x0与与xn之间有路径（通路），该路径可用上列边序之间有路径（通路），该路径可用上列边序列表示，亦可用下列结点序列表示列表示，亦可用下列结点序列表示(x0,x1,xn)路径中边的数目称为路径中边的数目称为路径长路径长。若若x0=xn，则称相应的路径为，则称相应的路径为回路回路/环路环路(loop)。若在路径若在路径(x

12、0,x1,xn)中，除中，除x0与与xn外，任意其它结点均不相外，任意其它结点均不相同，则称该路径为同，则称该路径为简单路径简单路径(Simple Path)。起点与终点重合的简。起点与终点重合的简单路径称为单路径称为简单回路简单回路(Simple Loop)。UU 显然，简单路径中不含回路。显然，简单路径中不含回路。12第12页，共36页，编辑于2022年，星期五8子图子图/生成图生成图 若若某某图图G的的结结点点集集合合与与边边集集合合分分别别是是另另一一图图G的的结结点点集集合合和和边集合的子集，则称边集合的子集，则称G为为G的的子图子图(Subgraph)。设设有有两两个个图图G与与G

13、，若若它它们们的的结结点点集集合合相相同同，但但G的的边边集集合合是是G的边集合的子集，则称的边集合的子集，则称G是是G的的生成图生成图(Spanning Graph)。显然，生成图一定是子图，但反之未必。显然，生成图一定是子图，但反之未必。13第13页，共36页，编辑于2022年，星期五10生成树生成树 无无回回路路的的连连通通的的无无向向图图的的生生成成图图，称称为为该该无无向向图图的的生生成成树树(SpanningTree)。9连通连通若图中任意两结点若图中任意两结点x和和y，或，或x到到y有通路，或有通路，或y到到x有通路，则称该有通路，则称该图是图是（弱）连通的（弱）连通的(Conn

14、ected)；若；若x到到y有通路，且有通路，且y到到x有通路，则称有通路，则称该图是该图是强连通的强连通的(StronglyConnected)。若图中某子图是连通的，则称。若图中某子图是连通的，则称该子图为一个该子图为一个连通分量连通分量(ConnectedComponent)。若。若G的某子图的某子图G是是连通的，并且，若将连通的，并且，若将G中任意其他结点及其任意相关联的边加入到中任意其他结点及其任意相关联的边加入到G，都会导致，都会导致G不连通，那么称不连通，那么称G是一个是一个极大连通分量（极大连通分量（MaximumConnectedComponent)。显然极大连通分量不唯一。

15、显然极大连通分量不唯一。14第14页，共36页，编辑于2022年，星期五证：先归纳证明，边的个数不能少于结点数减证：先归纳证明，边的个数不能少于结点数减1（否则图（否则图就不连通了）。再证明，边数必不大于结点数减就不连通了）。再证明，边数必不大于结点数减1，因为若有，因为若有n个结点，则有个结点，则有(n-1)条边就使这条边就使这n个结点连通了，若再添个结点连通了，若再添加一条边，则这条边关联的两结点间的路径就多于加一条边，则这条边关联的两结点间的路径就多于1条条了，从而构成回路。综合这两个方面，就证得了本定理。了，从而构成回路。综合这两个方面，就证得了本定理。参参见见p9图图定理定理7 1生

16、成树中边的个数为结点个数减生成树中边的个数为结点个数减1.15第15页，共36页，编辑于2022年，星期五18.2.2 图的基本操作图的基本操作 图是一种与具体应用密切相关的结构，有关它的基本操作图是一种与具体应用密切相关的结构，有关它的基本操作也往往随应用不同而出入很大也往往随应用不同而出入很大.检索：检索：按结点编号或内容检索结点位置按结点编号或内容检索结点位置 按边的两顶点检索边按边的两顶点检索边 插入：插入：插入结点插入结点 插入边插入边 删除：删除：删除结点及与其关联的边删除结点及与其关联的边 删除边删除边16第16页，共36页，编辑于2022年，星期五 求邻接点、关联边求邻接点、关

17、联边 求度（入度与出度）求度（入度与出度）求路径求路径 图的遍历图的遍历 求子图求子图 求生成图求生成图 求连通分量求连通分量 求拓扑序列（有向图）求拓扑序列（有向图）求（最小）生成树求（最小）生成树 求关键路径求关键路径 求最短路径求最短路径17第17页，共36页，编辑于2022年，星期五18.3 18.3 图的对象抽象模型图的对象抽象模型 这里，我们仅从逻辑关系出发，考虑图结这里，我们仅从逻辑关系出发，考虑图结点和整个图对象应具有的性质。由于图结点点和整个图对象应具有的性质。由于图结点的关系不象其他结构中结点那样有限制，所的关系不象其他结构中结点那样有限制，所以它的抽象结构比较复杂。以它的

18、抽象结构比较复杂。18第18页，共36页，编辑于2022年，星期五 为为了了后后面面的的使使用用，首首先先定定义义一一个个枚枚举举类类型型和和常常量：量：enumTTraverseModeDFS,WFS;/定义枚举类型，表示图遍历方式定义枚举类型，表示图遍历方式 constCNST_NumNodes=100;/定义常量，表示最大结点个数。实际结点定义常量，表示最大结点个数。实际结点个数可以小于该数个数可以小于该数19第19页，共36页，编辑于2022年，星期五18.3.1 图结点抽象模型图结点抽象模型 图结点抽象模型重点是描述图结点的图结点抽象模型重点是描述图结点的内容，隐蔽具体的图结点的结构

19、。所以，内容，隐蔽具体的图结点的结构。所以，图结点对象模型中，重点是关于结点信图结点对象模型中，重点是关于结点信息的息的Get和和Set类操作。类操作。下面是图结点的描述：下面是图结点的描述：20第20页，共36页，编辑于2022年，星期五template/结点内容的类型（可变类型）结点内容的类型（可变类型）structTGraphNode0/图结点类图结点类longno;/图结点的编号图结点的编号floatweight;/结点的权结点的权TEleminfo;/图结点的内容图结点的内容virtuallongGetNo()returnno;virtualvoidSetNo(longmNo)no=

20、mNo;virtualTElem&GetElem()returninfo;virtualTElem&SetElem(TElem&e)info=e;returninfo;virtualfloatGetWeight()returnweight;virtualfloatSetWeight(TElem&w)weight=w;returnweight;21第21页，共36页，编辑于2022年，星期五 该该类类的的各各基基本本操操作作都都已已在在类类定定义义中中实实现现，所所以以已已不不属属于于抽抽象象类类，但但其其在在整整个个图图类类中中，扮扮演演抽抽象象类类的的作作用。该类中主要成员说明如下：用。该类

21、中主要成员说明如下：GetNo()：返回本结点的编号。：返回本结点的编号。SetNo(longmNo)：将：将mNo做为本结点的编号值。做为本结点的编号值。GetElem()：返回本结点的值。：返回本结点的值。SetElem(TELem&e)：将：将e做为本结点做为本结点的元素值。的元素值。GetWeight()：返回本结点的权值。：返回本结点的权值。SetWeight(TELem&w)：将：将w做为本结点的权值。做为本结点的权值。22第22页，共36页，编辑于2022年，星期五18.3.2 图的边对象抽象模型图的边对象抽象模型 边实质上就是元素间的关系。在图中，边不仅仅表边实质上就是元素间的

22、关系。在图中，边不仅仅表达的是逻辑关系，它本身也可以具有其他的属性，如达的是逻辑关系，它本身也可以具有其他的属性，如权值。因此，有必要专门建立针对图的边的对象模型。权值。因此，有必要专门建立针对图的边的对象模型。与结点类与结点类TgraphNode0类类似似，该类的成员函数也都实，该类的成员函数也都实现，在语法上不属于抽象类。现，在语法上不属于抽象类。23第23页，共36页，编辑于2022年，星期五templatestructTGraphEdge0/图边抽象类图边抽象类longstartNo,endNo;/边的起点和终点边的起点和终点floatweight;/边权边权TEleminfo;/边的

23、内容边的内容virtualTElem&GetElem()returninfo;/读边内容读边内容virtualTElem&SetElem(TElem&e)info=e;returninfo;/置边置边 virtualfloatGetWeight()returnweight;/读边权读边权virtualfloatSetWeight(TElem&w)weight=w;returnweight;/置边权置边权virtuallongGetStartNo()returnstartNo;/读边的起点编号读边的起点编号virtuallongGetEndNo()returnendNo;/读边的终点编号读边的终

24、点编号virtualvoidSetStartNo(longmNo)startNo=mNo;/置边的起点编置边的起点编 virtualvoidSetEndNo(longmNo)endNo=mNo;/置边的终点编号置边的终点编号;24第24页，共36页，编辑于2022年，星期五18.3.3 图抽象对象模型图抽象对象模型 图抽象模型重点是定义针对图的整体结构的操图抽象模型重点是定义针对图的整体结构的操作。根据前面分析，图的整体方面的操作主要有遍作。根据前面分析，图的整体方面的操作主要有遍历、查找、求路径、求生成树、求拓扑序列（有向历、查找、求路径、求生成树、求拓扑序列（有向图）、求关键路径、求最短路

25、径、求最小生成树等。图）、求关键路径、求最短路径、求最小生成树等。下面是具体的抽象模型。下面是具体的抽象模型。25第25页，共36页，编辑于2022年，星期五template /用到两个可变类型，分别是图结点用到两个可变类型，分别是图结点内容和边内容内容和边内容class TGraph0/图抽象类图抽象类 public:long numNodes;virtual long GetNodeNo(TGraphNode0*pNode);virtual TGraphNode0*GetNodeAddress(long nodeNo);virtual TGraphNode0*GetSucc(TGraphN

26、ode0 *pNode,long sucNo)=0;virtual TGraphNode0*GetPrior(TGraphNode0 *pNode,long preNo)=0;virtual TGraphNode0*SetSucc(TGraphNode0 *pNode,long sucNo,TGraphNode0*pNode)=0;virtual TGraphNode0*SetPrior(TGraphNode0 *pNode,long preNo,TGraphNode0*pNode)=0;26第26页，共36页，编辑于2022年，星期五virtual TGraphEdge0*GetSuccEd

27、ge(TGraphNode0 *pNode,long sucNo)=0;virtual TGraphEdge0*GetPriorEdge(TGraphNode0 *pNode,long preNo)=0;virtual long GetInDegree(TGraphNode0*pNode)=0;virtual long GetOutDegree(TGraphNode0*pNode)=0;virtual long Cluster(long v0,long*nos,TTraverseMode tm)=0;virtual long GetNumNodes()return numNodes;virtu

28、al TGraphNode0*AddNode(long mNo,TElem&nodeInfo)=0;virtual TGraphEdge0*AddEdge(long startNo,long endNo,TEdgeElem *pee=NULL)=0;virtual TGraphNode0*DeleteNode(long mNo)=0;virtual TGraphEdge0*DeleteEdge(long startNo,long endNo)=0;virtual long Cluster(TGraphNode0*pStartNode,TElem*e,TTraverseMode tm)=0;27

29、第27页，共36页，编辑于2022年，星期五 virtual long Cluster(TGraphNode0*pStartNode,TGraphNode0*Nodes,TTraverseMode tm)=0;virtual TGraphNode0*Locate(long nNo)=0;virtual TGraphEdge0*Locate(long startNo,long endNo)=0;virtual TGraphNode0*Locate(TElem&e,TTraverseMode tm,long sn=1)=0;virtual long GetPath(long startNo,lon

30、g endNo,long sn,long*pathNodeNo)=0;virtual long GetPath(long startNo,long endNo,long sn,TGraphNode0*pathNode)=0;virtual long GetPathShortest(long startNo,TDijkPath *path)=0;virtual long GetPathShortest(long*path)=0;28第28页，共36页，编辑于2022年，星期五 其中主要成员说明如下。其中主要成员说明如下。GetNodeNo(TGraphNode0*pNode)：返回地址为：返回地

31、址为pNode的结点的结点的编号。的编号。GetNodeAddress(long nodeNo)：返回编号为：返回编号为nodeNo的结点的地址。的结点的地址。有有了了这这两两个个函函数数，就就可可以以自自由由地地由由结结点点的的编编号号，求求得得其其地地址址，或或反反过来。过来。GetSucc(longnodeNo,longsucNo)：返返回回编编号号为为nodeNo的的结结点的第点的第sucNo个后继结点的地址。个后继结点的地址。GetPrior(longnodeNo,longpreNo)：返返回回返返回回编编号号为为nodeNo的的结点的第结点的第preNo个前驱结点的地址。个前驱结点

32、的地址。SetSucc(longnodeNo,longsucNo,TGraphNode*pNode)：将编号为将编号为nodeNo的结点设置为本结点的第的结点设置为本结点的第sucNo个后继。个后继。29第29页，共36页，编辑于2022年，星期五SetProir(longnodeNo,longpreNo,TGraphNode*pNode)：将编号为将编号为nodeNo的结点设置为本结点的第的结点设置为本结点的第preNo个前驱。个前驱。GetSuccEdge(longnodeNo,longsucNo)：返回编号为：返回编号为nodeNo的结点的第的结点的第sucNo个结点的地址。：个结点的地

33、址。：和和GetPriorEdge(longnodeNo,longsucNo)。GetInDegree(longnodeNo)：返回编号为：返回编号为nodeNo的结点的入度的结点的入度值。值。GetOutDegree(longnodeNo)：返回编号为：返回编号为nodeNo的结点的结点的出度值。的出度值。AddNode(mNo,nodeInfo)：给图加入一个结点。结点的编号为：给图加入一个结点。结点的编号为mNo，值为，值为nodeInfo。30第30页，共36页，编辑于2022年，星期五AddEdge(startNo,endNo,pee)：给图增加一条边。边的起点和终点：给图增加一条边

34、。边的起点和终点分别为分别为startNo和和endNo，边的内容为，边的内容为pee所指内容，其为空时表所指内容，其为空时表示暂不设置边内容。当示暂不设置边内容。当startNo或或endNo不存在时，该函数还负责不存在时，该函数还负责加入相应的结点。加入相应的结点。DeleteNode(mNo)：删除编号为：删除编号为mNo的结点，的结点，并将其值存储在一个临时的缓冲区，返回该缓冲区的地址。并将其值存储在一个临时的缓冲区，返回该缓冲区的地址。DeleteEdge(startNo,endNo)：删除两端点的编号分别为：删除两端点的编号分别为startNo和和endNo的边，并将其值存储在一个

35、临时的缓冲区，返回该缓冲的边，并将其值存储在一个临时的缓冲区，返回该缓冲区的地址。区的地址。Cluster(longv0,TElem*e,TTraverseModetm)：串行化聚集：从结点：串行化聚集：从结点v0出发，按出发，按tm方式遍历图，将遍历到的方式遍历图，将遍历到的结点的内容的地址依次存于结点的内容的地址依次存于e中，并返回所遍历到的结点的个数。中，并返回所遍历到的结点的个数。31第31页，共36页，编辑于2022年，星期五Locate(longstartNo,longendNo)：边定位：返回两端点编号分别：边定位：返回两端点编号分别为为startNo和和endNo的边的指针。的

36、边的指针。Locate(TElem&e,TTraverseModetm,longsn=1)：结点内容定位：结点内容定位：返回结点内容为返回结点内容为e的（在遍历方式的（在遍历方式tm下的）第下的）第sn个结点的指针。个结点的指针。sn0时表示正数（第一次遍历到的内容为时表示正数（第一次遍历到的内容为e的结点的对应的结点的对应sn为为1，余，余递增），递增），sn0时表示倒数（最后遍历到的内容为时表示倒数（最后遍历到的内容为e的结点的对应的结点的对应sn为为-1，余为，余为-2,等等）。等等）。Cluster(longv0,long*nos,TTraverseModetm)：与上面的：与上面的函

37、数类似，不同的是将遍历到的结点的编号存于函数类似，不同的是将遍历到的结点的编号存于nos中。中。32第32页，共36页，编辑于2022年，星期五GetPath(longstartNo,longendNo,longsn,long*pathNodeNo)：求路径：求从：求路径：求从startNo（编号）到（编号）到endNo(编号编号)的第的第sn条路径，并将其上结点依次存入条路径，并将其上结点依次存入pathNodeNo中。这里，所谓路径中。这里，所谓路径的次序（第的次序（第sn条）条）,是按从是按从startNo到到endNo的深度优先次序。的深度优先次序。sn的含的含义同前。义同前。GetP

38、ath(longstartNo,longendNo,longsn,TGraphNode0*pathNode)：与上面的函数类似，不同的与上面的函数类似，不同的是将路径上的结点的指针存入是将路径上的结点的指针存入pathNode。GetPathShortest(longstartNo,TDijkPath*path)：生成单源最：生成单源最短路径（从短路径（从startNo到其余各点的最短路径）。到其余各点的最短路径）。GetPathShortest(long*path)：生成多源最短路径（每对结点讲间的最：生成多源最短路径（每对结点讲间的最短路径）短路径）33第33页，共36页，编辑于2022年

39、，星期五本讲小结本讲小结本讲介绍了图的基本概念，重点是有关图的术语和基本讲介绍了图的基本概念，重点是有关图的术语和基本含义。要求掌握图、有向图本含义。要求掌握图、有向图/无向图、结点、边、无向图、结点、边、弧、邻接、关联、度、权、路径、子图、生成弧、邻接、关联、度、权、路径、子图、生成图、连通、生成树等概念。了解图的基本操作。图、连通、生成树等概念。了解图的基本操作。另一个重点是掌握图的结点抽象模型、图的边另一个重点是掌握图的结点抽象模型、图的边的抽象模型，进而构建图凑向对象模型。了解的抽象模型，进而构建图凑向对象模型。了解图抽象对象模型中虚函数的功能。图抽象对象模型中虚函数的功能。接着讲图的两种存储结构，并接着讲图的两种存储结构，并在两种存储结构上，考虑其增、在两种存储结构上，考虑其增、删功能的实现删功能的实现34第34页，共36页，编辑于2022年，星期五思考与练习思考与练习见第19讲35第35页，共36页，编辑于2022年，星期五36第36页，共36页，编辑于2022年，星期五