深度优先搜索

图的深度优先搜索（Depth First Search），和树的先序遍历比较类似。假设初始状态是图中所有顶点均未被访问，则从某个顶点 v 出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和 v 有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

显然，深度优先搜索是一个递归的过程。

int book[100], sum, n, e[100][100];
void dfs(int cur){ // cur 当前所在顶点编号
      sum++;
      if(sum == n) return; // 所有顶点都已经访问过就直接退出
      for(int i=0; i<n; i++){
          if(e[cur][i] == 1 && book[i] == 0){
              book[i] = 1; // 标记顶点i已经访问过
              dfs(i); // 从顶点i再出发继续遍历
          }
      }
      return;
}

无向图的深度优先搜索

• 第 1 步：访问 A。
• 第 2 步：访问(A 的邻接点)C。在第 1 步访问 A 之后，接下来应该访问的是 A 的邻接点，即"C,D,F"中的一个。但在本文的实现中，顶点 ABCDEFG 是按照顺序存储，C 在"D 和 F"的前面，因此，先访问 C。
• 第 3 步：访问(C 的邻接点)B。在第 2 步访问 C 之后，接下来应该访问 C 的邻接点，即"B 和 D"中一个(A 已经被访问过，就不算在内)。而由于 B 在 D 之前，先访问 B。
• 第 4 步：访问(C 的邻接点)D。在第 3 步访问了 C 的邻接点 B 之后，B 没有未被访问的邻接点；因此，返回到访问 C 的另一个邻接点 D。
• 第 5 步：访问(A 的邻接点)F。前面已经访问了 A，并且访问完了"A 的邻接点 B 的所有邻接点(包括递归的邻接点在内)"；因此，此时返回到访问 A 的另一个邻接点 F。
• 第 6 步：访问(F 的邻接点)G。
• 第 7 步：访问(G 的邻接点)E。

因此访问顺序是：A -> C -> B -> D -> F -> G -> E

有向图的深度优先搜索

• 第 1 步：访问 A。
• 第 2 步：访问 B。在访问了 A 之后，接下来应该访问的是 A 的出边的另一个顶点，即顶点 B。
• 第 3 步：访问 C。在访问了 B 之后，接下来应该访问的是 B 的出边的另一个顶点，即顶点 C,E,F。在本文实现的图中，顶点 ABCDEFG 按照顺序存储，因此先访问 C。
• 第 4 步：访问 E。接下来访问 C 的出边的另一个顶点，即顶点 E。
• 第 5 步：访问 D。接下来访问 E 的出边的另一个顶点，即顶点 B,D。顶点 B 已经被访问过，因此访问顶点 D。
• 第 6 步：访问 F。接下应该回溯"访问 A 的出边的另一个顶点 F"。
• 第 7 步：访问 G。

因此访问顺序是：A -> B -> C -> E -> D -> F -> G

深度优先遍历

图的深度优先遍历基于深度优先搜索 DFS(Depth First Search)，其类似于树的前序遍历。深度优先搜索是从图中某一顶点 v 出发，在访问顶点 v 后，再依次从 v 的任一还没有被访问的邻接顶点 w 出发进行深度优先搜索，直到图中所有与顶点 v 有路径相通的顶点都被访问过为止。这是一个递归定义，所以图的深度优先搜索可以用递归算法实现。

下图（a）给出了深度优先搜索的示例。由于该图是连通的，所以从顶点 A 出发，通过一次深度优先搜索，就可以访问图中的所有顶点。图的深度优先搜索的访问顺序与树的前序遍历顺序类似。图 (b)给出了在深度优先搜索的过程中，访问的所有顶点和经过的边，图中各顶点旁附加的数字表示各顶点被访问的次序。在图 (b)中，共有 n-1 条边连结了所有 n 个顶点，在此把它称为图（a）的深度优先搜索生成树。

从指定的结点 v 开始进行深度优先搜索的算法的步骤是：

（1）访问结点 v，并标记 v 已被访问 （2）取顶点 v 的第一个邻接顶点 w （3）若顶点 w 不存在，返回；否则继续步骤（4） （4）若顶点 w 未被访问，则访问结点 w，并标记 w 已被访问；否则转步骤（5） （5）使 w 为顶点 v 的在原来 w 之后的下一个邻接顶点，转到步骤（3）

深度优先遍历的主要思想是：首先以一个未被访问过的顶点作为起始顶点，沿着当前顶点的边走到未被访问过的顶点；当没有未被访问过的顶点时，回到上一个顶点，继续试探访问别的顶点，直到所有的顶点都被访问过。显然，深度优先遍历是沿着图的某一条分支遍历直到末端，然后回溯，再沿着另一条继续遍历，直到所有的顶点都被访问过为止。

算法实现

// 深度优先遍历的算法
template<class vertexType, class arcType>void Graph <vertexType, arcType> ::
DFTraverse ( void visit( vertexType v )) {
    int i, n = NumberOfVertexes() ;//取图的顶点个数
    int * visited = new int [n]; //定义访问标记数组 visited
    for ( i = 0; i < n; i++ )
        visited [i] = 0;  //访问标记数组 visited 初始化
    for ( i = 0; i < n; i++ ) //对图中的每一个顶点进行判断
      if (!visited [i]) DFS (v, visited, visit );
    delete [ ] visited; //释放 visited
}

// 深度优先搜索
template<class vertexType, class arcType>void
Graph<vertexType, arcType> ::
DFS ( const int v, int visited [ ], void visit( vertexType v )) {
    visit( GetValue (v));  //访问顶点 v
    visited[v] = 1;          //顶点v 作访问标记
    int w = GetFirstNeighbor (v);
    while ( w != -1 ) {          //若顶点 w 存在
        if ( !visited[w] ) DFS ( w, visited );
        w = GetNextNeighbor ( v, w );
    }  //重复检测 v 的所有邻接顶点
}

最短路径的实现：

int min = 999999999, n, book[100], e[100][100];
void dfs(int cur, int dis){
      if(dis > min) return;
      if(cur == n){ // 判断是否到达目标城市
          if(dis < min) min = dis; // 更新最小值
          return；
      }

      for(int i=0; i<n; i++){
          if(e[cur][i] != 99999999 && book[i] == 0){
            book[i] = 1;
              dfs(i,dis+e[cur][i]);
              book[i] = 0;
          }
      }
      return;
}