深度优先遍历，就是深度优先遍历
没有说是怎样的

1、图的遍历
    　和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。
    　深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。
  注意：
　    以下假定遍历过程中访问顶点的操作是简单地输出顶点。

2、布尔向量visited[0．．n-1]的设置
    　图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一布尔向量visited[0．．n-1]，其初值为假，一旦访问了顶点Vi之后，便将visited[i]置为真。

深度优先遍历(Depth-First Traversal)

1．图的深度优先遍历的递归定义
    　假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
    　图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。

2、深度优先搜索的过程
    　设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。

图的遍历




　　与树的遍历类似，我们希望从图中的某一点出发，遍访图中的每一个顶点，且使图 中的每一个顶点仅被访问一次 。这种操作称为图 的遍历。遍历算法是许多操作的基础。

　　图的遍历算法要比树的遍历算法要复杂些，特别是在一些存在回路的图中，很有可能沿某一条路径搜索后又回到原先的出发点。为了避免同一个顶点被访问多次，可以采用多种方法，比如，记下已访问过的顶点，或干脆给访问过的顶点做上标记。

遍历方式有按深度优先和按广度优先两种。

1． 按深度优先遍历算法（以无向连通图为例）：

　　① 设立搜索指针P ，使之指向起始顶点。
　　② 访问 P ，给P 结点作上已被访问的标记，并使P 指向与之邻接但未被访问的结点。
　　③ 若 P 不空，则重复②。
　　④ 退回到刚才出发的结点位置 ， 另外搜索一个未被访问过的结点，重复②。直到所有结点都被访问为止。例如下图所示的遍历过程。


　　Proc trave ( var g:lkgraph; v:integer);
　　　[ g[v].vertex:=1;
　　　　write (v:4); p:=g[v].link;
　　　　while (p<> nil) do
　　　　　[ if g[p^.vex].vertex=0 then
　　　　　　　trave ( g, p^.vex);
　　　　　　　p:=p^.next;
　　　　　]
　　　]

　　至于以邻接矩阵为存储结构的图遍历，也可以用类似的算法。不过需要另设立一个标记数组，用以记录顶点是否被访问过。进入算法前，须将该数组初始化：

　　for I:=1 to g.dem do a[I]:=false;
　　　　Proc trave1 ( g:sqgraph ; v integer);
　　　　[ a[v]:=true; write (v:4);
　　　　　　I:=1;
　　　　　　While I<=g.dem do
　　　　　　　[If (g.graph[v,I]=1) and not a[I] then
　　　　　　　　　　　　　trave1 (g ,I);
　　　　　　　I:=I+1]
　　　　]

对于一般的无向图，可以用该算法求出图中的所有的连通分量：

　　proc takecompanient ( var g:lkgraph;var n:integer);
　　　proc search ( g:lkgraph; var ver:integer);
　　　　……………………….（* search 过程略去*）
　　　　[ repeat
　　　　　search ( g,I );
　　　　　　if I =0 then writeln (' complated')
　　　　　　else [ trave ( g,I); writeln; writeln ];
　　　　　　　until I=0;

2． 按广度优先遍历。这种遍历类似树中的按层次遍历。其主要点是以V0 为起点 ，由近及远依次访问和V0 有路径相通且路径长度为1，2…..n 的顶点。具体的算法是：

　　标记初始化；队列初始化；

　　将起始顶点V0 入队；

　　while 队不空 do

　　[ 取队头元素；出队；

　　访问该顶点；将与该顶点路径长度为1 且未被访问的顶点入队；
　　]

　　proc trave2 ( var g:lkgraph; v:integer);
　　　　var queue: array [1..maxsize] of 0..1;
　　[ initiate ( queue ); front:=0;rear:=1;
　　　　queue[1]:=v;
　　　while front<>rear do
　　　　[ vd:=queue[front+1];front:=front+1;
　　　　　　write ( vd:4); g[vd].vertex:=1;
　　　　　　　p:=g[vd].link;
　　　　　　while p<>nil do
　　　　　　　[ if g[p^.vex].vertex=0 then
　　　　　　　　[ queue[rear+1]:=p^.vex; rear:=rear+1 ];
　　　　　　　p:=p^.next
　　　　　　　]
　　　　 ]
　　]

?

？