一、思路
指定的起始点和终点，确定好当前点与邻接点之间的偏移值、结束搜索的条件、符合访问的点所需条件、回溯处理
1、若当前点的邻接点有未被访问的，则选一个进行访问；
2、若当前点的邻接点都不符合访问条件，退回到当前点的上一个点；
3、直到访问到目标终点，或是所有点均以访问仍无法到达终点；
二、伪代码
DFS可以通过递归函数、栈（先入后出的存储结构）来实现
1、递归方法实现思路
2、栈实现思路
三、实例
前段时间正好帮同学敲一个迷宫的讲解，针对具体题目H是墙，O是路。。。
代码由C++编写
1 #include <stack> 2 #include <cstdio> 3 #include <string> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 8 typedef struct { 9 int x, y, step; 10 }point; 11 void out(int a[100][100], int m, int n){//用于查看迷宫地图 12 int i, j; 13 for(i = 0; i < m; i++){ 14 for(j = 0; j < n; j++) 15 cout << a[i][j] << " "; 16 cout << endl; 17 } 18 } 19 20 int main(){ 21 int t, z; 22 cout << "请输入需要走几个迷宫：" << endl; 23 while(cin >> t){ 24 int m, n; 25 for(z = 0; z < t; z++){ 26 int i, j; 27 string str; //用于输入 28 stack<point> s; //用于保存已走的路径 29 point start, end; //起始点和终止点 30 int map[100][100]; //迷宫地图 31 int d1[4] = {-1, 0, 1, 0}; //走迷宫的过程中上下方向的偏移值 32 int d2[4] = {0, 1, 0, -1}; //走迷宫的过程中左右方向的偏移值 33 34 cout << "请输入第" << z+1 << "个迷宫的行列：" << endl; 35 cin >> m >> n; 36 37 cout << "请输入第" << z+1 << "个迷宫：" << endl; 38 for(i = 0; i < m; i++){ //利用转化的方式，将输入变为数据地图 39 cin >> str; 40 for(j = 0; j < n; j++){ 41 if(str[j] == 'H') 42 map[i][j] = 1; 43 if(str[j] == 'O') 44 map[i][j] = 0; 45 } 46 }//out(map, m, n); //查看迷宫地图 47 48 cout << "请输入起点坐标和终点坐标：" << endl; 49 cin >> start.x >> start.y >> end.x >> end.y; 50 51 start.step = 1; 52 map[start.x][start.y] = -1; //将起始点在地图上标记出来 53 s.push(start); 54 while(!s.empty()){ 55 point p = s.top(); 56 57 if(p.x == end.x && p.y == end.y) //判断是否到达终点 58 break; 59 60 for(i = 0; i < 4; i++){ 61 int dx = p.x + d1[i]; //下一步的上下位置 62 int dy = p.y + d2[i]; //下一步的左右位置 63 //判断邻接点是否符合走的要求 64 if(dx>=0 && dx<m && dy>=0 && dy<n 65 && map[dx][dy] == 0){ //判断该点是否可走 66 map[dx][dy] = -1; //走过的点进行标记 67 point px; 68 px.x = dx, px.y = dy, px.step = p.step+1; 69 s.push(px); //将这个符合行走条件的点入栈 70 break; //保证每次只走一步 71 } 72 } 73 if(i == 4) //当i为4的时候，就是四周都不能走 74 s.pop(); 75 } 76 if(s.empty()){//因栈为空而停止循环，当然是无法走出迷宫 77 cout << "无法走出迷宫！" << endl; 78 continue; 79 }//out(map, m, n); //查看迷宫地图行走情况 80 81 i = 0; 82 point *road = new point[m*n]; //用于输出走出迷宫的路径 83 while(!s.empty()){ //读取走过的点 84 point p = s.top(); 85 road[p.step] = p; 86 s.pop(); 87 i++; 88 } 89 cout << "走出迷宫共用了" << i << "步，经过的点为："; 90 for(i = 1; i < j; i++) 91 cout << road[i].x << "," << road[i].y << "->"; 92 cout << road[i].x << "," << road[i].y << endl; 93 } 94 cout << "请输入需要走几个迷宫：" << endl; 95 } 96 return 0; 97 }
等待更新。。。