数据结构-第6章-图课件.ppt

1、 Office:西配楼西配楼304（软件教研室）（软件教研室）Email:北京林业大学信息学院北京林业大学信息学院北京林业大学信息学院北京林业大学信息学院线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树集合数据元素间除“同属于一个集合”外，无其它关系图形结构多个对多个，如图逻辑结构逻辑结构北京林业大学信息学院北京林业大学信息学院6.16.1图的定义和基本术语图的定义和基本术语6.26.2案例引入案例引入6.36.3图的类型定义图的类型定义6.46.4图的存储结构图的存储结构6.56.5图的遍历图的遍历6.66.6图的应用图的应用6.76.7案例分析与实现案例分析与实现教学内容教学

2、内容北京林业大学信息学院北京林业大学信息学院1.1.掌握：图的基本掌握：图的基本概念及相关术语和性质概念及相关术语和性质2.2.熟练掌握：图的熟练掌握：图的邻接矩阵和邻接表邻接矩阵和邻接表两种存储表示方法两种存储表示方法3.3.熟练掌握：图的两种遍历方法熟练掌握：图的两种遍历方法DFSDFS和和BFSBFS4.4.熟练掌握：最短路算法（熟练掌握：最短路算法（DijkstraDijkstra算法算法）5.5.掌握：掌握：最小生成树最小生成树的两种算法及的两种算法及拓扑排序拓扑排序算法的思想算法的思想教学目标教学目标北京林业大学信息学院北京林业大学信息学院6.1 6.1 图的定义和术语图的定义和术

3、语V1V2V3V4G1V1V2V4V5G2V3图：图：Graph=(V,E)V：顶点：顶点(数据元素数据元素)的的有穷非空有穷非空集合；集合；E：边的：边的有穷有穷集合。集合。无向图：无向图：有向图：有向图：每条边都是无方向的每条边都是无方向的每条边都是有方向的每条边都是有方向的北京林业大学信息学院北京林业大学信息学院完全图：完全图：任意两个点都有一条边相连任意两个点都有一条边相连无向完全图无向完全图有向完全图有向完全图北京林业大学信息学院北京林业大学信息学院稀疏图稀疏图：有很少边或弧的图。：有很少边或弧的图。稠密图稠密图：有较多边或弧的图。：有较多边或弧的图。网网：边：边/弧带权的图。弧带权

4、的图。邻接邻接：有边：有边/弧相连的两个顶点之间的关系。弧相连的两个顶点之间的关系。存在存在(vi,vj)，则称，则称vi和和vj互为互为邻接点邻接点；存在存在，则称，则称vi邻接到邻接到vj，vj邻接于邻接于vi 关联关联(依附依附)：边边/弧与顶点之间的关系。弧与顶点之间的关系。存在存在(vi,vj)/，则称该边则称该边/弧关联于弧关联于vi和和vj北京林业大学信息学院北京林业大学信息学院顶点的度顶点的度：与该顶点相关联的边的数目，记为：与该顶点相关联的边的数目，记为TD(v)在在有向图有向图中中,顶点的度等于该顶点的顶点的度等于该顶点的入度入度与与出度出度之和。之和。顶点顶点 v 的入度

5、的入度是以是以 v 为终点的有向边的条数为终点的有向边的条数,记作记作 ID(v)顶点顶点 v 的出度的出度是以是以 v 为始点的有向边的条数为始点的有向边的条数,记作记作OD(v)问：问：当有向图中仅当有向图中仅1 1个顶点的入度为个顶点的入度为0,0,其其余顶点的入度均为余顶点的入度均为1 1，此时是何形状？，此时是何形状？答：答：是树！而且是一棵有向树！是树！而且是一棵有向树！北京林业大学信息学院北京林业大学信息学院路径路径：接续的边构成的顶点序列。：接续的边构成的顶点序列。路径长度路径长度：路径上边或弧的数目：路径上边或弧的数目/权值之和。权值之和。回路回路(环环)：第一个顶点和最后一

6、个顶点相同的路径。第一个顶点和最后一个顶点相同的路径。简单路径：简单路径：除路径起点和终点可以相同外，其余顶点均不相同除路径起点和终点可以相同外，其余顶点均不相同的路径。的路径。简单回路简单回路(简单环简单环)：除路径起点和终点相同外，其余顶点均不除路径起点和终点相同外，其余顶点均不相同的路径。相同的路径。北京林业大学信息学院北京林业大学信息学院 非连通图非连通图 连通图连通图 强连通图强连通图 非强连通图非强连通图 V0V0 V1V1 V2V2 V3V3 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1 V5V5

7、 V4V4在无（有）向图在无（有）向图G=(V,E)G=(V,E)中，若对任何两个顶中，若对任何两个顶点点 v v、u u 都存在从都存在从v v 到到 u u 的路径，则称的路径，则称G G是连通图是连通图（强连通图）。（强连通图）。北京林业大学信息学院北京林业大学信息学院(a)(a)(b)(b)(c)(c)V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2设有两个图设有两个图G=G=（V V，EE）、）、G1=G1=（V1V1，E1E1），），若若V1V1 V V，E1 E1 E E，则称，则

8、称 G1G1是是G G的子图。的子图。例例:(b):(b)、(c)(c)是是 (a)(a)的子图的子图图中边或弧所具有的相关数称为权。表明从一个顶图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。点到另一个顶点的距离或耗费。带权的图称为带权的图称为。北京林业大学信息学院北京林业大学信息学院非连通图非连通图 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4无向图无向图G G 的极大连通子图称为的极大连通子图称为G G的连通分量。的连通分量。极大连通子图意思是：该子图是极大连通子图意思是：该子图是 G G 连通子图，将连通子图，将G G 的任何不在该子图中的顶点加入

9、，子图不再连通。的任何不在该子图中的顶点加入，子图不再连通。V0V0 V2V2 V3V3 V1V1 V5V5 V4V4连通分量连通分量北京林业大学信息学院北京林业大学信息学院有向图有向图G G 的极大强连通子图称为的极大强连通子图称为G G的强连通分量。的强连通分量。极大强连通子图意思是：该子图是极大强连通子图意思是：该子图是G G的强连通子图的强连通子图，将，将D D的任何不在该子图中的顶点加入，子图不再的任何不在该子图中的顶点加入，子图不再是强连通的。是强连通的。强连通分量强连通分量 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1北京林业大学信息学院北京林业

10、大学信息学院：该子图是：该子图是G G 的连通子图，在该子图的连通子图，在该子图中删除任何一条边，子图不再连通。中删除任何一条边，子图不再连通。包含无向图包含无向图G G 所有顶点的极小连通子图。所有顶点的极小连通子图。对非连通图，由各个连通分量的生成树对非连通图，由各个连通分量的生成树的集合。的集合。连通图连通图 G1G1G1G1的生成树的生成树 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2北京林业大学信息学院北京林业大学信息学院6.2 6.2 案例引入案例引入案例案例6.1 6.1：六度

11、空间理论：六度空间理论你和任何一个陌生人之你和任何一个陌生人之间所间隔的人不会超过间所间隔的人不会超过6 6个，也就是说，最多通个，也就是说，最多通过过6 6个中间人你就能够认个中间人你就能够认识任何一个陌生人。识任何一个陌生人。北京林业大学信息学院北京林业大学信息学院6.3 6.3 图的类型定义图的类型定义CreateGraph(&G,V,VR)CreateGraph(&G,V,VR)初始条件：初始条件：V V是图的顶点集，是图的顶点集，VRVR是图中弧的集合。是图中弧的集合。操作结果：按操作结果：按V V和和VRVR的定义的定义构造图构造图G G。DFSTraverse(G)DFSTrav

12、erse(G)初始条件：图初始条件：图G G存在。存在。操作结果：对图进行操作结果：对图进行深度深度优先遍历。优先遍历。BFSTraverse(G)BFSTraverse(G)初始条件：图初始条件：图G G存在。存在。操作结果：对图进行操作结果：对图进行广度广度优先遍历。优先遍历。北京林业大学信息学院北京林业大学信息学院6.4 6.4 图的存储结构图的存储结构邻接表邻接表邻接多重表邻接多重表十字链表十字链表链式存储结构：链式存储结构：顺序存储结构：顺序存储结构：数组表示法（邻接矩阵）数组表示法（邻接矩阵）多重链表多重链表重点介绍：重点介绍：北京林业大学信息学院北京林业大学信息学院 ,),(,.

13、否否则则或或者者如如果果01AEjiEjijiEdgev建立一个建立一个顶点表顶点表（记录各个顶点信息）（记录各个顶点信息）和一个和一个邻接矩邻接矩阵阵（表示各个顶点之间关系）（表示各个顶点之间关系）。v设图设图 A=(A=(V V,E E)有有 n n 个顶点，则图的邻接矩阵是个顶点，则图的邻接矩阵是一个二维数组一个二维数组 A.EdgennA.Edgenn，定义为：，定义为：数组（邻接矩阵）表示法数组（邻接矩阵）表示法北京林业大学信息学院北京林业大学信息学院邻接矩阵：A.Edge=（v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00

14、 0 0 0 00 0 0 0 0分析分析1 1：无向图的邻接矩阵是无向图的邻接矩阵是对称对称的；的；分析分析2 2：顶点顶点i i 的的度度第第 i i 行行(列列)中中1 1 的个数的个数；特别：特别：完全图完全图的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为0 0，其余，其余1 1。0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0顶点表：无向图的邻接矩阵表示法无向图的邻接矩阵表示法v1v2v3v5v4v4北京林业大学信息学院北京林业大学信息学院有向图的邻接

15、矩阵有向图的邻接矩阵可能是不对称可能是不对称的。的。顶点的顶点的出度出度=第第i i行元素之和行元素之和 顶点的顶点的入度入度=第第i i列元素之和列元素之和 顶点的顶点的度度=第第i i行元素之和行元素之和+第第i i列元素之和列元素之和 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为尾的弧为尾的弧(即出度边）；即出度边）；第第i i列含义：以结点列含义：以结点v vi i为头的弧为头的弧(即

16、入度边）。即入度边）。顶点表：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 有向图的邻接矩阵表示法有向图的邻接矩阵表示法北京林业大学信息学院北京林业大学信息学院定义为：定义为：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 网（即有权图）的邻接矩阵表示法网（即有权图）的邻接矩阵表示法北京林业大学

17、信息学院北京林业大学信息学院优点：优点：容易实现图的操作，如：求某顶点的度、判容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边、找顶点的邻接点等等。断顶点之间是否有边、找顶点的邻接点等等。缺点：缺点：n n个顶点需要个顶点需要n n*n n个单元存储边个单元存储边;空间效率为空间效率为O(nO(n2 2)。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。邻接矩阵表示法的特点邻接矩阵表示法的特点北京林业大学信息学院北京林业大学信息学院/用两个数组分别存储顶点表和邻接矩阵用两个数组分别存储顶点表和邻接矩阵#define MaxInt 32767 /表示极大值，即表示极大值，即#defi

18、ne MVNum 100 /最大顶点数最大顶点数 typedef char VerTexType;/假设顶点的数据类型为字符型假设顶点的数据类型为字符型 typedef int ArcType;/假设边的权值类型为整型假设边的权值类型为整型 typedef struct VerTexType vexsMVNum;/顶点表顶点表 ArcType arcsMVNumMVNum;/邻接矩阵邻接矩阵 int vexnum,arcnum;/图的当前点数和边数图的当前点数和边数 AMGraph;邻接矩阵的存储表示邻接矩阵的存储表示北京林业大学信息学院北京林业大学信息学院（1 1）输入）输入总顶点数和总边数

19、总顶点数和总边数。（2 2）依次输入）依次输入点的信息存入顶点表点的信息存入顶点表中。中。（3 3）初始化邻接矩阵初始化邻接矩阵，使每个权值初始化为极大值。，使每个权值初始化为极大值。（4 4）构造邻接矩阵构造邻接矩阵。【算法思想算法思想】采用邻接矩阵表示法创建无向网采用邻接矩阵表示法创建无向网4 5A B C DA B 500A C 200A D 150B C 400C D 600 北京林业大学信息学院北京林业大学信息学院Status CreateUDN(AMGraph&G)/采用邻接矩阵表示法，创建无向网采用邻接矩阵表示法，创建无向网G cinG.vexnumG.arcnum;/输入总顶点

20、数，总边数输入总顶点数，总边数 for(i=0;iG.vexsi;/依次输入点的信息依次输入点的信息 for(i=0;iG.vexnum;+i)/初始化邻接矩阵，边的权值均置为极大值初始化邻接矩阵，边的权值均置为极大值 for(j=0;jG.vexnum;+j)G.arcsij=MaxInt;for(k=0;kv1v2w;/输入一条边依附的顶点及权值输入一条边依附的顶点及权值 i=LocateVex(G,v1);j=LocateVex(G,v2);/确定确定v1和和v2在在G中的位置中的位置 G.arcsij=w;/边边的权值置为的权值置为w G.arcsji=G.arcsij;/置置的对称边

21、的对称边的权值为的权值为w /for return OK;/CreateUDN【算法描述算法描述】4 5A B C DA B 500A C 200A D 150B C 400C D 600北京林业大学信息学院北京林业大学信息学院 int LocateVex(MGraph G,VertexType u)/存在则返回存在则返回u在顶点表中的下标在顶点表中的下标;否则返回否则返回-1 int i;for(i=0;iG.vexnum;+i)if(u=G.vexsi)return i;return-1;4 5A B C DA B 500A C 200A D 150B C 400C D 600北京林业大学

22、信息学院北京林业大学信息学院v 对每个顶点对每个顶点vi 建立一个建立一个单链表单链表，把与，把与vi有关联的有关联的边的信息链接边的信息链接起来，每个结点设为起来，每个结点设为3个域；个域；adjvex nextarcinfodatafirstarc邻接点域邻接点域，表表示示vi一个邻接一个邻接点的位置点的位置链域链域，指向指向vi下一个边下一个边或弧的结点或弧的结点数据域数据域，与与边有关信息边有关信息（如权值）（如权值）数据域数据域，存存储顶点储顶点vi 信信息息链域链域，指向，指向单链表的第单链表的第一个结点一个结点邻接表（链式）表示法邻接表（链式）表示法北京林业大学信息学院北京林业大

23、学信息学院0123413341420注：注：邻接表不唯一邻接表不唯一，因各个边结点的链入顺序是任意的，因各个边结点的链入顺序是任意的v1v2v3v4v5231420无向图的邻接表表示无向图的邻接表表示空间效率为空间效率为O(n+2e)O(n+2e)。若是稀疏图若是稀疏图(en(eG.vexnumG.arcnum;/输入总顶点数，总边数输入总顶点数，总边数 for(i=0;i G.verticesi.data;/输入顶点值输入顶点值 G.verticesi.firstarc=NULL;/初始化表头结点的指针域为初始化表头结点的指针域为NULL /for for(k=0;kv1v2;/输入一条边依

24、附的两个顶点输入一条边依附的两个顶点 i=LocateVex(G,v1);j=LocateVex(G,v2);p1=new ArcNode;/生成一个新的边结点生成一个新的边结点*p1 p1-adjvex=j;/邻接点序号为邻接点序号为j p1-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p1;/将新结点将新结点*p1插入顶点插入顶点vi的边表头部的边表头部 p2=new ArcNode;/生成另一个对称的新的边结点生成另一个对称的新的边结点*p2 p2-adjvex=i;/邻接点序号为邻接点序号为i p2-nextarc=G.verti

25、cesj.firstarc;G.verticesj.firstarc=p2;/将新结点将新结点*p2插入顶点插入顶点vj的边表头部的边表头部 /for return OK;/CreateUDG【算法描述算法描述】北京林业大学信息学院北京林业大学信息学院优点：优点：空间效率高，容易寻找顶点的邻接点；空间效率高，容易寻找顶点的邻接点；缺点：缺点：判断两顶点间是否有边或弧，需搜索两结判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。点对应的单链表，没有邻接矩阵方便。邻接表表示法的特点邻接表表示法的特点北京林业大学信息学院北京林业大学信息学院v1v2v3v5v4v443210133

26、41420v5v4v3v2v1231420（v1 v2 v3 v4 v5 ）v1v2v3v4v50 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 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0邻接矩阵与邻接表表示法的关系邻接矩阵与邻接表表示法的关系1.1.联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数

27、。北京林业大学信息学院北京林业大学信息学院2.2.区别：区别：对于任一确定的无向图，邻接矩阵是对于任一确定的无向图，邻接矩阵是唯一唯一的（行列的（行列号与顶点编号一致），但邻接表号与顶点编号一致），但邻接表不唯一不唯一（链接次序（链接次序与顶点编号无关）。与顶点编号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)O(n+e)。3.3.用途：用途：邻接矩阵多用于邻接矩阵多用于稠密图稠密图；而邻接表多用于；而邻接表多用于稀稀疏图疏图邻接矩阵与邻接表表示法的关系邻接矩阵与邻接表表示法的关系datafirstinfi

28、rstoutinfo tailvex headvex边结点表中的结点的表示：边结点表中的结点的表示：结点表中的结点的表示：结点表中的结点的表示：data：结点的数据结点的数据域域，保存结点的数据值。，保存结点的数据值。firstin:结点的指针结点的指针域域，给出自该结点出发的，给出自该结点出发的的第一条边的边结点的地址。的第一条边的边结点的地址。firstout：结点的指针场，给出进入该结点的第结点的指针场，给出进入该结点的第一条边的一条边的 边结点的地址。边结点的地址。info:边结点的数据边结点的数据域域，保存边的权值等。，保存边的权值等。hlinktlinktailvex:本条边的出发

29、结点本条边的出发结点 的的地址。地址。headvex:本条边的终止结点本条边的终止结点 的地址。的地址。hlink:终止终止结点相同的边结点相同的边 中的下一条边的地址。中的下一条边的地址。tlink:出发出发结点相同的边结点相同的边 中的下一条边的地址。中的下一条边的地址。十字链表十字链表-用于有向图用于有向图十字链表十字链表datafirstedgemarkivex ilink边结点表中的结点的表示：边结点表中的结点的表示：结点表中的结点的表示：结点表中的结点的表示：data:结点的数据结点的数据域域，保存结点的数据值。，保存结点的数据值。firstedge:结点的指针结点的指针域域，给出

30、自该结点出发的的第一条边的，给出自该结点出发的的第一条边的 边结点的地址。边结点的地址。info:边结点的数据边结点的数据域域，保存边的，保存边的 权值等。权值等。mark:边结点的标志域，用于标识边结点的标志域，用于标识 该条边是否被访问过。该条边是否被访问过。jvexinfoivex:本条边本条边依附的一依附的一 个个结点的地址结点的地址。ilink:依附于该结点（地依附于该结点（地 址由址由ivex给出）的给出）的 边中的下一条边的边中的下一条边的 的地址。的地址。jlinkjvex:本条边本条边依附的另依附的另 一个一个结点的地址结点的地址。jlink:依附于该结点（地依附于该结点（地

31、 址由址由jvex给出）的给出）的 边中的下一条边的边中的下一条边的 的地址。的地址。十字链表十字链表-用于无向图用于无向图十字链表十字链表 2022年12月22日 北京林业大学信息学院北京林业大学信息学院遍历定义：遍历定义：从已给的连通图中某一顶点出发，沿着一从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做问一次，就叫做图的图的基本运算基本运算。遍历实质：遍历实质：找每个顶点的邻接点的过程。找每个顶点的邻接点的过程。图的特点：图的特点：图中可能存在图中可能存在回路回路，且图的任一顶点都可，且图的任一顶点都可

32、能与其它顶点相通，在访问完某个顶点之后可能能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边会沿着某些边又回到了曾经访问过的顶点又回到了曾经访问过的顶点6.5 6.5 图的遍历图的遍历北京林业大学信息学院北京林业大学信息学院人工智能人工智能-搜索问题搜索问题有有3 3个传教士和个传教士和3 3个野人来到河边准备渡河，河个野人来到河边准备渡河，河岸有一条船，每次最多可坐岸有一条船，每次最多可坐2 2个人。问传教士为安全个人。问传教士为安全起见，应如何规划摆渡方案，使得在任何时刻，在起见，应如何规划摆渡方案，使得在任何时刻，在河两岸以及船上传教士人数不能少于野人人数？河两岸以及船上传教士人数不

33、能少于野人人数？在每一次渡河后，都会有几种渡河方案供选择在每一次渡河后，都会有几种渡河方案供选择，究竟哪种方案最有利？，究竟哪种方案最有利？这就是搜索问题。这就是搜索问题。北京林业大学信息学院北京林业大学信息学院适用情况：适用情况：难以获得求解所需的全部信息；更没有现成的难以获得求解所需的全部信息；更没有现成的算法可供求解使用。算法可供求解使用。人工智能人工智能-搜索问题搜索问题概念：概念：依靠经验，利用已有知识，根据问题的实际情况，依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的

34、过程称为搜索，使问题得以解决的过程称为搜索北京林业大学信息学院北京林业大学信息学院对这类问题，一般我们都转换为状态空对这类问题，一般我们都转换为状态空间的搜索问题。间的搜索问题。如如传教士和野人问题，传教士和野人问题，可用在河左岸的可用在河左岸的传教士人数、野人人数和船的情况来表示。传教士人数、野人人数和船的情况来表示。即，初始时状态为（即，初始时状态为（3 3，3 3，1 1），结束状态为），结束状态为（0 0，0 0，0 0），而中间状态可表示为（），而中间状态可表示为（2 2，2 2，0 0）、（）、（3 3，2 2，1 1）等等。）等等。北京林业大学信息学院北京林业大学信息学院这类问题

35、的解，这类问题的解，就是一个合法状态的就是一个合法状态的序列，其中序列中第序列，其中序列中第一个状态是问题的初一个状态是问题的初始状态，而最后一个始状态，而最后一个状态则是问题的结束状态则是问题的结束状态。状态。SgS0解路径解路径搜索空间搜索空间全状态空间全状态空间北京林业大学信息学院北京林业大学信息学院例例:8:8数码难题数码难题 在一个在一个3 33 3的方框内放有的方框内放有8 8个编号的小方块，紧邻空位的小个编号的小方块，紧邻空位的小方块可以移入到空位上，通过平移小方块可将某一布局变换为另方块可以移入到空位上，通过平移小方块可将某一布局变换为另一布局。请给出从初始状态到目标状态移动小

36、方块的操作序列。一布局。请给出从初始状态到目标状态移动小方块的操作序列。2318476512384765北京林业大学信息学院北京林业大学信息学院搜索引擎的两种基本抓取策略搜索引擎的两种基本抓取策略 搜索引擎蜘蛛通过跟踪链接访问网页，获得页面HTML代码存入数据库爬行和抓取 索引程序对抓取来的页面数据进行文字提取、中文分词、索引等处理，以备排名程序调用预处理 用户输入关键词后，排名程序调用索引库数据，计算相关性，然后按一定格式生成搜索结果页面排名 2022年12月22日 北京林业大学信息学院北京林业大学信息学院爬行抓取爬行抓取索引索引排序返回排序返回搜索引擎的两种基本抓取策略搜索引擎的两种基本抓

37、取策略 -深度优先深度优先如封建帝位的继承。不能深入的情况下才考虑其他分支的策略搜索引擎的两种基本抓取策略搜索引擎的两种基本抓取策略 -广度优先广度优先类似长幼有序的规则两种策略结合两种策略结合=先广后深先广后深 +权重优先权重优先先把这个页面所有的链接都抓取一次先把这个页面所有的链接都抓取一次再根据这些再根据这些URLURL的权重来判定的权重来判定URLURL的权重高，就采用深度优先，的权重高，就采用深度优先，URLURL权重低，就采用宽度优先或者不抓取权重低，就采用宽度优先或者不抓取 2022年12月22日 北京林业大学信息学院北京林业大学信息学院图常用的遍历：图常用的遍历：深度优先搜索深

38、度优先搜索广度优先搜索广度优先搜索解决思路：解决思路：设置设置辅助数组辅助数组 visitedvisited n n，用来标记每，用来标记每个被访问过的顶点。个被访问过的顶点。初始状态为初始状态为0 0i i 被访问，改被访问，改 visitedvisited i i 为为1 1，防止被多次访问，防止被多次访问怎样避免重复访问？怎样避免重复访问？2022年12月22日 北京林业大学信息学院北京林业大学信息学院基本思想：基本思想：仿树的先序遍历过程。仿树的先序遍历过程。v1v2v3v8v7v6v4v5起点起点深度优先搜索深度优先搜索(DFS(DFS Depth_First Search)Dept

39、h_First Search)2022年12月22日 北京林业大学信息学院北京林业大学信息学院深度优先搜索的步骤深度优先搜索的步骤简单归纳：简单归纳：访问起访问起始点始点v v;若若v v的的第第1 1个个邻接点没访问过，邻接点没访问过，深度遍历深度遍历此邻接此邻接点；点；若当前邻接点已访问过，再找若当前邻接点已访问过，再找v v的第的第2 2个邻接点个邻接点重新遍历。重新遍历。2022年12月22日 北京林业大学信息学院北京林业大学信息学院2 21 13 34 45 56 6深度优先搜索练习深度优先搜索练习 2022年12月22日 北京林业大学信息学院北京林业大学信息学院深度优先搜索的步骤深

40、度优先搜索的步骤详细归纳：详细归纳：E在访问图中某一起始顶点在访问图中某一起始顶点 v 后，后，由由 v 出发，访问出发，访问它的任一邻接顶它的任一邻接顶点点 w1；E再从再从 w1 出发，访问出发，访问与与 w1邻接邻接但还但还未被访问未被访问过的顶点过的顶点 w2；E然后再从然后再从 w2 出发，进行类似的出发，进行类似的访问，访问，E如此进行下去，直至到达所有如此进行下去，直至到达所有的邻接顶点都被访问过的顶点的邻接顶点都被访问过的顶点 u 为止。为止。起点起点 2022年12月22日 北京林业大学信息学院北京林业大学信息学院深度优先搜索的步骤深度优先搜索的步骤详细归纳：详细归纳：E接着

41、，退回一步，接着，退回一步，退到前一次退到前一次刚访问过的顶点刚访问过的顶点，看是否还有其，看是否还有其它没有被访问的邻接顶点。它没有被访问的邻接顶点。如果有，如果有，则访问此顶点，之后则访问此顶点，之后再从此顶点出发，进行与前述类再从此顶点出发，进行与前述类似的访问；似的访问；如果没有，如果没有，就就再退回一步再退回一步进行进行搜索。重复上述过程，直到连通搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。图中所有顶点都被访问过为止。起点起点 2022年12月22日 北京林业大学信息学院北京林业大学信息学院讨论讨论1 1：计算机如何实现：计算机如何实现DFSDFS？1 2345610 0

42、00000 0000030 0000040 0000050 0000060 00000000000123456010000100001000010101邻邻接接矩矩阵阵A辅助数组辅助数组 visited n 开辅助数组开辅助数组 visited n！1 23 456100000 00300 00400 005000060 00002 21 13 34 45 56 6 2022年12月22日 北京林业大学信息学院北京林业大学信息学院void DFS(AMGraph G,int v)/图图G为邻接矩阵类型为邻接矩阵类型 coutv;visitedv=true;/访问第访问第v个顶点个顶点 for(

43、w=0;w G.vexnum;w+)/依次检查邻接矩阵依次检查邻接矩阵v所在的行所在的行 if(G.arcsvw!=0)&(!visitedw)DFS(G,w);/w是是v的邻接点，如果的邻接点，如果w未访问，则递归调用未访问，则递归调用DFS 可以用递归算法！可以用递归算法！2022年12月22日 北京林业大学信息学院北京林业大学信息学院00000123辅助数组辅助数组 visited n 1000110011101111照样借用照样借用visited n！起点起点0123 2022年12月22日 北京林业大学信息学院北京林业大学信息学院void DFS(ALGraph G,int v)/图

44、图G为邻接表类型为邻接表类型 coutadjvex;/表示表示w是是v的邻接点的邻接点 if(!visitedw)DFS(G,w);/如果如果w未访问，则递归调用未访问，则递归调用DFS p=p-nextarc;/p指向下一个边结点指向下一个边结点 仍可用递归算法仍可用递归算法 2022年12月22日 北京林业大学信息学院北京林业大学信息学院n用用邻接矩阵邻接矩阵来表示图，遍历图中每一个顶点都要来表示图，遍历图中每一个顶点都要从头扫描从头扫描该顶点所在行，时间复杂度为该顶点所在行，时间复杂度为O(O(n n2 2)。n用用邻接表邻接表来表示图，虽然有来表示图，虽然有 2 2e e 个表结点，但

45、只个表结点，但只需扫描需扫描 e e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问 n n个个头结点的时间，时间复杂度为头结点的时间，时间复杂度为O(O(n n+e e)。结论：结论：稠密图稠密图适于在邻接矩阵上进行深度遍历；适于在邻接矩阵上进行深度遍历；稀疏图稀疏图适于在邻接表上进行深度遍历。适于在邻接表上进行深度遍历。DFSDFS算法效率分析算法效率分析 2022年12月22日 北京林业大学信息学院北京林业大学信息学院基本思想：基本思想：仿树的层次遍历过程仿树的层次遍历过程广度优先搜索广度优先搜索(BFS(BFS Breadth_First Search)Breadth_Fir

46、st Search)v1v2v3v8v7v6v4v5起点起点 2022年12月22日 北京林业大学信息学院北京林业大学信息学院简单归纳：简单归纳：在访问了在访问了起始点起始点v v之后，依次访问之后，依次访问 v v的邻接点的邻接点；然后再依次访问然后再依次访问这些顶点中未被访问过的邻接点这些顶点中未被访问过的邻接点；直到所有顶点都被访问直到所有顶点都被访问过为止。过为止。广度优先搜索是一种广度优先搜索是一种分层分层的搜索过程，每向前的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。那样有回退的情况。因此，广度优先搜索因此，广度

47、优先搜索不是一个递归不是一个递归的过程，其的过程，其算法也不是递归的。算法也不是递归的。广度优先搜索的步骤广度优先搜索的步骤 2022年12月22日 北京林业大学信息学院北京林业大学信息学院 2022年12月22日 北京林业大学信息学院北京林业大学信息学院（1 1）从图中某个顶点）从图中某个顶点v v出发，访问出发，访问v v，并置，并置visitedvisitedv v 的值为的值为truetrue，然后将，然后将v v进队。进队。（2 2）只要队列不空，则重复下述处理。）只要队列不空，则重复下述处理。队头顶点队头顶点u u出队。出队。依次检查依次检查u u的所有邻接点的所有邻接点w w，如

48、果，如果visitedvisitedw w 的值为的值为falsefalse，则访问，则访问w w，并置，并置visitedvisitedw w 的值为的值为truetrue，然后将，然后将w w进队。进队。【算法思想算法思想】2022年12月22日 北京林业大学信息学院北京林业大学信息学院讨论讨论1 1：计算机如何实现：计算机如何实现BFSBFS？邻接表邻接表除辅助数组除辅助数组visited n 外，外，还需再开一辅助队列还需再开一辅助队列起点起点辅助队列辅助队列v2已访问过了已访问过了BFS BFS 遍历结果遍历结果入队！入队！2022年12月22日 北京林业大学信息学院北京林业大学信息

49、学院void BFS(Graph G,int v)/按广度优先非递归遍历连通图按广度优先非递归遍历连通图G cout=0;w=NextAdjVex(G,u,w)if(!visitedw)/w为为u的尚未访问的邻接顶点的尚未访问的邻接顶点 coutw;visitedw=true;EnQueue(Q,w);/w进队进队 /if /while/BFS【算法描述算法描述】2022年12月22日 北京林业大学信息学院北京林业大学信息学院 如果使用邻接矩阵，则如果使用邻接矩阵，则BFS对于每一个被访问到的顶点对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（，都要循环检测矩阵中的整整一行（n 个元素

50、），总个元素），总的时间代价为的时间代价为O(n2)。用邻接表来表示图，虽然有用邻接表来表示图，虽然有 2e 个表结点，但只需扫描个表结点，但只需扫描 e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问 n个头结点的时间，个头结点的时间，时间复杂度为时间复杂度为O(n+e)。BFSBFS算法效率分析算法效率分析 2022年12月22日 北京林业大学信息学院北京林业大学信息学院 已知图的邻接表，分别给出用深度优先搜索和广度优已知图的邻接表，分别给出用深度优先搜索和广度优先搜索从先搜索从顶点顶点3出发出发的遍历序列。的遍历序列。1 2 4 1 3 6 2 4 6 5 3 5 1 6 5