深度优先搜索算法 

    深度优先搜索算法（Depth-First-Search，简称DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

   深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。

算法实现：

    利用函数栈来保存当前搜索路径中每个节点的状态，每搜索一个新节点，就标记此节点被使用并递归调用一次dfs函数，确定此节点在本路径中无法到达终点，则return上一级函数，更换下一节点。

注意问题：

1、回溯后是否要将节点标记重置应该看路径来源是否会对节点能否到达出口产生影响，如果任意路径到达此节点都不会影响它能否到达终点，则不去除标记，因为即使下一次搜索到它，也知道它无法到达终点，从而跳过它。

如果不同路径来源会影响，则需要重置标记，保证能被其他路径再次选取。

2、剪枝，通过对题目的理解，在选取节点递归之前，直接判断此节点能否到达终点，从而减少大量不必要的搜索过程。

   扩展：点击打开链接

Eg:

POJ2386：有一个大小为N*M的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼？

***

*W*

***

/*从任意的W开始，不停地把邻接的部分用“。”代替。1次dfs后与初始的这个W连接的所有W就被替换成了“。”，因此直到图中不再 
 *存在W为止，总共进行DFS的次数就是答案了。8个方向共对应了8种状态转移，每个格子作为DFS的参数至多被调用一次，所以复杂度为O(N*M）  
*/  
  
int N, M;  
char field[MAX_N][MAX_N + 1];  
  
//现在位置（x, y)  
void dfs(int x, int y) {  
    //将现在所在位置替换为.   
    field[x][y] = '.';  
      
    //循环遍历移动的8个方向  
    for (int dx = -1; dx <=1; dx ++ ) {  
        for (int dy = -1; dy <= 1; dy ++) {  
            // 向x方向移动dx，向y方向移动dy，移动的结果是(nx, ny)  
            int nx = x + dx, ny = y + dy;  
            //判断(nx,ny)是不是在园子内，以及是否有积水  
            if (0<=nx && nx < N && ny>=0 && ny<M && field[nx][ny] == 'W')   dfs(nx, ny);   
        }  
    }   
    return ;  
}   
  
void solve() {  
    int res = 0;  
    for (int i = 0; i<N; i++) {  
        for (int j = 0; j<M; j++) {  
            if (field[i][j] == 'W') {  
                //从有W的地方开始dfs  
                dfs(i, j);  
                res ++ ;   
            }  
        }  
    }  
    cout << res << endl;  
}  

 广度优先搜索算法 

const int INF = 100000000;  
  
//使用pair表示状态时，使用typedef会更加方便一些  
typedef pair <int, int> P;  
  
char maze[MAX_N][MAX_M+1];  //表示迷宫的字符串数组  
int N, M;  
int sx, sy;     //起点坐标  
int gx, gy;     //终点坐标  
  
int d[MAX_N][MAX_M];    //到达各个位置的最短距离的数组  
  
//4个方向移动的向量  
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};  
  
//求从{sx, sy} 到{gx, gy}的最短距离  
//如果无法到达，则是INF  
int bfs() {  
    queue<p> que;  
    //把所有的位置都初始化INF  
    for (int i = 0; i<N; i++)   
        for (int j = 0; j<M; j++)    d[i][j] = INF;  
    //将起点加入队列，并把这一地点的距离设置为0  
    que.push(P(sx, xy));  
    d[sx][xy] = 0;  
      
    //不断循环直到队列的长度为0  
    while (que.size())  {  
        //从队列的最前端取出元素  
        P p = que.front();  que.pop();  
        //如果取出的状态已经是终点，则结束搜索  
        if (p.first == gx && p.second == gy)    break;  
          
        //四个方向的循环  
        for (int i = 0; i<4; i++) {  
            //移动之后的位置记为(nx, ny)  
            int nx = p.first + dx[i], ny = p.second + dy[i];  
              
            //判断是否可以移动以及是否已经访问过(d[nx][ny] != INF即为已经访问过）  
            if (0 <= nx && nx < N && 0 <= ny && ny < M && maze[nx][ny] != '#' && d[nx][ny] == INF) {  
                //可以移动的话，则加入到队列，并且到该位置的距离确定为到p的距离加1  
                que.push(P(nx, ny));  
                d[nx][ny] = d[p.first][p.second] + 1;   
            }   
        }   
    }  
    return d[gx][gy];  
}   
  
void solve() {  
    int res = bfs();  
    cout << res << endl;  
}