1、17.3 7.3 图的遍历图的遍历遍历：遍历：从已给的连通图中某一顶点出发，沿着一些边，从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做就叫做图的图的基本运算。基本运算。遍历实质：遍历实质：找每个顶点的邻接点的过程。找每个顶点的邻接点的过程。图的特点：图的特点：图中可能存在图中可能存在回路，回路，且图的任一顶点都可能与且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点些边又回到了曾经访问过的顶点解决思路：解决思路
2、：可设置一个可设置一个辅助数组辅助数组 visited n，用来标，用来标记每个被访问过的顶点。它的初始状态为记每个被访问过的顶点。它的初始状态为falsefalse，在图的遍历过程中，一旦某一个顶点在图的遍历过程中，一旦某一个顶点i 被访问，就被访问，就立即改立即改 visited i为为truetrue，防止它被重复访问。，防止它被重复访问。怎样避免重复访问？怎样避免重复访问？2深度优先搜索深度优先搜索和和广度优先搜索广度优先搜索 图常用的遍历：图常用的遍历：一、深度优先搜索一、深度优先搜索(DFS)(DFS)Depth_First Search基本思想：基本思想：类似于树的先根遍历过程。
3、类似于树的先根遍历过程。1、连通图的深度优先搜索遍历、连通图的深度优先搜索遍历步骤：步骤：访问起始点访问起始点 v;v;依次从依次从v v的未被访问的邻接点出发深度优先遍历的未被访问的邻接点出发深度优先遍历图直至图中所有和图直至图中所有和v v有路径相通的顶点都被访问有路径相通的顶点都被访问到。到。3v1v2v3v8v7v6v4v5起点起点应退回到应退回到V8V8，因为，因为V2V2已有标记已有标记void DFS(Graph G,int v)/从顶点从顶点v v出发，深度优先遍历出发，深度优先遍历G G visitedv=TRUE;VisitFunc(v);for(w=FirstAdjVex
4、(G,v);w!=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对对v的尚未访问的邻接顶点的尚未访问的邻接顶点w递归调用递归调用DFS/DFS4 对于无向图，这个算法可以对于无向图，这个算法可以遍历到遍历到v v顶点所在的连通顶点所在的连通分量中的所有顶点分量中的所有顶点，而与，而与v v顶点不在一个连通分量中的顶点不在一个连通分量中的所有顶点遍历不到；所有顶点遍历不到；对于有向图可以对于有向图可以遍历到起始顶点遍历到起始顶点v v能够到达的所有顶能够到达的所有顶点。点。若希望遍历到图中的所有顶点，就需要在上述深度若希望遍历到图中的所有顶点，就需要在上
5、述深度优先遍历算法的基础上，优先遍历算法的基础上，增加对每个顶点访问状态的增加对每个顶点访问状态的检测。检测。2、非连通图的深度优先搜索遍历、非连通图的深度优先搜索遍历步骤：步骤：访问起始点访问起始点 v v及图中所有和及图中所有和v v有路径相通的顶点。有路径相通的顶点。如果图中尚有顶点未被访问，则以该顶点为起始点，如果图中尚有顶点未被访问，则以该顶点为起始点，进行深度优先搜索遍历。重复上述过程，直至所有进行深度优先搜索遍历。重复上述过程，直至所有顶点都已被访问。顶点都已被访问。5abchdekfgF F F F F F F F FT TT T T TT T Tach d kfe bgach
6、kfedbg访问标志访问标志:访问次序访问次序:例例2:2:0 1 2 3 4 5 6 7 88123456706void DFSTraverse(Graph G,Status(*Visit)(int v)/对图对图 G 作深度优先遍历作深度优先遍历。VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化访问标志数组初始化 for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);/对尚未访问的顶点调用对尚未访问的顶点调用DFS7（）（1）如果用邻接矩阵来表示图，遍历图中每一个）如果用邻接矩阵来表
7、示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为顶点所需的时间为O(n2)。（2）如果用邻接表来表示图，虽然有）如果用邻接表来表示图，虽然有 2e 个表结点，个表结点，但只需扫描但只需扫描 e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问 n个头结点的时间，因此遍历图的时间复杂度为个头结点的时间，因此遍历图的时间复杂度为O(n+e)。结结 论：论：稠密图稠密图适于在邻接矩阵上进行深度优先遍历；适于在邻接矩阵上进行深度优先遍历；稀疏图稀疏图适于在邻接表上进行深度优先遍历。适于在邻接表上进行深度优先遍历。8二、广度
8、优先搜索二、广度优先搜索(BFS)(BFS)基本思想：基本思想：仿树的层次遍历过程。仿树的层次遍历过程。Breadth_First Search在访问了起始点在访问了起始点v v之后，之后，依次访问依次访问 v v的各个未曾访问的各个未曾访问过的邻接点过的邻接点；然后按这些顶点被访问的然后按这些顶点被访问的先后次序先后次序依次访问它们的依次访问它们的邻接点，直至图中所有和邻接点，直至图中所有和V V有路径相通的顶点都被访有路径相通的顶点都被访问到。问到。若此时图中尚有顶点未被访问若此时图中尚有顶点未被访问,则则另选图中一个未曾另选图中一个未曾被访问的顶点作起始点被访问的顶点作起始点，重复上述过
9、程，直至图中，重复上述过程，直至图中所有顶点都被访问到为止。所有顶点都被访问到为止。步骤：步骤：9v1v2v3v8v7v6v4v5 起点起点起点起点10讨论：讨论：答答:利用一个利用一个队列队列结构记录顶点访问顺序，将访问的结构记录顶点访问顺序，将访问的每个顶点入队，然后，再依次出队，出队时访问其邻每个顶点入队，然后，再依次出队，出队时访问其邻接点并将邻接点入队。接点并将邻接点入队。（2 2）如何避免重复访问某个顶点？）如何避免重复访问某个顶点？（1 1）在广度优先遍历中，要求先被访问的顶点其邻接点）在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，应采用何种方式记录顶点访问顺序？也被
10、优先访问，应采用何种方式记录顶点访问顺序？答：创建一个答：创建一个一维数组一维数组visited0.n-1visited0.n-1（n n是图中顶是图中顶点的数目），用来记录每个顶点是否已经被访问过。点的数目），用来记录每个顶点是否已经被访问过。（3 3）广度优先搜索有回退的情况吗？）广度优先搜索有回退的情况吗？11答：广度优先搜索是一种分层的搜索过程，每向前走答：广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此广度优先搜索不是一个递归的过程，退的情况。因此广度优先搜索不是一个递归的过程，其算法
11、也不是递归的。其算法也不是递归的。void BFSTraverse(Graph G,Status(*Visit)(int v)for(v=0;vG.vexnum;+v)visitedv=FALSE;/初始化访问标志初始化访问标志 InitQueue(Q);/置空的辅助队列置空的辅助队列Q for(v=0;vG.vexnum;+v)if(!visitedv)/v 尚未访问尚未访问 /BFSTraverse12visitedv=TRUE;Visit(v);/访问访问vEnQueue(Q,v);/v入队列入队列while(!QueueEmpty(Q)DeQueue(Q,u);/队头元素出队并置为队头
12、元素出队并置为u for(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;Visit(w);EnQueue(Q,w);/访问的顶点访问的顶点w入队列入队列 /if/while13 如果使用邻接表来表示图，则如果使用邻接表来表示图，则BFS循环的总时间代价为循环的总时间代价为 d0+d1+dn-1=O(e)，其中的其中的 di 是顶点是顶点 i 的度的度。如果使用邻接矩阵，则如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（都要循环检测矩阵中的整整
13、一行（n 个元素），总的个元素），总的时间代价为时间代价为O(n2)。（）空间复杂度相同，都是空间复杂度相同，都是O(n)(O(n)(借用堆栈或队列装借用堆栈或队列装n n个个顶点）；顶点）；时间复杂度只与存储结构（邻接矩阵或邻接表）有时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。关，而与搜索路径无关。14生成树：生成树：是一个极小连通子图，它含有图中全部顶点，是一个极小连通子图，它含有图中全部顶点，但只有但只有n-1n-1条边。条边。生成森林：生成森林：由若干棵由若干棵生成树生成树组成，含全部顶点，但构组成，含全部顶点，但构成这些树的边是最少的。成这些树的边是最少的。（对
14、有向或无向图（对有向或无向图均适用）均适用）思考思考1：若对连通图进行遍历，得到的是什么？：若对连通图进行遍历，得到的是什么？一个极小连通子图，即图的一个极小连通子图，即图的生成树生成树！由深度优先搜索得到的生成树，为由深度优先搜索得到的生成树，为深度优先生成树。深度优先生成树。由广度优先搜索得到的生成树，为由广度优先搜索得到的生成树，为广度优先生成树。广度优先生成树。思考思考2：若对非连通图进行遍历，得到的是什么？：若对非连通图进行遍历，得到的是什么？各连通分量的生成树，即图的各连通分量的生成树，即图的生成森林生成森林！7.4 7.4 图的连通性图的连通性15例例1 1：画出下图的生成树。：
15、画出下图的生成树。DFS生生成成树树v0v1v2v4v4v3邻邻接接表表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生生成成树树v0v1v3v2v4v0v1v2v4v4v3v0v1v2v4v4v316DEABCFJLMGHIK例例2 2：画出下图的生成森林（或极小连通子图）：画出下图的生成森林（或极小连通子图）下面选用邻接表方式来求深度优先生成森林下面选用邻接表方式来求深度优先生成森林17115 5M12L11K10J9I8H7G6F5E4D3C2B1A01201200437810661011126709121911112294710811DFS结果：结
16、果：ABMJLCF DE GHKI18DEGHIK子图子图1：子图子图2：子图子图3：AFCMLBJDEGHIKAFCMLBJ生生成成森森林林注：注：图的生成树（生成森林）不唯一！图的生成树（生成森林）不唯一！192.2.求无向网的最小生成树求无向网的最小生成树目标：目标：在网络的多个生成树中，寻找一个各边权值之在网络的多个生成树中，寻找一个各边权值之和最小的生成树。即和最小的生成树。即在在 e 条带权的边中选取条带权的边中选取 n-1 条边条边（不构成回路），使（不构成回路），使“权值之和权值之和”为最小。为最小。欲在欲在n n个城市间建立通信网，则个城市间建立通信网，则n n个城市应铺个城
17、市应铺n-1n-1条线路；条线路；但因为每条线路都会有对应的经济成本，而但因为每条线路都会有对应的经济成本，而n n个城市可个城市可能有能有n(n-1)/2 n(n-1)/2 条线路，那么，条线路，那么，如何选择如何选择n1n1条线路使条线路使总费用最少？总费用最少？典型用途：典型用途：V V是顶点集，是顶点集，U U是是V V的一个非空子集，若的一个非空子集，若(u(u0 0,v,v0 0)是一是一条条最小权值的边最小权值的边，其中，其中u u0 0 U U，v v0 0 V-UV-U；则：；则：(u(u0 0,v,v0 0)必在最小生成树上必在最小生成树上。20求求MST有多种算法，但最常
18、用的是以下两种：有多种算法，但最常用的是以下两种：v Prim（普里姆普里姆）算法）算法 v Kruskal（克鲁斯卡尔克鲁斯卡尔）算法）算法PrimPrim算法特点算法特点:顶点归并顶点归并，与边数无关，适于稠密网。，与边数无关，适于稠密网。KruskalKruskal算法特点：算法特点：边归并边归并，适于求稀疏网。，适于求稀疏网。对边操作对边操作对顶点操作对顶点操作普里姆算法的基本思想普里姆算法的基本思想:在生成树的构造过程中，图中在生成树的构造过程中，图中 n n 个顶点分属两个集个顶点分属两个集合：已落在生成树上的顶点集合：已落在生成树上的顶点集 U U 和尚未落在生成树和尚未落在生成
19、树上的顶点集上的顶点集V-U V-U，则应在所有连通，则应在所有连通U U中顶点和中顶点和V-UV-U中顶中顶点的边中选取权值最小的边。如图所示：点的边中选取权值最小的边。如图所示：21abcdegf例如例如:195141827168213ae12dcbgf7148531621所得生成树权值和所得生成树权值和=14+8+3+5+16+21=67集集合合U集集合合V-Uu0v022方法：方法：设置一个辅助数组，对当前设置一个辅助数组，对当前VU集中的每集中的每个顶点，记录和顶点集个顶点，记录和顶点集U中顶点相连接的代价最小中顶点相连接的代价最小的边。对每个属于的边。对每个属于V-U的顶点的顶点v
20、i，在辅助数组中存在辅助数组中存在一个相应的分量在一个相应的分量closedgei-1，它包含两个域，它包含两个域，其中其中lowcost存储该边上的权。显然，存储该边上的权。显然，closedgei-1.lowcostMincost(u,vi)|uU存储方式：存储方式：struct VertexType adjvex;/U集中的顶点序号集中的顶点序号 VRType lowcost;/边的权值边的权值 closedgeMAX_VERTEX_NUM;23closedge0123456AdjvexLowcostabcdegf195141827168213ae12dcb7aaa19141814例如例
21、如:e12ee8168d3dd7213c5 5 19 14 1819 5 7 12 5 3 7 3 8 21 14 12 8 16 21 2718 16 27 （a b c d e f g)PrimPrim算法的时间效率算法的时间效率O O（n n2 2）（a b c d e f g)24具体做法具体做法:先构造一个只含先构造一个只含 n 个顶点的子图个顶点的子图 SG，然后从，然后从权值最小的边开始，若它的添加不使权值最小的边开始，若它的添加不使SG 中产生回路，中产生回路，则在则在 SG 上加上这条边，如此重复，直至加上上加上这条边，如此重复，直至加上 n-1 条边条边为止。为止。考虑问题的出发点考虑问题的出发点:为使生成树上边的权值之和达到为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。最小，则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：KruskalKruskal算法的时间效率算法的时间效率O O（elogelog2 2e e）
