《图的遍历及生成树精品文稿.ppt》由会员分享，可在线阅读，更多相关《图的遍历及生成树精品文稿.ppt（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图的遍历及生成树图的遍历及生成树2010-3-3第1页，本讲稿共32页期末考试期末考试l长春工业大学长春工业大学 数据结构精品课程网站数据结构精品课程网站 习题解析习题解析lhttp:/ 7.3 图的遍历图的遍历 从图中从图中某某一顶点出发访遍图中其余顶点，且使每一顶点出发访遍图中其余顶点，且使每一个顶点仅被一个顶点仅被访问访问一次。这一过程就叫做一次。这一过程就叫做图的遍历图的遍历。抽象操作，抽象操作，可以是对结点进行的各种可以是对结点进行的各种处理，这里处理，这里简化为输出结点的数据。简化为输出结点的数据。第4页，本讲稿共32页图的遍历操作要解决的关键问题图的遍历操作要解决的关键问题1、在
2、图中，如何选取遍历的起始顶点？在图中，如何选取遍历的起始顶点？n 在在图图中，任何两个顶点之间都可能存在边，中，任何两个顶点之间都可能存在边，顶点顶点是是没有没有确确定的先后定的先后次序次序的，所以，顶点的编号不唯一。的，所以，顶点的编号不唯一。n 这里指这里指按顶点的存储顺序按顶点的存储顺序。解决方案：从编号小的顶点开始解决方案：从编号小的顶点开始 。2、因因图图中中可可能能存存在在回回路路，在在访访问问完完某某个个顶顶点点之之后后会会沿沿着着某某些些边边又回到了曾经访问过的顶点又回到了曾经访问过的顶点。那么那么如何避免顶点的重复访问如何避免顶点的重复访问？解决方案：附设访问标志数组解决方案
3、：附设访问标志数组visited0.n-1，它的初始状它的初始状态为态为0，在图的遍历过程中，一旦某一个顶点，在图的遍历过程中，一旦某一个顶点i 被访问，就被访问，就立即改立即改 visited i为为1，防止它被多次访问。，防止它被多次访问。第5页，本讲稿共32页1.深度优先搜索深度优先搜索(DFS，Depth_First Search)基本思想：基本思想：（1）从图中某顶点）从图中某顶点V0出发，出发，访问访问此顶点，此顶点，然后依次然后依次从从V0的各个未被访问的邻接点的各个未被访问的邻接点出发出发深度优先搜深度优先搜索索遍历图，直至图中所有和遍历图，直至图中所有和V0有路径相通的顶点都
4、被访问有路径相通的顶点都被访问到；到；（2）若此时图中尚有顶点未被访问，则）若此时图中尚有顶点未被访问，则另选图中另选图中一个未曾被访问的顶点作起始点一个未曾被访问的顶点作起始点；（3）重复上述两步，直至图中所有顶点都被访问到为止。）重复上述两步，直至图中所有顶点都被访问到为止。与树的先序遍历过程类似与树的先序遍历过程类似第6页，本讲稿共32页详细过程：详细过程：1)1.1 在在访问访问图中某一起始顶点图中某一起始顶点 v 后，由后，由 v 出发，出发，访问访问它的它的任一任一邻接顶点邻接顶点 w1；1.2 再从再从 w1 出发出发，访问，访问与与 w1邻接但还未被访问过邻接但还未被访问过的顶
5、点的顶点 w2；1.3 然后再从然后再从 w2 出发，进行类似的访问出发，进行类似的访问 直至到达所有直至到达所有的邻接顶点都被访问过的顶点的邻接顶点都被访问过的顶点 u 为止为止。2)退回一步，退回一步，退到前一次刚访问过的顶点退到前一次刚访问过的顶点，看是否还有其它，看是否还有其它未被访问的邻接顶点未被访问的邻接顶点:2.1 如果有，则访问此顶点，之后再从此顶点出发，返回如果有，则访问此顶点，之后再从此顶点出发，返回第第1)步的操作；步的操作；2.2 如果没有，就再退回一步进行搜索。如果没有，就再退回一步进行搜索。2.3 重复上述过程，重复上述过程，直到连通图中所有顶点都被访问直到连通图中
6、所有顶点都被访问过为过为止。止。第7页，本讲稿共32页 例：例：从从顶顶点点v1出出发发，DFS下下图图。访问序列：访问序列：v1,v2,v4,v8,v5,v3,v6,v7v1v6v2v5v3v8v4v7v1v6v2v5v3v8v4v7第8页，本讲稿共32页图的图的DFS算法一般描述算法一般描述int visitedMAXVEX;/访问标志数组访问标志数组void DFSTraverse(Graph G)/对图对图G作深度优先遍历作深度优先遍历 for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化访问标志数组初始化0 for(v=0;v=0;w=Next
7、AdjVex(G,v,w)if(!visitedw)DFS(G,w);第10页，本讲稿共32页用邻接表实现图的深度优先搜索用邻接表实现图的深度优先搜索v1v6v2v5v3v8v4v7v9v1012345678 1 7 1 7 2 6 2 5 3 4 2 3 1 2 0 5 6 0 3 4910 8/9 /0123456789第11页，本讲稿共32页在图的邻接表中如何进行在图的邻接表中如何进行DFS？DFS 结果结果00000123辅助数组辅助数组 visited n1000110011101111例：例：照样借用照样借用visited n 起点起点0123注意：在邻接表中，并非每个链注意：在邻
8、接表中，并非每个链表元素（表结点）都被扫描到表元素（表结点）都被扫描到,因此遍历速度很快。因此遍历速度很快。v0v v1v2v3第12页，本讲稿共32页void DFS(ALGraph G,int v)ArcNode*p;visitedv=1;/*置已置已访问标记访问标记*/printf(%d ,v);/*输输出被出被访问顶访问顶点的点的编编号号*/p=G.verticesv.firstarc;/*p指向指向顶顶点点v的第一的第一个邻接点个邻接点*/while(p!=NULL)if(visitedp-adjvex=0)DFS(G,p-adjvex);/*若若p-adjvex顶顶点未点未访问访问
9、,递归访问递归访问它它*/p=p-nextarc;/*p指向指向顶顶点点v的下一的下一个邻接点个邻接点*/邻接表的邻接表的DFS算法算法第13页，本讲稿共32页 for(j=0;jG.vexnum;j+)if(G.arcsv j&!visitedj)DFS1(G,j);/DFS1DFS1(MGraph G,int v)visit(v);visitedv=1;/G.arcsnn为邻为邻接矩接矩阵阵，v为为起始起始顶顶点点(编编号）号）/访问访问（例如打印）（例如打印）顶顶点点v G.arcsvj 1 有有邻邻接点接点visited n=0未未访问过访问过/访问访问后立即修改后立即修改辅辅助数助数
10、组标组标志志/从从v所在行从所在行从头头搜索搜索邻邻接点接点邻邻接矩接矩阵阵的的DFS算法算法第14页，本讲稿共32页分析：分析：在遍在遍历图时历图时，对图对图中每个中每个顶顶点至多点至多调调用一次用一次DFS函数，函数，因因为为一旦某个一旦某个顶顶点被点被标标志成已被志成已被访问访问，就不再从它出，就不再从它出发进发进行搜索。行搜索。因此，遍因此，遍历图历图的的过过程程实质实质上是上是对对每个每个顶顶点点查查找其找其邻邻接接点的点的过过程程。其耗。其耗费费的的时间则时间则取决于所采用的存取决于所采用的存储结储结构构。l 如果用如果用邻邻接矩接矩阵阵来表示来表示图图，遍，遍历图历图中每一个中每
11、一个顶顶点都要点都要从从头扫头扫描描该顶该顶点所在行，因此遍点所在行，因此遍历历全部全部顶顶点所需的点所需的时间为时间为O(n2)。l 如果用如果用邻邻接表接表来表示来表示图图，虽虽然有然有 2e 个表个表结结点，但只需点，但只需扫扫描描 e 个个结结点即可完成遍点即可完成遍历历，加上，加上访问访问 n个个头结头结点的点的时间时间，因此遍因此遍历图历图的的时间时间复复杂杂度度为为O(n+e)。第15页，本讲稿共32页2.广度优先搜索广度优先搜索(BFS,Breadth_First Search)基本思想：基本思想：从图中某个顶点从图中某个顶点V0出发，并在访问此顶点后出发，并在访问此顶点后依次
12、依次访访问问V0的的所有未被访问过的邻接点所有未被访问过的邻接点，之后，之后按这些顶点被访问按这些顶点被访问的先后次序依次的先后次序依次访问它们的邻接点，直至图中所有和访问它们的邻接点，直至图中所有和V0有有路径相通的顶点都被访问到；路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点；被访问的顶点作起始点；重复上述过程，直至图中所有顶点都被访问到为止。重复上述过程，直至图中所有顶点都被访问到为止。与树的层次遍历过程类似与树的层次遍历过程类似第16页，本讲稿共32页 例：例：从顶点从顶点v1出发，出发，BFS
13、下图。下图。访问序列：访问序列：v1,v2,v3,v4,v5,v6,v7,v8v1v6v2v5v3v8v4v7第17页，本讲稿共32页用邻接表实现图的广度优先搜索用邻接表实现图的广度优先搜索v1v6v2v5v3v8v4v7v1v2v3v4v5v6v7v8 1 7 1 7 2 6 2 5 3 4 2 3 1 2 0 5 6 0 3 401234567第18页，本讲稿共32页BFS非非递归递归算法算法void BFSTraverse(Graph G,Status(*Visit)(int v)/使用辅助使用辅助队列队列Q和访问标志数组和访问标志数组visitedv for(v=0;vG.vexnum
14、;+v)visitedv=FALSE;InitQueue(Q);/置空的辅助队列置空的辅助队列Q for(v=0;v=0;w=NextAdjVex(G,u,w)if(!visitedw)/w为为u的尚未访问的邻接顶点的尚未访问的邻接顶点 visitedw=TRUE;Visit(w);EnQueue(Q,w);/if /while /if /BFSTraverse第20页，本讲稿共32页分析：分析：每个顶点至多进一次队列。遍历图的过程每个顶点至多进一次队列。遍历图的过程实质上实质上是通过边或弧找邻接点的过程是通过边或弧找邻接点的过程，因此广度优先搜索遍，因此广度优先搜索遍历图的历图的时间复杂度和
15、深度优先搜索遍历相同时间复杂度和深度优先搜索遍历相同，两者，两者不同不同之处仅仅在于对顶点访问的顺序不同之处仅仅在于对顶点访问的顺序不同。邻接矩阵：邻接矩阵：O(n2)邻接表：邻接表：O(n+e)第21页，本讲稿共32页第7章 图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径第22页，本讲稿共32页7.4 图的连通性问题图的连通性问题1）无向图的无向图的连通分量和连通分量和生成树生成树2）最小生成树最小生成树 普里姆算法普里姆算法 克鲁斯卡尔算法克鲁斯卡尔算法第23页，本讲稿共32页要想要想判定一个无向图是否为连通图判
16、定一个无向图是否为连通图，或有几个连通分量，或有几个连通分量，通过通过对无向图遍历即可得到结果。对无向图遍历即可得到结果。连连通通图图：仅仅需需从从图图中中任任一一顶顶点点出出发发，进进行行深深度度优优先先搜搜索索（或广度优先搜索），便可访问到图中所有顶点。（或广度优先搜索），便可访问到图中所有顶点。无向图的连通性无向图的连通性1.无向图的无向图的连通分量和连通分量和生成树生成树非非连连通通图图：需需从从多多个个顶顶点点出出发发进进行行搜搜索索，而而每每一一次次从从一一个个新新的的起起始始点点出出发发进进行行搜搜索索过过程程中中得得到到的的顶顶点点访访问问序序列列恰恰为其各个连通分量中的顶点集
17、。为其各个连通分量中的顶点集。第24页，本讲稿共32页基本概念基本概念n生成树生成树：某连通分量的某连通分量的极小连通子图极小连通子图，它含有图中它含有图中全部顶点，但只有全部顶点，但只有n-1条边条边；n生成森林生成森林：非连通图的各个连通分量的极小连通子：非连通图的各个连通分量的极小连通子图图（即生成树）（即生成树）构成的集合构成的集合，含全部顶点，但构成含全部顶点，但构成这些树的边是最少的这些树的边是最少的。第25页，本讲稿共32页思考思考1：若对连通图进行遍历，得到的是什么？：若对连通图进行遍历，得到的是什么？遍历过程中历经的边的集合遍历过程中历经的边的集合和图和图G中中所有顶点所有顶
18、点一起一起构成连构成连通图通图G的极小连通子图的极小连通子图，即图的，即图的生成树生成树。由深度优先搜索得到的生成树，称为由深度优先搜索得到的生成树，称为深度优先搜索生成树深度优先搜索生成树。由广度优先搜索得到的生成树，称为由广度优先搜索得到的生成树，称为广度优先搜索生成广度优先搜索生成树树。思考思考2：若对非连通图进行遍历，得到的是什么？：若对非连通图进行遍历，得到的是什么？得到的将是各连通分量的生成树，即图的得到的将是各连通分量的生成树，即图的生成森林生成森林。第26页，本讲稿共32页（a）深度优先生成树）深度优先生成树 （b）广度优先生成树广度优先生成树生成树生成树生成树生成树V1V3V
19、2V4V5V6V7V8V1V3V2V4V5V6V7V8第27页，本讲稿共32页例：求下图的深度优先生成树和广度优先生成树。例：求下图的深度优先生成树和广度优先生成树。v1v6v2v5v3v8v4v7第28页，本讲稿共32页 对非连通图，对非连通图，每个连通分量每个连通分量中的顶点集和遍历时走过的中的顶点集和遍历时走过的边一起构成若干棵边一起构成若干棵生成树生成树，这些连通分量的生成树组成非，这些连通分量的生成树组成非连通图的连通图的生成森林生成森林。例：例：一个连通图的一个连通图的生成树可能不唯一生成树可能不唯一，由，由不同的遍历次序不同的遍历次序、从不同顶点出发从不同顶点出发进行遍历都会得到
20、不同的生成树。进行遍历都会得到不同的生成树。第29页，本讲稿共32页DEGHIKABCFJLMABCFJLMDEGHIK深度优先深度优先生成森林生成森林广广度优先度优先生成森林生成森林第30页，本讲稿共32页1.1.理解并掌握图的深度优先搜索和广度优先搜索理解并掌握图的深度优先搜索和广度优先搜索两种遍历两种遍历算法及其性能分析算法及其性能分析；以及两种遍历所使用的辅助数据结构；以及两种遍历所使用的辅助数据结构（栈或队列）在遍历过程中所起的作用，能够（栈或队列）在遍历过程中所起的作用，能够确定确定两种遍两种遍历所得到的历所得到的顶点访问序列顶点访问序列以及利用图的两种以及利用图的两种遍历遍历设计算法设计算法解决解决简单的应用简单的应用问题。问题。2.2.理解并掌握生成树的概念，能理解并掌握生成树的概念，能画出画出给定的图深度优先和给定的图深度优先和广度优先广度优先生成树或生成森林生成树或生成森林；小结小结第31页，本讲稿共32页作业作业l基于邻接矩阵的基于邻接矩阵的DFS算法实现算法实现l基于邻接矩阵的基于邻接矩阵的BFS算法实现算法实现第32页，本讲稿共32页