数据结构：第7章图B

1、1具体内容：先生成一棵二叉具体内容：先生成一棵二叉排序排序树，再用中序遍历方式打印每个树，再用中序遍历方式打印每个结点值，并统计其叶子结点的个数结点值，并统计其叶子结点的个数。具体内容：先生成一棵哈夫曼树，再打印各具体内容：先生成一棵哈夫曼树，再打印各字符字符对应的哈夫曼编对应的哈夫曼编码。码。具体内容：参见严题集具体内容：参见严题集P149 实习实习5.2要求，或参见自测卷要求，或参见自测卷（算法设计题一定要写出思路）（算法设计题一定要写出思路） 1.1.忽视验证手段忽视验证手段2.2.不理解二叉排序树的含义不理解二叉排序树的含义1.1.不列字符只列权重，轻视物理不列字符只列权重，轻视物理意

2、义意义2.2.无验证手段无验证手段1.1.热情高，但程序质量不高（热情高，但程序质量不高（完成方案三的人不多完成方案三的人不多）2.2.“用户体验用户体验”意识不够（用文件者少）意识不够（用文件者少）23ADT Graph 数据对象数据对象V：数据关系数据关系 R：基本操作基本操作P： ADT Graph V V是具有相同特性的数据元素的集合，称为顶点集。是具有相同特性的数据元素的集合，称为顶点集。R=VRR=VR；VR=VR=|v,wV |v,wV 且且 P(v,w)P(v,w), , 表示从表示从v v到到w w的弧，的弧， 谓词谓词P(v,w)P(v,w)定义了弧定义了弧的意义或信息的意

3、义或信息 CreatGraph ( &G, V,VR); 初始条件：初始条件：V V是图的是图的顶点集顶点集，VRVR是图中弧的集合。是图中弧的集合。 操作结果：操作结果：按按V V和和VRVR的定义构造图的定义构造图G G。注意：注意：V V 的大小写含的大小写含义不同！义不同！InsertVex ( &G, v); 初始条件：初始条件：图图G G存在，存在，v v 和图中和图中顶点顶点有相同特征。有相同特征。 操作结果：操作结果：在图在图G G中添加中添加新顶点新顶点。 （参见教材（参见教材P156-257P156-257）4图的特点：图的特点：链式存储结构：链式存储结构：

4、顺序存储结构：顺序存储结构：可用链表描述可用链表描述用用数组数组描述行否？描述行否？非线性结构非线性结构（m : nm : n）邻接矩阵邻接矩阵邻接表邻接表十字链表十字链表邻接多重表邻接多重表各种表示法成立的原则：各种表示法成立的原则：存入电脑后能存入电脑后能惟一复原惟一复原多个顶点，而且无序，仅用顶点坐标无法表达相互关系多个顶点，而且无序，仅用顶点坐标无法表达相互关系5 , ),( , ,.否否则则或或者者如如果果01AEjiEjijiEdge邻接矩阵：邻接矩阵：A.Edge =（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 1 0 1 01 0 1 0 10 1 0 1 11

5、0 1 0 10 1 1 1 0顶点表：顶点表：下面无向图的邻接矩阵如何表示？下面无向图的邻接矩阵如何表示？v1v2v3v5v4v4记录各个顶点信息记录各个顶点信息表示各个顶点之间关系表示各个顶点之间关系0 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 06例例2 ：下面有向图的邻接矩阵如何表示？下面有向图的邻接矩阵如何表示？有向图的邻接矩阵有向图的邻接矩阵可能是不对称可能是不对称的。的。顶点顶点v vi i的的出度出度= =第第i i行元素之和行元素之和，OD(v

6、vi i )= A.Edge i j 顶点顶点v vi i的的入度入度= =第第i i列元素之和列元素之和。ID(v vi i )= A.Edge j i 顶点的顶点的度度= =第第i i行元素之和行元素之和+ +第第i i列元素之和列元素之和, , 即：即：TD( v vi i ) = OD( vi ) + ID( vi )v1v2v3v4邻接矩阵：邻接矩阵：A.Edge =( v1 v2 v3 v4 )v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 在有向图的邻接矩阵中，在有向图的邻接矩阵中， 第第i i行含义：以结点行含义：以结点v vi i为尾的弧为尾的弧

7、( (即出度边）；即出度边）； 第第i i列含义：以结点列含义：以结点v vi i为头的弧为头的弧( (即入度边）。即入度边）。顶点表：顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 7 容易实现图的操作，如：求某顶点的度、判断容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。顶点之间是否有边（弧）、找顶点的邻接点等等。 n n个顶点需要个顶点需要个单元存储边个单元存储边( (弧弧););空间效率空间效率为为O(O(n n ) )。例例3 ： 有权图（即有权图（即网络网络）的）

8、的邻接矩阵邻接矩阵如何表示？如何表示？定义：定义：A.Edge i j =Wij 或（或（vi, vj）VR 无边（弧）无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：以有向网为例：邻接矩阵：邻接矩阵： N.Edge =( v1 v2 v3 v4 v5 v6 )邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：顶点表：顶点表： 5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 v1v2v3v4v5v6对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。8注：注：用两个数组分别存储顶点表和邻接矩阵用两个数组分别存储顶点表和邻接矩阵

9、#define INFINITY INT_MAX /最大值最大值#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数Typedef enum DG, DN, AG, AN GraphKind; /有向有向/ /无向图，有向无向图，有向/ /无向无向网网图的邻接矩阵在机内如何表示？图的邻接矩阵在机内如何表示？ （参见教材（参见教材P161P161）对于对于n n个顶点的图或网，空间效率个顶点的图或网，空间效率=O(n=O(n2 2) )Typedef struct ArcCell /弧（边）弧（边）结点的定义结点的定义 VRType adj; /顶点间关系，无权

10、图取顶点间关系，无权图取1 1或或0 0；有权图取权值类型；有权图取权值类型 InfoType *info; /该弧相关信息的指针该弧相关信息的指针ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ;Typedef struct /图的定义图的定义VertexType vexs MAX_VERTEX_NUM ; /顶点表，用一维向量即可顶点表，用一维向量即可( (n n) )AdjMatrix arcs; /邻接矩阵邻接矩阵n n* *n nInt Vernum, arcnum; /顶点总数顶点总数n n，弧（边）总数，弧（边）总数e eGrap

11、hKind kind; /图的种类标志图的种类标志Mgraph; 9Status CreateUDN(Mgraph &G) /无向网的构造，用邻接矩阵表示无向网的构造，用邻接矩阵表示scanf(&G.vexnum, &G.arcnum, &IncInfo); /输入总顶点数输入总顶点数n n、总弧数、总弧数e e和信息和信息for(i=0;iG.vexnum,;+i) scanf(&G.vexsi );/输入输入n n个顶点值个顶点值，存入一维向量，存入一维向量例：例：用邻接矩阵生成用邻接矩阵生成无向网无向网的算法的算法（参见教材（参见教材P162P16

12、2）对于对于n n个顶点个顶点e e条弧的网，条弧的网，建网时间效率建网时间效率 = O(n+= O(n+n n2 2+ +e e* *n n) )for(i=0; iG.vexnum; +i) /对邻接矩阵对邻接矩阵n n* *n n个单元初始化，个单元初始化，adj=,info=NULLfor(j=0;jG.vexnum;+j) G.arcsij=INFINITY, NULL; for(k=0;kG.arcnum;+k) /给邻接矩阵有关单元赋初值给邻接矩阵有关单元赋初值( (循环次数弧数循环次数弧数e e scanf(&v1, &v2, &w); /输入弧的两顶点

13、以及对应权值输入弧的两顶点以及对应权值 i=LocateVex(G,v1); j=LocateVex(G,v2); /找到两顶点在矩阵中的位置找到两顶点在矩阵中的位置( (n n次次) ) G.arcsij.adj=w; /输入对应权值输入对应权值 If(IncInfo) Input(*G.); /如果弧有信息则填入如果弧有信息则填入 G.arcsij = G.arcs j i； /无向网是对称矩阵无向网是对称矩阵 return OK; / CreateCreateUDN INT_MAX10adjvex nextarcinfodatafirstarc邻接点域，邻接点域，表

14、表示示v vi i 邻接点邻接点的位置的位置链域，链域，指向指向下一个边或下一个边或弧的结点弧的结点数据域，数据域，与与边有关信息边有关信息（如权值）（如权值）数据域，存数据域，存储顶点储顶点vi 信信息息链域，链域，指向指向单链表的第单链表的第一个结点一个结点11例例1 1：无向图的邻接表如何表示？无向图的邻接表如何表示？v1v2v3v5v4v4邻邻接接表表0123413341420例例2 2：有向图的邻接表如何表示？有向图的邻接表如何表示？v1v2v3v4V4V3V2V12301邻接表邻接表(出边出边)V4V3V2V13020逆邻接表逆邻接表(入边入边)请注意：邻接表不惟一！因各个边结点的

15、链入顺序是任意的。请注意：邻接表不惟一！因各个边结点的链入顺序是任意的。v1v2v3v4v5231420v v1 1邻接点邻接点v v4 4和和v2 2的位置的位置此无权图未开第此无权图未开第3 3分量分量12例例3 3：已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的存储当邻接表的存储结构形成后，图结构形成后，图便唯一确定！便唯一确定！13分析分析1: 对于对于n n个顶点个顶点e e条边的无向图条边的无向图，邻接表中除了，邻接表中除了n n个头结点个头结点外，只有外，只有2e2e个表结点个表结点, ,空间效率为空间效率为O(n+2e)

16、O(n+2e)。若是稀疏图若是稀疏图(en(en2 2) )，则比邻接矩阵表示法，则比邻接矩阵表示法O(nO(n2 2) )省空间。省空间。邻接表存储法的特点：邻接表存储法的特点：分析分析2:在在有向图有向图中，邻接表中除了中，邻接表中除了n n个头结点外，只有个头结点外，只有e e个表结点个表结点, ,空间效率为空间效率为O(n+e)O(n+e)。若是稀疏图，则比邻接矩阵表示法更合适。若是稀疏图，则比邻接矩阵表示法更合适。它其实是对邻接矩阵法的一种改进它其实是对邻接矩阵法的一种改进怎样计算无向图顶点的度？怎样计算无向图顶点的度？邻接表的邻接表的缺点：缺点：怎样计算有向图顶点的出度？怎样计算有

17、向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点的入度？怎样计算有向图顶点怎样计算有向图顶点Vi的度：的度：需遍历全表需遍历全表邻接表的邻接表的优点：优点：TD(Vi)TD(Vi)= =单链表中链接的结点个数单链表中链接的结点个数OD(Vi)单链出边表中链接的结点数单链出边表中链接的结点数I D( Vi ) 邻接点为邻接点为ViVi的弧个数的弧个数TD(Vi) = OD( Vi ) + I D( Vi )空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。结点对应

18、的单链表，没有邻接矩阵方便。14图的邻接表在机内如何表示？图的邻接表在机内如何表示？ （参见教材（参见教材P163P163）#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数空间效率为空间效率为O(n+2e)O(n+2e)或或O(n+e)O(n+e)时间效率为时间效率为O(n+eO(n+e* *n)n)Typedef struct VNode /顶点结构顶点结构 VertexType data; /顶点信息顶点信息 ArcNode * firstarc; /指向依附该顶点的第一条弧的指针指向依附该顶点的第一条弧的指针VNode, AdjList MAX_VE

19、RTEX_NUM ; Typedef struct /图结构图结构 AdjList vertics ; /应包含邻接表应包含邻接表 int vexnum, arcnum; /应包含顶点总数和弧总数应包含顶点总数和弧总数 int kind; /还应说明图的种类（用标志）还应说明图的种类（用标志）ALGraph; Typedef struct ArcNode /弧结构弧结构 int adjvex; /该弧所指向的顶点位置该弧所指向的顶点位置 struct ArcNode *nextarcs; /指向下一条弧的指针指向下一条弧的指针 InfoArc *info; /该弧相关信息的指针该弧相关信息的指

20、针 ArcNode；图的邻接表图的邻接表生成算法作生成算法作为自测题为自测题151.1. 联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2. 2. 区别：区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但号与顶点编号一致），但邻接表不唯一邻接表不唯一（链接次序（链接次序与顶点编号无关）。与顶点编号无关）。 邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空

21、间复杂度为杂度为O(n+e)O(n+e)。3. 3. 用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-1)/2)n(n-1)/2)；而邻接表多用于稀疏图的存储（而邻接表多用于稀疏图的存储（enen2 2) )16 它是它是有向图有向图的另一种链式结构。的另一种链式结构。 思路：思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。1、开设弧结点，设弧结点，设5 5个域个域（每段弧是一个数据元素）（每段弧是一个数据元素）2 2、开设顶点结点，设、开设顶点结点，设3 3个域个域（每个顶点也是一个数据元素）（每

22、个顶点也是一个数据元素）tailvexheadvexhlinktlinkinfo data : 顶点信息Firstin : 以顶点为弧头的第一条弧结点Firstout: 以顶点为弧尾的第一条弧结点dataFirstinFirstout顶点结点顶点结点弧结点弧结点tailvextailvex: : 弧尾顶点位置 headvexheadvex: : 弧头顶点位置hlinkhlink: : 弧头相同的下一弧位置tlinktlink: : 弧尾相同的下一弧位置info:info: 弧信息n个顶点的集合怎样储存？个顶点的集合怎样储存？仍用顺序存储结构仍用顺序存储结构因课时有限，因课时有限，以下内容自学以

23、下内容自学17v1v2v3v42 0233031例：画出有向图的十字链表。例：画出有向图的十字链表。十字链表优点：十字链表优点：容易操作，如求顶点的入度、出度等。容易操作，如求顶点的入度、出度等。FirstoutFirstindata顶点结点顶点结点infotlinkhlinkheadvextailvex弧结点弧结点0v11v22v33v401230 102此无权图未开第此无权图未开第4 4分量分量空间复杂度和建表的时间复杂度都与邻接表相同空间复杂度和建表的时间复杂度都与邻接表相同。18#define MAX_VERTEX_NUM 20十字链表存储结构描述：十字链表存储结构描述：Typedef

24、 struct ArcBox /弧结点结构，弧结点结构，5 5分量分量 int tailvex , headvex ; struct ArcBox * hlink , tlink; InfoType *info; ArcBox;Typedef struct VexNode /顶点结构顶点结构, 3, 3分量分量 VertexType data; ArcBox * firstin,*firstout;VexNode;Typedef struct /图结构图结构, ,整体概念整体概念 VexNode xlist MAX_VERTEX_NUM ; /表头向量表头向量 int vexnum, arcn

25、um;OLGraph; 19这是这是无向图无向图的另一种存储结构，当的另一种存储结构，当对边操作对边操作时建议采用此种结构存储。时建议采用此种结构存储。 1、设立、设立边结点，边结点， 6个域个域（每条边是一个数据元素）（每条边是一个数据元素）2、设立、设立顶点结点，顶点结点， 2个域个域（每个顶点也是一个数据元素）（每个顶点也是一个数据元素）markivexilinkjvexjlinkinfo边结点边结点 data : 存储顶点信息存储顶点信息Firstedge : 依附顶点的第一依附顶点的第一条边结点条边结点dataFirstedge顶点结点顶点结点mark：标志域标志域ivex， jve

26、x : 边依附的两个顶点位置边依附的两个顶点位置 ilink: 指向下一条依附顶点指向下一条依附顶点 i 的边位置的边位置jlink; 指向下一条依附顶点指向下一条依附顶点 j 的边位置的边位置info: 边信息边信息n个顶点的集合怎样储存？个顶点的集合怎样储存？仍用顺序存储结构仍用顺序存储结构20121 4232 43 4 v1v2v3v5v4v4例：画出无向图的邻接多重表例：画出无向图的邻接多重表邻接多重表优点：邻接多重表优点：容易操作，如求顶点的度等。容易操作，如求顶点的度等。0v11v22v33v44v501234Firstedgedata顶点结点顶点结点markinfojlinkjv

27、exilinkivex边结点边结点空间复杂度和建表的时间复杂度都与邻接表相同。空间复杂度和建表的时间复杂度都与邻接表相同。0103此无权此无权图未开图未开第第6 6分量分量2122一、深度优先搜索二、广度优先搜索 7.3 图的遍历图的遍历遍历定义：遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的图的基本运算基本运算。遍历实质：遍历实质：找每个顶点的邻接点的过程。找每个顶点的邻接点的过程。图的特点：图的特点：图中可能存在图中可能存在回路回路，且

28、图的任一顶点都可能与其它，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点到了曾经访问过的顶点解决思路：解决思路：可设置一个可设置一个辅助数组辅助数组 visited n ，用来标记每个被，用来标记每个被访问过的顶点。它的初始状态为访问过的顶点。它的初始状态为0 0，在图的遍历过程中，在图的遍历过程中，一旦某一个顶点一旦某一个顶点i 被访问，就立即改被访问，就立即改 visited i为为1 1，防止，防止它被多次访问。它被多次访问。图常用的遍历：图常用的遍历：怎样避免重复访问？怎样避免重复访问？

29、23基本思想：基本思想：仿树的先序遍历过程。仿树的先序遍历过程。Depth_First Searchv1v2v3v8v7v6v4v5起点起点起点起点遍历步骤遍历步骤应退回到应退回到V8V8，因为，因为V2V2已有标记已有标记应退回到应退回到V3V3，因为，因为V2V2已有标记已有标记24深度优先搜索（遍历）步骤：深度优先搜索（遍历）步骤：详细归纳：详细归纳：E在访问图中某一起始顶点在访问图中某一起始顶点 v 后，由后，由 v 出发，访问出发，访问它的任一邻接它的任一邻接顶点顶点 w1；E再从再从 w1 出发，访问出发，访问与与 w1邻接邻接但还但还未被访问未被访问过的顶点过的顶点 w2；E然后

30、再从然后再从 w2 出发，进行类似的访问，出发，进行类似的访问， E如此进行下去，直至到达所有的邻接顶点都被访问过的顶点如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。为止。E接着，接着，退回一步，退回一步，退到前一次刚访问过的顶点退到前一次刚访问过的顶点，看是否还有，看是否还有其它未被访问的邻接顶点。其它未被访问的邻接顶点。 如果有，如果有，则访问此顶点，之后再从此顶点出发，进行与前述则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；类似的访问； 如果没有，就如果没有，就再退回一步再退回一步进行搜索进行搜索。重复上述过程，直到连。重复上述过程，直到连通图中所有顶点都被访

31、问过为止。通图中所有顶点都被访问过为止。简单归纳：简单归纳： 访问起始点访问起始点 v; 若若v的第的第1个邻接点没访问过，深度遍历此邻接点；个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找若当前邻接点已访问过，再找v的第的第2个邻接点重新遍历。个邻接点重新遍历。251 2345610 000000 0000030 0000040 0000050 0000060 00000000000123456010000100001000010101邻邻接接矩矩阵阵A辅助数组辅助数组 visited n 起点起点开辅助数组开辅助数组 visited n ！例：例：1 23 456100000

32、 00300 00400 005000060 0000请注意逐级回退是递归概念请注意逐级回退是递归概念26for( j=1; jlink)while(p-link) /当存在起点的第一个邻接点时当存在起点的第一个邻接点时 p=p-link; p=p-link; v=p-data; v=p-data; if(!visitedv)DFS(List,v,p);if(!visitedv)DFS(List,v,p); /进行递归进行递归 return; return; 29（）n如果用如果用邻接矩阵邻接矩阵来表示图，遍历图中每一个顶点都来表示图，遍历图中每一个顶点都要要从头扫描从头扫描该顶点所在行，因此

33、遍历全部顶点所需该顶点所在行，因此遍历全部顶点所需的时间为的时间为O(n2)。n如果用如果用邻接表邻接表来表示图，虽然有来表示图，虽然有 2e 个表结点，但个表结点，但只需扫描只需扫描 e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问 n个头个头结点的时间，因此遍历图的时间复杂度为结点的时间，因此遍历图的时间复杂度为O(n+e)。结结 论：论：稠密图稠密图适于在邻接矩阵上进行深度遍历；适于在邻接矩阵上进行深度遍历；稀疏图稀疏图适于在邻接表上进行深度遍历。适于在邻接表上进行深度遍历。30基本思想：基本思想：仿树的层次遍历过程。仿树的层次遍历过程。Breadth_First Searc

34、hv1v2v3v8v7v6v4v5起点起点遍历步骤遍历步骤起点起点31广度优先搜索（遍历）步骤：广度优先搜索（遍历）步骤：简单归纳：简单归纳：在访问了起始点在访问了起始点v之后，依次访问之后，依次访问 v的邻接点；的邻接点；然后再依次然后再依次（顺序）（顺序）访问这些点访问这些点（下一层）（下一层）中未被中未被访问过的邻接点；访问过的邻接点；直到所有顶点都被访问过为止。直到所有顶点都被访问过为止。广度优先搜索是一种分层的搜索过程，每向前走一广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回步可能访问一批顶点，不像深度优先搜索那样有回退的情况。退的情况。因此

35、，广度优先搜索不是一个递归的过程，其算法因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。也不是递归的。32讨论讨论1：计算机如何实现计算机如何实现BFS？邻接表邻接表宽度优先搜索要借助队列！宽度优先搜索要借助队列！例：例：起点起点辅助队列辅助队列v2已访问过了已访问过了V2入队入队visited n 仍需要仍需要front=n-1;rear=0front=n-1;rear=033while(rear!=front) /队不空时队不空时 front=(front+1)%n; v=qfront; /访问过的顶点出队（此时才访问过的顶点出队（此时才输出输出） p=Listv.firstar

36、c; /P/P指向第指向第1 1个邻接点个邻接点 while(!p) if(! Visitedadjvex(p) )/未到表尾，且邻接域未访问过，未到表尾，且邻接域未访问过， Visit(adjvex(p); Visitedadjvex(p)=1;/先访问再改标记，先访问再改标记， rear=(rear+1)%n; qrear= adjvex(p) /然后入队然后入队 p=nextarc(p); /指向单链表中下一个邻接点指向单链表中下一个邻接点 return / BFS1/ BFS1讨论讨论2： BFS算法如何编程算法如何编程？BFS1(List, n, v) /List/List为邻接表，

37、为邻接表，v v为起点，为起点，QnQn为辅助队列为辅助队列 Visit(v); Visitedv=1; /访问（例如打印）顶点访问（例如打印）顶点v v并修改标志并修改标志 层次遍历应当用队列！层次遍历应当用队列！（教材上（教材上BFSBFS算法见算法见P170P170）front=n-1;rear=0; /队列指针初始化队列指针初始化qrear=v; /起始点入队（此前虽访问但未输出）起始点入队（此前虽访问但未输出）34 空间复杂度相同，都是空间复杂度相同，都是O(n)O(n)( (借用堆栈或队列装借用堆栈或队列装n n个顶点）；个顶点）； 时间复杂度只与存储结构时间复杂度只与存储结构（邻

38、接矩阵或邻接表）（邻接矩阵或邻接表）有关，而有关，而与搜索路径无关。与搜索路径无关。 如果使用邻接表来表示图，则如果使用邻接表来表示图，则BFS循环的总时间代价为循环的总时间代价为 d0 + d1 + + dn-1 = O(e)，其中的其中的 di 是顶点是顶点 i 的度的度。 如果使用邻接矩阵，则如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（都要循环检测矩阵中的整整一行（ n 个元素），总的个元素），总的时间代价为时间代价为O(n2)。（）357.4 7.4 图的其他图的其他运算运算1. 求图的生成树求图的生成树2. 求最小生成树

39、求最小生成树3. 求最短路径求最短路径4. 求关节点和重连通分量（略）求关节点和重连通分量（略）5. 拓扑排序拓扑排序6. 求关键路径求关键路径36生成树：生成树：是一个极小连通子图，它含有图中全部顶点，但只有是一个极小连通子图，它含有图中全部顶点，但只有n-1n-1条边。条边。生成森林：生成森林：由若干棵由若干棵生成树生成树组成，含全部顶点，但构成这些树组成，含全部顶点，但构成这些树的边是最少的。的边是最少的。思考1：若对连通图进行遍历，得到的是什么？ 得到的将是一个极小连通子图，即图的得到的将是一个极小连通子图，即图的生成树生成树！由深度优先搜索得到的生成树，称为由深度优先搜索得到的生成树

40、，称为深度优先搜索生成树深度优先搜索生成树。由广度优先搜索得到的生成树，称为由广度优先搜索得到的生成树，称为广度优先搜索生成树广度优先搜索生成树。思考2：若对非连通图进行遍历，得到的是什么？ 得到的将是各连通分量的生成树，即图的得到的将是各连通分量的生成树，即图的生成森林生成森林！37例例1 ：画出下图的生成树：画出下图的生成树DFS生生成成树树v0v1v2v4v4v3邻接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生生成成树树v0v1v3v2v4无向连通图无向连通图v0v1v2v4v4v3v0v1v2v4v4v3本例无回溯本例无回溯38其实由邻接矩阵

41、或邻接表其实由邻接矩阵或邻接表也能直接画出生成森林也能直接画出生成森林DEABCFJLMGHIK例例2：画出下图的生成森林（或极小连通子图）：画出下图的生成森林（或极小连通子图）求解步骤：求解步骤：Step1:Step1:先求出邻接矩阵或邻接表；先求出邻接矩阵或邻接表；Step2:Step2:写出写出DFSDFS或或BFSBFS结果序列；结果序列；Step3:Step3:画出对应子图或生成森林。画出对应子图或生成森林。这是一个无向非连通图这是一个无向非连通图（参见教材（参见教材P170-171P170-171例）例）下面选用下面选用邻接表邻接表方式来求方式来求深度深度优先搜索生成森林优先搜索生

42、成森林生成森林的定义生成森林的定义（对有向或无向图（对有向或无向图均适用）：是若干棵均适用）：是若干棵生成树的集合生成树的集合，含全部顶点，但构成这些树的边或含全部顶点，但构成这些树的边或弧弧是最少的。是最少的。39115 5M12L11K10J9I8H7G6F5E4D3C2B1A01201200437810661011126709121911112294710811DEGHIK子图子图1：再写出再写出DFS结果结果ABMJLCFDEGHKIABCFJLM先写出邻接表（先写出邻接表（或邻接矩阵或邻接矩阵）：）：子图子图2：子图子图3：最小连通！最小连通！思考：怎样思考：怎样找找3 3个根？个根？40DEGHIK子图子图(或连通分量或连通分量)ABCFJLMABCFJLMDEGHIK生生成成森森林林412. 2. 求最小生成树求最小生成树首先明确：首先明确： 使用不同的遍历图的方法，可以得到不同的生成树；从使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。不同的顶点出发，也可能得到不同的生成树。 按照生成树的定义，按照生成树的定义，n n 个顶点的个顶点