深度优先搜索

基本思想：从初始状态S开始，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态G，若未出现，以此状态利用规则生成再下一层任一个结点，再检查是否为目标节点G，若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点），当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜索的分支。生成新状态节点。若仍不是目标状态，就按该分支一直扩展到叶节点，若仍不是目标，采用相同的回溯办法回退到上层节点，扩展可能的分支生成新状态，…，一直进行下去，直到找到目标状态G为止。

深度优先遍历算法
  typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1
  Boolean visited[MaxVertexNum]； //访问标志向量是全局量
  void DFSTraverse(ALGraph *G)
  { //深度优先遍历以邻接表表示的图G，而以邻接矩阵表示G时，算法完全与此相同
    int i；
    for(i=0;i<G->n;i++)
      visited[i]=FALSE； //标志向量初始化
    for(i=0;i<G->n；i++)
      if(!visited[i]) //vi未访问过
        DFS(G，i)； //以vi为源点开始DFS搜索
   }//DFSTraverse

深度优先注意点，1、标志位的设置

                2、成功条件的终止

                3、恢复现场

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

2、栈在深度优先遍历算法中的作用
    深度优先遍历过程中，后访问的顶点其邻接点被先访问，故在递归调用过程中使用栈（系统运行时刻栈）来保存已访问的顶点。

算法分析
    对于具有n个顶点和e条边的无向图或有向图，遍历算法DFSTraverse对图中每顶点至多调用一次DFS或DFSM。从DFSTraverse中调用DFS(或DFSM)及DFS(或DFSM)内部递归调用自己的总次数为n。
    当访问某顶点vi时，DFS(或DFSM)的时间主要耗费在从该顶点出发搜索它的所有邻接点上。用邻接矩阵（数组）表示图时，其搜索时间为O(n)；用邻接表表示图时，需搜索第i个边表上的所有结点。因此，对所有n个顶点访问，在邻接矩阵上共需检查n²个矩阵元素，在邻接表上需将边表中所有O(e)个结点检查一遍。
    所以，DFSTraverse的时间复杂度为O(n²) （调用DFSM）或0(n+e)（调用DFS）。