Question

遍历的图

Answer 1

（Depth-First Traversal)
图的深度优先遍历的递归定义：
假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点（源点），则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点（亦称为从源点可达的顶点）均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search）。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。
深度优先搜索的过程
设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边（x，y）。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边（x，y）到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点（即从源点可达的所有顶点）都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。
算法实现 plate<intmax_size>voidDigraph<max_size>::depth_first(void(*visit)(Vertex&))const/*Post:Thefunction*visithasbeenperformedateachvertexoftheDigraphindepth-firstorder.Uses:Methodtraversetoproducetherecursivedepth-firstorder.*/{boolvisited[max_size];Vertexv;for(allvinG)visited[v]=false;for(allvinG)if(!visited[v])traverse(v,visited,visit);}template<intmax_size>voidDigraph<max_size>::traverse(Vertex&v,boolvisited[],void(*visit)(Vertex&))const/*Pre:visavertexoftheDigraph.Post:Thedepth-firsttraversal,usingfunction*visit,hasbeencompletedforvandforallverticesthatcanbereachedfromv.Uses:traverserecursively.*/{Vertexw;visited[v]=true;（*visit)(v);for(allwadjacenttov)if(!visited[w])traverse(w,visited,visit);} （Width-First Traversal）
基本思想
1、从图中某个顶点V0出发，并访问此顶点；
2、从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…，Wk；然后，依次从W1,W2，…，Wk出发访问各自未被访问的邻接点；
3、重复步骤2，直到全部顶点都被访问为止。
广度优先遍历的性质
与深度优先遍历类似，广度优先遍历也有许多有用的特性：
1、广度优先生成树
在广度优先遍历中，如果将每次“前进”（纵深）路过的（将被访问的）结点和边都记录下来，就得到一个子图，该子图为以出发点为根的树，称为广度优先生成树。这种情况与深度优先遍历类似。
类似地，也可以给广度优先生成树结点定义时间戳。
2、最短路径
显然，从v0出发广度优先遍历图，将得到v0到它的各个可达到的路径。我们这里定义路径上的边的数目为路径长度。与深度优先遍历不同，广度优先遍历得到的v0到各点的路径是最短路径（未考虑边权）。
算法实现　 template<intmax_size>voidDigraph<max_size>::breadth_first(void(*visit)(Vertex&))const/*Post:Thefunction*visithasbeenperformedateachvertexoftheDigraphinbreadth-firstorder.Uses:MethodsofclassQueue.*/{Queueq;boolvisited[max_size];Vertexv,w,x;for(allvinG)visited[v]=false;for(allvinG)if(!visited[v]){q.append(v);while(!q.empty()){q.retrieve(w);if(!visited[w]){visited[w]=true;(*visit)(w);for(allxadjacenttow)q.append(x);}q.serve();}}}与深度优先遍历的比较
广度优先遍历与深度优先遍历的区别在于：广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索；而深度优先遍历是将某一条枝桠上的所有节点都搜索到了之后，才转向搜索另一条枝桠上的所有节点。
深度优先遍历从某个顶点出发，首先访问这个顶点，然后找出刚访问这个结点的第一个未被访问的邻结点，然后再以此邻结点为顶点，继续找它的下一个新的顶点进行访问，重复此步骤，直到所有结点都被访问完为止。
广度优先遍历从某个顶点出发，首先访问这个顶点，然后找出这个结点的所有未被访问的邻接点，访问完后再访问这些结点中第一个邻接点的所有结点，重复此方法，直到所有结点都被访问完为止。
可以看到两种方法最大的区别在于前者从顶点的第一个邻接点一直访问下去再访问顶点的第二个邻接点；后者从顶点开始访问该顶点的所有邻接点再依次向下，一层一层的访问。