图的遍历(深度优先遍历和广度优先遍历).ppt

数据结构与算法-第二十讲,北方民族大学计算机科学与工程学院王伦津研究员,图的遍历,20、图的遍历深度优先遍历和广度优先遍历,掌握图的深度优先和广度优先遍历的性质和方法，以及基于邻接矩阵和邻接表存储结构的递归和非递归的算法实现,目录,20.1概述20.2深度优先遍历20.3深度优先遍历的性质20.4广度优先遍历20.5广度优先遍历的性质,20、图的遍历,从这节起，我们介绍图的一些重要操作的实现，包括遍历、拓扑排序、关键路径等。另有一些重要操作，如最短路径问题、最小生成树问题，由于主要难点在于算法，所以我们安排在后面的算法设计章节中介绍。图的遍历与树的遍历一样具有十分重要的作用，图的许多其他操作（算法）都与遍历相关。,20.1概述,图的遍历的含意是，从图中某结点出发，按某既定方式访问图中各个可访问到的结点，使每个可访问到的结点恰被访问一次。图的遍历方式有两种：深度优先与广度优先方式，分别对应于树的先根遍历与层序遍历。树中不存在回路，但图中可能有回路。因此，当沿回路进行扫描时，一个结点可能被扫描到多次，可能导致死循环。为了避免这种情形，在遍历中，应为每个结点设立一个访问标志，每扫描到一个结点，要检查它的访问标志，若标志为“未访问”，则按正常方式对其进行处理（如访问或转到它的邻接点等），否则放过它，扫描下一个结点。,访问标志的设置有两种方法：在描述图结的记录中增设一个访问标志位。这种方法的优点是，访问“访问标志”的方法与访问结点的方法一致。如果访问标志需要与图结构同生命期，则这种方法比较合适。但是，若访问标志要重复使用，就必须先重新初始化访问标志。如果图结点的存储不利于顺序访问，这往往也是个遍历问题！另设一个“访问数组”，令它的每个元素对应于一个图结点访问标志。这种方法的访问标志很容易多次初始化。,从图中某一结点出发，一趟只能遍历到它所在的极大连通分量中的结点，要想遍历到图中各结点，需进行多趟遍历（每趟遍历一个极大连通分量）。该过程可描述为：for(图中每个结点v)if(v尚未被访问过)从v出发遍历该图;,下面只考虑从一点出发遍历，因此有可能会出现遍历不到的点。即那些初始点无路径可达的点，是遍历不到的。,20.2深度优先遍历,(一)遍历规则从图中某结点v0出发，深度优先遍历（DFS:DepthFirstSearch）图的规则为：访问v0；对v0的各个出点v01，v02，v0m，每次从它们中按一定方式（也可任选）选取一个未被访问过的结点，从该结点出发按深度优先遍历方式遍历。显然，因为我们没有规定对出点的遍历次序，所以，图的深度优先遍历结果一般不唯一。,例如，对图201给出的有向图与无向图，一些遍历结果（结点访问次序）为：左图：从1出发：1，2，4，5；或1，5，2，4从2出发：2，1，5，4；或2，4，1，5右图：从a出发：a，b，c，d；或a，b，d，c;,图201一个有向图（左）和无向图,1.一般算法下面考虑深度优先遍历的递归实现的一般方法（存储结构无关）。图的深度优先遍历与二叉树的前序遍历相似。不同之处有：二叉树每个结点至多有两个可达邻接点（左右儿子），而图的可达邻接点数目不定；对二叉树，沿可达邻接点搜索时不会发生回绕，但对图，若不加特别控制，就有可能回绕。下面是图的深度优先遍历递归算法的一般性描述。如果要另设一个数组作为访问标志，则该数组要在递归过程（函数）之外初始化为“未访问”。,（二）递归实现方法,longDFS(图g，结点v0)/图深度优先遍历递归算法。从结点v0出发，深度优先遍历图g，返回访问到的结点总数intnNodes;/寄存访问到的结点数目访问v0;为v0置已访问标志;nNodes=1;求出v0的第1个可达邻接点v;while(v存在)if(v未被访问过)nNodes=nNodes+DFS(g,v);求出v0的下个可达邻接点v;returnnNodes;,12345101001210010300001410000500000,所示图的邻接矩阵g,1121304151,图201有向图,访问标识数组visited,输出数组resu,例如从1点深度优先遍历，先把1设置访问标志，并置入输出数组resu，然后从邻接矩阵的第一行，扫描各列，找到最近的邻接点2，将其设置访问标志，并进入输出数组，接着从邻接矩阵的2行扫描，找到第一个构成边的点是1，检查访问标识数组，发现1已经访问过，跳过，找第二个构成边的点4，设置访问标识，进入输出数组，再从邻接矩阵的第4行扫描，寻找构成边的点，除1外在无其他点，返回2行，继续寻找，也无新点，返回1，找到5，将5置访问标志，进入输出数组，1行再无其他新点，遍历结束，返回遍历元素个数为4。,2邻接矩阵实现这里我们为了突出主题、简化问题，假定图是用一般的邻接矩阵存储，邻接矩阵用简单的二维数组表示（静态），用0和1分别表示无边和有边。图结点用自然数编号。longDFS1(intgCNST_NumNodes,longn,longv0,char*visited,long*resu，longnNodes=1;resutop+=v0;/将访问到的结点依次存于resuvisitedv0=1;/为v0置已访问标志for(i=0;i是边if(!visitedi)/若结点i未被访问过nNodes=nNodes+DFS1(g,n,i,visited,resu);/从i起深度优先遍历图returnnNodes;,A如果不想让visited或top做为函数参数，也可以在函数中将其定义为static型量。但是，这样的程序是不可再入的，即函数再次被调用时，static型的量也不重新初始化，造成错误！,上面函数中的参数visited和top实质上是中间变量，只是为了避免在递归调用时重新初始化而放在参数表中，造成使用的不方便，为此，做个包装程序：longDFS1(intgCNST_NumNodes,longn,longv0,long*resu)char*visited;longtop=0;visited=newcharn;for(longi=0;iendNo)/若p未访问，则从p出发深度优先遍历nNodes=nNodes+DFS2(nodes,n,p-endNo,visited,resu,top);p=p-next;/令p指向v0的下个出点returnnNodes;与邻接矩阵的情况类似，也可以对该程序“包装”，以隐蔽visited和top。,(三)非递归实现方法1一般方法下面考虑深度优先遍历的非递归实现的一般方法（存储结构无关）。图的深度优先遍历的非递归实现，仍然与二叉树的前序遍历非递归实现相似。不同之处有：二叉树每个结点至多有两个可达邻接点（左右儿子），而图的可达邻接点数目不定，因此，当结点重新出现在栈顶时，不能一定出栈，而是要根据它的各出点是否都已被访问过来决定（是则出栈）；对二叉树，沿可达邻接点搜索时不会发生回绕，但对图，若不加特别控制，就有可能回绕。,longDFS_NR(图g，结点v0)/图深度优先遍历非递归算法。从结点v0出发，深度优先遍历图g，返回访问到的结点总数intnNodes;/寄存访问到的结点数目访问v0;为v0置已访问标志;v0进栈S；nNodes=1;求出v0的第1个可达邻接点v;,深度优先遍历非递归算法的一般性描述。,while(栈S不空)v=栈S顶部元素；求v的下个未访问过的出点i；访问i;为i置已访问标志;i进栈S；nNodes+;if(v已无未被访问过的出点)出栈；returnnNodes;上面的伪码描述与具体的数据结构无关。下面的程序分别给出了针对邻接矩阵与邻接表的算法模型。,2邻接矩阵实现longDFS1_NR(intgCNST_NumNodes,longn,longv0,long*resu)/深度优先遍历图(非递归）。图g为邻接矩阵，结点编号为0n.返回实际遍历到的结点数目/resu为一维数组，用于存放所遍历到的结点的编号，调用本函数前，应为其分配空间longnNodes,i,v;longtop;char*visited;long*s;visited=newcharn;for(i=0;iendNo);visitedp-endNo=1;p=p-next/while/whiledeletevisited;returnnNodes;,对应的邻接表,图202有向图,1121304151,访问标识数组visited,输出数组nos,邻接表边,P,Nodes,20.5广度优先遍历的性质,与深度优先遍历类似，广度优先遍历也有许多有用的特性。(一)广度优先生成树在广度优先遍历中，如果将每次“前进”（纵深）路过的（将被访问的）结点和边都记录下来，就得到一个子图，该子图为以出发点为根的树，称为广度优先生成树。这种情况与深度优先遍历类似。类似地，也可以给广度优先生成树结点定义时间戳。(二)最短路径显然，从v0出发广度优先遍历图，将得到v0到它的各个可达点的路径。我们这里定义路径上的边的数目为路径长度。与深度优先遍历不同，广度优先遍历得到的v0到各点的路径是最短路径（未考虑边权）。,本章小结,图的基本特征是图中元素的前驱与后继的个数都没有限制。图是最复杂的非线性结构，它的表达能力也最强，前面介绍的线性结构、树等均是它的特例。图的存储方式一般有两类：用边的集合表示图和用链接关系表示图。其中，边的集合方式有邻接矩阵，链接方式有邻接表、十字链表和邻接多重表等。图结构的接口主要有：求某结点的各入点/出点，求某结点的各入边/出边、遍历（深度优先和广度优先）。,思考与练习,1、给出下列有向图和无向图的深度优先和广度优先遍历结果。,2、叙述增加新顶点和删除某顶点的过程。,