数据结构图的介绍幻灯片.ppt

《数据结构图的介绍幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构图的介绍幻灯片.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构图的介绍第1页，共28页，编辑于2022年，星期六基本定义和术语 若图G中的每条边都是有方向的，则称G为有向图有向图（Digraph）。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，vi，vj表示一条有向边，vi是边的始点（起点），vj是边的终点。因此，vi，vj和vj，vi是两条不同的有向边。有向边也称为弧（Arc），边的始点称为弧尾（Tail），终点称为弧头（Head）。图图G由两个集合V和E组成，记为G(V，E)，其中v是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集。通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空

2、集，若E(G)为空，则图G只有顶点而没有边，称为空图。第2页，共28页，编辑于2022年，星期六 若(vi，vj)是一条无向边，则称顶点vi和vj互为邻接点邻接点(Adjacent)，或称vi和vj相邻接；称(vi，vj)关联(Incident)于顶点vi和vj，或称(vi，vj)与顶点vi和vj相关联相关联。如图7-1中G2，与顶点vl相邻接的顶点是v2，v3和v4，而关联于顶点v2的边是(vl，v2)，(v2，v3)和(v2，v4)。若vi，vj是一条有向边，则称顶点vi邻接到vj,顶点vj邻接于顶点vi,并称边vi，vj关联于vi和vj或称vi，vj与顶点vi和vj相关联。如图7-1中G

3、l，关联于顶点v2的边是v1，v2，v2，vl和v2,v3。无向图中顶点v的度度(Degree)是关联于该顶点的边的数目，记为D(v)。若G为有向图，则把以顶点v为终点的边的数目，称为v的人度人度(1ndegree)，记为ID(v)；把以顶点v为始点的边的数目，称为v的出度出度(outdegree)，记为OD(v)；顶点v的度则定义为该顶点的入度和出度之和，即D(v)ID(v)十OD(v)。第3页，共28页，编辑于2022年，星期六 在无向图G中，若存在一个顶点序列vp,vi1,vi2，vin，vq，使得(vp，vil)，(vi1,vi2)，(vin，vq)均属于E(G)，则称顶点vp到vq存

4、在一条路径路径(Path)。若G是有向图，则路径也是有向的，它由E(G)中的有向边vp，vil，vil，vi2，vin，vq组成。路径长度路径长度定义为该路径上边的数目。若一条路径上除了vp和vq可以相同外；其余顶点均不相同，则称此路径为一条简单路径简单路径。起点和终点相同(vpvq)的简单路径称为简单回路简单回路或简单环简单环(Cycle)。例如，在图G2中顶点序列vl,v2，v3，v4是一条从顶点vl到顶点v4的长度为3的简单路径；顶点序列vl,v2，v4，vl，v3是一条从顶点vl到顶点v3的长度为4的路径，但不是简单路径；顶点序列vl，v2，v4，vl是一个长度为3的简单环。在有向图G

5、l中，顶点序列vl，v2，vl是一个长度为2的有向简单环。第4页，共28页，编辑于2022年，星期六 在一个有向图中，若存在一个顶点v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为有根图有根图，v称作图的根根。在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通连通的。若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图连通图(Connected Graph)。例如，图G2和G3是连通图。无向图G的极大连通子图称为G的连通分量连通分量(connected Component)。显然，任何连通图的连通分量只有一个，即是其

6、自身，而非连通的无向图有多个连通分量。例如，图7-4中的G4是非连通图，它有两个连通分量Hl和H2。在有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图强连通图。有向图G的极大强连通子图称为G的强连通分量强连通分量。显然，强连通图只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分量。例如图7-1中的Gl不是强连通图，因为v3到v2没有路径，但它有两个强连通分量，第5页，共28页，编辑于2022年，星期六若将图的每条边都赋上一个权，则称这种带权图为网网络络(Network)。通常权是具有某种意义的数.第6页，共28页，

7、编辑于2022年，星期六它们可以表示两个顶点之间的距离，耗费等 第7页，共28页，编辑于2022年，星期六图的存储结构 邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。设G(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：第8页，共28页，编辑于2022年，星期六用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储顶点信息。其形式说明如下：#define n 6 /*图的顶点数*/#define e 8 /*图的边（弧）数*/typedef char vextype；/*顶点的数据类型*/typedef

8、float adjtype；/*权值类型*/typedef structvextype vexsn；adjtype arcsnn；graph；第9页，共28页，编辑于2022年，星期六 若图中顶点信息是0至n-1的编号，则仅需令权值为1，存储一个邻接矩阵就可以表示图。若是网络，则adjtype为权的类型。由于无向图或无向网络的邻接矩阵是对称的，故可采用压缩存储的方法，仅存储下三角阵(不包括对角线上的元素)中的元素即可。显然，邻接矩阵表示法的空间复杂度S(n)O(n2)。CREATGRAPH(ga)*建立无向网络*Graph*ga；int i，j，k；float w；for(i0；in；i+)g

9、a-vexsigetchar()；*读入顶点信息，建立顶点表*for(i0；in；i+)for(j0；jn；j+)ga-arcsij0；*邻接矩阵初始化*for(k0；ke；k+)*读入e条边*(scanf(”ddf”，&I,&j，&w)；*读入边(vi，vj)上的权w*ga-arcsijw；ga-arcsjiw；*CREATGRAPH*该算法的执行时间是O(n+n2+e)，其中O(n2)的时问耗费在邻接矩阵的初始化操作上。因为en2，所以，算法的时间复杂度是O(n2)。第10页，共28页，编辑于2022年，星期六邻接表 这种表示法类似于树的孩子链表表示法。对于图G中的每个顶点vi，该方法把所

10、有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表(Adjacency List)。邻接表中每个表结点均有两个域，其一是邻接点域(Adjvex)，用以存放与vi相邻接的顶点vj的序号；其二是链域(Next)，用来将邻接表的所有表结点链在一起。并且为每个顶点vi的邻接表设置一个具有两个域的表头结点：一个是顶点域(vertex)，用来存放顶点vi的信息；另一个是指针域(Link)，用于存入指向vi的邻接表中第一个表结点的头指针。为了便于随机访问任一顶点的邻接表，将所有邻接表的表头结点顺序存储在一个向量中，这样，图G就可以由这个表头向量来表示。第11页，共28页，编辑于2022年

11、，星期六建立有向图的邻接表与此类似，只是更加简单，每读入一个顶点对序号i，j时，仅需生成十个邻接点序号为j的边表结点，将其插入到vi的出边表头部即可。若建立网络的邻接表，则需在边表的每个结点中增加一个存储边上权的数据域。值得注意的是，一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为邻接表表示中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。邻接矩阵和邻接表是图的两种最常用的存储结构，它们各有所长。下面从空间及执行某些常用操作的时间这两方面来作一比较。第12页，共28页，编辑于2022年，星期六 在邻接表(或逆邻接表)表示中，每个边表对应于邻接矩阵的一行(或一列)，边表

12、中结点个数等于一行(或一列)中非零元素的个数。对于一个具有n个顶点e条边的图G，若G是无向图，则它的邻接表表示中有n个顶点表结点和2e个边表结点；若G是有向图，则它的邻接表表示或逆邻接表表示中均有n个顶点表结点和e个边表结点。因此邻接表或逆邻接表表示的空间复杂度为S(n，e)O(n+e)。若图中边的数目远远小于n2(即en2)，此类图称作稀疏图(Sparse Graph)，这时用邻接表表示比用邻接矩阵表示节省存储空间；若e接近于n2(准确地说，无向图e接近于n(n-1)2，有向图e接近于n(n-1)，此类图称作稠密图(Dense Graph)，考虑到邻接表中要附加链域，则应取邻接矩阵表示法为宜

13、。第13页，共28页，编辑于2022年，星期六在无向图中求顶点的度，邻接矩阵及邻接表两种存储结构都很容易做到：邻接矩阵中第i行(或第i列)上非零元素的个数即为顶点vi的度；在邻接表表示中，顶点vi的度则是第i个边表中的结点个数。在有向图中求顶点的度。采用邻接矩阵表示比邻接表表示更方便：邻接矩阵中的第i行上非零元素的个数是顶点vi的出度OD(vi)，第i列上非零元素的个数是顶点vi的入度ID(vi)，顶点vi的度即是二者之和；在邻接表表示中，第i个边表(即出边表)上的结点个数是顶点vi的出度，求vi的入度较困难，需遍历各顶点的边表。若有向图采用逆邻接表表示，则与邻接表表示相反，求顶点的入度容易，

14、而求顶点出度较难。在邻接矩阵表示中，很容易判定(vi，vj)或vi，vj是否是图的一条边，只要判定矩阵中的第i行第j列上的那个元素是否为零即可；但是在邻接表表示中，需扫描第i个边表，最坏情况下要耗费O(n)时间。在邻接矩阵中求边的数目e，必须检测整个矩阵，所耗费的时间是0(n2)，与e的大小无关；而在邻接表表示中，只要对每个边表的结点个数计数即可求得e，所耗费的时间是0(e+n)。因此，当en2时，采用邻接表表示更节省时间。第14页，共28页，编辑于2022年，星期六图的遍历 和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中所有顶点各作一次访问。若给定的图是连通图，则从图中任

15、一顶点出发顺着边可以访问到该图的所有顶点。然而，图的遍历比树的遍历复杂得多，这是因为图中的任一顶点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个顶点是否被访问过。为此，可设置一个布尔向量visitedn，它的初值为false，一旦访问了顶点vi，便将visitedi-1置为TRUE。第15页，共28页，编辑于2022年，星期六深度优先搜索(Depth-First-Search)遍历类似于树的前序遍历。假设给定图G的初态是所有顶点均未访问过，在G中任选一顶点vi为初始出发点，则深度优先搜索可定义如下：首先，访问出发点vi，

16、并将其标记为已访问过，然后，依次从vi出发搜索vi的每一个邻接点vj,若vj未曾访问过，则以vj为新的出发点继续进行深度优先搜索。显然上述搜索法是递归定义的，它的特点是尽可能先对纵深方向进行搜索，故称之为深度优先搜索。例如，设x是刚访问过的顶点，按深度优先搜索方法，下一步将选择一条从x出发的未检测过的边(x，y)。若发现顶点y已被访问过，则重新选择另一条从x出发的未检测过的边。若发现顶点y未曾访问过，则沿此边从x到达y，访问y并将其标记为已访问过，然后从y开始搜索，直到搜索完从y出发的所有路径，才回溯到顶点x，然后再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此

17、时，若x不是初始出发点，则回溯到在x之前被访问过的顶点；若x是初始出发点，则整个搜索过程结束。显然这时图G中所有和初始出发点有路径相通的顶点都已被访问过。因此，若G是连通图，则从初始出发点开始的搜索过程结束，也就意味着完成了对图G的遍历。第16页，共28页，编辑于2022年，星期六在该存储结构上执行DFS算法的过程如下：设初始出发点是v1，则DFS（0）的执行结果是访问v1，将其置上已访问标记，从v1搜索到的第1个邻接点是v2，因v2未曾访问过，故调用DFS(1)。执行DFS(1)，首先访问v2，将其标记为已访问过，然后从v2搜索到的第1个邻接点是vl，但vl已访问过，故继续搜索到第2个邻接点

18、v4，v4未曾访过，因此调用DFS(3)。类似地分析，访问v4后调用DFS(7)，访问v：后调用DPS(4)。执行DFS(4)时，在访问v5并作标记后，从v5搜索到的两个邻接点依次是v2和v8，因为它们均已被访问过，所以DFS(4)执行结束返回，回溯到v8。又因为v8的两个邻接点已搜索过，故DFS(7)亦结束返回，回溯到v4。类似地由v4回溯到v2。V2的邻接点vl和v4已搜索过，但v2的第3个邻接点v5还尚未搜索，故接下来由v2搜索到v5，但因为v5已访问过，所以DFS(1)也结束返回，回溯到vl。vl的第1个邻接点已搜索过，故继续从v1搜索到第2个邻接点v3，因为v3未曾访问过，故调用DF

19、S(2)。类似地依次访问v3，v6，v7后，又由v7依次回溯到v6，v3，vl。此时，vl的所有邻接点都已搜索过，故DFS(0)执行完毕。第17页，共28页，编辑于2022年，星期六宽度优先搜索法 宽度优先搜索(Breadth-First-Search)遍历类似于树的按层次遍历。设图G的初态是所有顶点均未访问过，在G中任选一顶点2为初始出发点，则宽度优先搜索的基本思想是：首先访问出发点Vi，接着依次访问vi的所有邻接点wl，w2，wt，然后，再依次访问与wl，w2，wt邻接的所有未曾访问过的顶点，依此类推，直至图中所有和初始出发点v有路径相通的顶点都已访问到为止。此时，从vi开始的搜索过程结束

20、，若G是连通图则遍历完成。显然，上述搜索法的特点是尽可能先对横向进行搜索，故称之为宽度优先搜索。设x和y是两个相继被访问过的顶点，若当前是以x为出发点进行搜索，则在访问x的所有未曾访问过的邻接点之后，紧接着是以y为出发点进行横向搜索，并对搜索到的y的邻接点中尚未被访问的顶点进行访问。也就是说，先访问的顶点其邻接点亦先被访问。为此，需引进队列保存已访问过的顶点。第18页，共28页，编辑于2022年，星期六最小生成树 图的生成树不是唯一的，从不同的顶点出发进行遍历，可以得到不同的生成树。对于连通网络G(V，E)，边是带权的，因而G的生成树的各边也是带权的。我们把生成树各边的权值总和称为生成树的权，

21、并把权最小的生成树称为G的最最小小生成树生成树(Minimun Spanning Tree)。生成树和最小生成树有许多重要的应用。令图G的顶点表示城市，边表示连接两个城市之间的通讯线路。n个城市之间最多可设立的线路有n(n-1)2条，把n个城市连接起来至少要有n-1条线路，则图G的生成树表示了建立通讯网络的可行方案。如果给图中的边都赋予权，而这些权可表示两个城市之间通讯线路的长度或建造代价，那么，如何选择n-1条线路，使得建立的通讯网络其线路的总长度最短或总代价最小呢?这就是要构造该图的一棵最小生成树。第19页，共28页，编辑于2022年，星期六以下我们只讨论无向图的最小生成树问题。构造最小生

22、成树可以有多种算法，其中大多数构造算法都是利用了最小生成树的下述性质：设G(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中所有的一个端点在U(即uU)里、另一个端点不在U(即vV-U)里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包含此边(u，v)。这个性质称为MST性质。MST性质可用反证法证明：假设G的任何一棵最小生成树中都不含边(u，v)。设T是G的一棵最小生成树，但不包含边(u，v)。由于T是树，且是连通的，因此有一条从u到v的路径；且该路径上必有一条连接两个顶点集U和V-U的边(u，v)，其中uU，vV-U，否则u和v不连通。当把边(u，v)加入树

23、T时，得到一个含有边(u，v)的回路，见图7-15。删去边(u，v)，上述回路即被消除，由此得到另一棵生成树T，T和T的区别仅在于用边(u，v)取代了T中的边(u，v)。因为(u，v)的权(u，v)的权，故T的权T的权，因此T也是G的最小生成树，它包含边(u，v)，与假设矛盾!第20页，共28页，编辑于2022年，星期六 假设G(V，E)是连通网络，为简单起见，我们用序号1至n来表示顶点集合，即v1，2，n。设所求的最小生成树为T(U，TE)，其中U是T的顶点集，TE是T的边集。并且将G中边上的权看做是长度。Prim算法的基本思想是：首先从v中任取一个顶点u0，将生成树T置为仅有一个结点u0的

24、树，即置Uu0；然后只要U是V的真子集，就在所有那些其一个端点u己在T(即uU)、另一个端点v还未在T(即vVU)的边中，找一条最短(即权最小)的边(u，v)，并把该条边(u，v)和其不在T中的顶点v，分别并入T的边集TE和顶点集U。如此进行下去，每次往生成树里并入一个顶点和一条边，直到把所有顶点都包括进生成树T为止。此时，必有UV，TE中有n-1条边。MST性质保证上述过程求得的T(U，TE)是G的一棵最小生成树。显然，Prim算法的关键是如何找到连接U和V-U的最短边来扩充生成树T。为直观解释方便，设想在构造过程中，T的顶点集U中顶点和边集TE中的边均被涂成红色，U之外的顶点集V-U中的顶

25、点均被涂成蓝色，连接红点和蓝点的边均被涂成紫色，那么最短紫边就是连接U和V-U的最短边。第21页，共28页，编辑于2022年，星期六最短路径 交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通?在有多条通路的情况下，哪一条路最短?交通网络可用带权图来表示。顶点表示城市名称，边表示两个城市有路连通，边上权值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径，不是指路径上边数之和最少，而是指路径上各边的权值之和最小。另外，若两个顶点之间没有边，则认为两个顶点无通路，但有可能有间接通路（从其他顶点达到)）。路径上的开始顶点(出发点)称为源点，路径上的最后一个顶点称

26、为终点，并假定讨论的权值不能为负数。第22页，共28页，编辑于2022年，星期六所有顶点对之间的最短路径 所有顶点对之间的最短路径是指：对于给定的有向网G=(V,E)，要对G中任意一对顶点有序对V、W(VW)，找出V到W的最短距离和W到V的最短距离。解决此问题的一个有效方法是:轮流以每一个顶点为源点，重复执行迪杰斯特拉算法n次，即可求得每一对顶点之间的最短路径,总的时间复杂度为O(n3)。第23页，共28页，编辑于2022年，星期六弗洛伊德算法仍然使用前面定义的图的邻接矩阵costn+1n+1来存储带权有向图。算法的基本思想是:设置一个nxn的矩阵A(k)，其中除对角线的元素都等于0外，其他元

27、素a(k)ij表示顶点i到顶点j的路径长度，K表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有 向 边 时，路 径 长 度 为，当 K=0时，A(0)ij=arcsij,以后逐步尝试在原路径中加入其他顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为：第一步，让所有边上加入中间顶点1，取Aij与Ai1+A1j中较小的值作Aij的值，完成后得到A(1)，第二步，让所有边上加入中间顶点2，取Aij与Ai2+A2j中较小的值，完成后得到A(2)，如此进行下去，当第n步完成后，得到A(n)，A(n)即为我们

28、所求结果，A(n)ij表示顶点i到顶点j的最短距离。第24页，共28页，编辑于2022年，星期六拓扑排序 通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动，这些活动完成时，整个工程也就完成了。例如，计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动，图7-24给出了若干门所开设的课程，其中有些课程的开设有先后关系，有些则没有先后关系，有先后关系的课程必须按先后关系开设，如开设数据结构课程之前必须先学完程序设计基础及离散数学，而开设离散数学则必须学完高等数学。在图7-24（b）中，我们用一种有向图来表示课

29、程开设，在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这有向图叫做顶点表示活动的网络(Active On Vertices)简称为AOV网。第25页，共28页，编辑于2022年，星期六在AOV网中，有向边表示i活动应先于j活动开始，即i活动必须完成后，j活动才可以开始，并称i为j的直接前驱，j为i的直接后继。这种前驱与后继的关系有传递性，此外，任何活动i不能以它自己作为自己的前驱或后继，这叫做反自反性。从前驱和后继的传递性和反自反性来看，AOV网中不能出现有向回路（或称有向环）。在AOV网中如果出现了有向环，则意味着某项活动应以自己作为先决条件，这是不对的，工程将无法进行。对程序流程

30、而言，将出现死循环。因此，对给定的AOV网，应先判断它是否存在有向环。判断AOV网是否有有向环的方法是对该AOV网进行拓扑排序，将AOV网中顶点排列成一个线性有序序列，若该线性序列中包含AOV网全部顶点，则AOV网无环，否则，AOV网中存在有向环，该AOV网所代表的工程是不可行的。第26页，共28页，编辑于2022年，星期六本章小结 图是一种复杂的非线性结构，具有广泛的应用背景。本章涉及到的基本概念有：图图：由两个集合V和E组成，记为G(V，E)，其中v是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集。通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集，若E(G

31、)为空，则图G只有顶点而没有边，称为空图。有向图（有向图（Digraph）：若图G中的每条边都是有方向的，则称G为有向图。无向图（无向图（Undigraph）：）：若图G中的每条边都是没有方向的，则称G为无向图。无向完全图无向完全图(Undirected Complete Graph)：恰好有n(n-1)2条边的无向图称为无向完全图。有向完全图有向完全图(Directed Complete Graph)：恰有n(n-1)条边的有向图称为有向完全图。邻接点邻接点(Adjacent)：若(vi，vj)是一条无向边，则称顶点vi和vj互为邻接点。度度(Degree)：无向图中顶点v的度是关联于该顶点

32、的边的数目。人度人度(1ndegree)若G为有向图，则把以顶点v为终点的边的数目，称为v的人度，记为ID(v)。出度出度(outdegree)：把以顶点v为始点的边的数目，称为v的出度，记为OD(v)。子图子图(Subgraph)：设G(V，E)是一个图，若v是v的子集，E是E的子集，且E中的边所关联的顶点均在v中，则G(V，E)也是一个图，并称其为G的子图。第27页，共28页，编辑于2022年，星期六路路径径(Path)：在无向图G中，若存在一个顶点序列vp,vi1,vi2，vin，vq，使得(vp，vil)，(vi1,vi2)，(vin，vq)均属于E(G)，则称顶点vp到vq存在一条路

33、径。路径长度路径长度：该路径上边的数目。简单路径简单路径：若一条路径上除了vp和vq可以相同外，其余顶点均不相同，则称此路径为一条简单路径。简单回路或简单环简单回路或简单环(Cycle)：起点和终点相同(vpvq)的简单路径称为简单回路或简单环。有有根根图图：在一个有向图中，若存在一个顶点v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为有根图，v称作图的根。连通连通：在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通的。连通图连通图(Connected Graph)：若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通

34、图。连通分量连通分量(connected Component)：无向图G的极大连通子图称为G的连通分量。强强连连通通图图：在有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。强连通分量强连通分量：有向图G的极大强连通子图称为G的强连通分量。网络网络(Network)：若将图的每条边都赋上一个权，则称这种带权图为网络。生成树生成树(Spanning Tree)：连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。最小生成树最小生成树(Minimun Spanning Tree)：权最小的生成树称为G的最小生成树。本章在介绍图的基本概念的基础上，还介绍了图的两种常用的存储结构，对图的遍历、最小生成树等问题做了较详细的讨论，给出了相应的求解算法，有的算法采用自顶向下、逐步求精的方法加以介绍，也许能便于读者理解它们。相对而言之，图这一章内容较难，尤其是离散数学基础较差的读者，也许难度更大些。建议读者知难而进，理解本章所介绍的算法实质，掌握图的有关术语和存储表示。面对实际问题时，学会引用本章的有关内容。第28页，共28页，编辑于2022年，星期六