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

数据结构与算法 ---第二十讲;20、图的遍历深度优先遍历和广度优先遍历 ;目 录;20、 图的遍历;20.1 概述; 访问标志的设置有两种方法： ①在描述图结的记录中增设一个访问标志位。这种方法的优点是，访问“访问标志”的方法与访问结点的方法一致。如果访问标志需要与图结构同生命期，则这种方法比较合适。但是，若访问标志要重复使用，就必须先重新初始化访问标志。如果图结点的存储不利于顺序访问，这往往也是个遍历问题！ ②另设一个“访问数组”，令它的每个元素对应于一个图结点访问标志。这种方法的访问标志很容易多次初始化。;从图中某一结点出发，一趟只能遍历到它所在的极大连通分量中的结点，要想遍历到图中各结点，需进行多趟遍历（每趟遍历一个极大连通分量）。该过程可描述为： 　　　 for (图中每个结点v) if (v尚未被访问过) 从v出发遍历该图; ;20.2 深度优先遍历; 例如，对图 20?1给出的有向图与无向图，一些遍历结果（结点访问次序）为： 左图：从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; … … ; 1. 一般算法 下面考虑深度优先遍历的递归实现的一般方法（存储结构无关）。 图的深度优先遍历与二叉树的前序遍历相似。不同之处有：①二叉树每个结点至多有两个可达邻接点（左右儿子），而图的可达邻接点数目不定； ②对二叉树，沿可达邻接点有哪些信誉好的足球投注网站时不会发生回绕，但对图，若不加特别控制，就有可能回绕。 下面是图的深度优先遍历递归算法的一般性描述。如果要另设一个数组作为访问标志，则该数组要在递归过程（函数）之外初始化为“未访问”。 ;long DFS(图g，结点v0) { //图深度优先遍历递归算法。从结点v0出发，深度优先遍历图g，返回访问到的结点总数 int nNodes; //寄存访问到的结点数目? 访问v0; 为v0置已访问标志; nNodes=1; 求出v0的第1个可达邻接点v; while (v存在) { if (v未被访问过) nNodes=nNodes+DFS(g,v); 求出v0的下个可达邻接点v; } return nNodes; }?;1; 2．邻接矩阵实现 这里我们为了突出主题、简化问题，假定图是用一般的邻接矩阵存储，邻接矩阵用简单的二维数组表示（静态），用0和1分别表示无边和有边。图结点用自然数编号。 long DFS1(int g[][CNST_NumNodes], long n, long v0, char *visited,long *resu，long top ) {//深度优先遍历图（递归）。图g为邻接矩阵，结点编号为 0~n. 返回实际遍历到的结点数目 //visited是访问标志数组，调用本函数前，应为其分配空间并初始化为全0(未访问) //resu为一维数组，用于存放所遍历到的结点的编号，调用本函数前，应为其分配空间; long nNodes, i;? nNodes=1; resu[top++]=v0; //将访问到的结点依次存于resu[] visited[v0]=1; //为v0置已访问标志 for (i=0; in; i++) {//依次从v0的各个出点出发，深度优先遍历图 if (g[v0][i]!=0) //若v0, i是边 if (!visited[i]) //若结点i未被访