图深度优先遍历图的方法是，从图中某顶点v出发：
（1）访问顶点v；
（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。 当然，当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法，那就是广度优先搜索(BFS).
在我们遇到的一些问题当中，有些问题我们不能够确切的找出数学模型，即找不出一种直接求解的方法，解决这一类问题，我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探，按照一定的顺序、规则，不断去试探，直到找到问题的解，试完了也没有找到解，那就是无解，试探时一定要试探完所有的情况（实际上就是穷举）； [2]
对于问题的第一个状态，叫初始状态，要求的状态叫目标状态。
搜索就是把规则应用于实始状态，在其产生的状态中，直到得到一个目标状态为止。
产生新的状态的过程叫扩展（由一个状态，应用规则，产生新状态的过程）
搜索的要点：（1）初始状态；
（2）重复产生新状态；
（3）检查新状态是否为目标，是结束，否转（2）； [1]
如果扩展是首先扩展新产生的状态，则叫深度优先搜索。
深度优先搜索
（3） 判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态；
（4） 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法。
搜索是人工智能中的一种基本方法，是一项非常普遍使用的算法策略，能够解决许许多多的常见问题，在某些情况下我们很难想到高效的解法时，搜索往往是可选的唯一选择。按照标准的话来讲：搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。
搜索虽然简单易学易于理解，但要掌握好并写出速度快效率高优化好的程序却又相当困难，总而言之，搜索算法灵活多变，一般的框架很容易写出，但合适的优化却要根据实际情况来确定。在搜索算法中，深度优先搜索（也可以称为回溯法）是搜索算法里最简单也最常见的，今天我们就从这里讲起，下面的内容假设读者已经知道最基本的程序设计和简单的递归算法。
所有的搜索算法从其最终的算法实现上来看，都可以划分成两个部分──控制结构和产生系统。正如前面所说的，搜索算法简而言之就是穷举所有可能情况并找到合适的答案，所以最基本的问题就是罗列出所有可能的情况，这其实就是一种产生式系统。 [2]
上面的话可能难于理解，没关系，我们通过基本框架和例子来阐述这个算法，你会发现其中的原理非常简单自然。
·dfs(状态) [3]
–if 状态 是 目标状态then
·dosomething
–else
·for 每个新状态
–if 新状态合法
»dfs(新状态)
·主程序：
·dfs(初始状态)
定义一个结构体来表达一个NODE的结构： [2]
struct Node { int self; //数据 node *left; //左节点 node *right; //右节点 };
“
A B C D E F G
”
A是第一个访问的，然后顺序是B和D、然后是E。然后再是C、F、G。那么我们怎么来保证这个顺序呢？ [3]
“
const int TREE_SIZE = 9;
std::stack<node*> visited, unvisited;
node nodes[TREE_SIZE];
node* current;
for( int i=0; i<TREE_SIZE; i++) //初始化树
{
nodes[i].self = i;
int child = i*2+1;
if( child<TREE_SIZE ) //Left child
nodes[i].left = &nodes[child];
else nodes[i].left = NULL;
child++;
if( child<TREE_SIZE ) //Right child
nodes[i].right = &nodes[child];
else nodes[i].right = NULL;
}
unvisited.push(&nodes[0]); //先把0放入UNVISITED stack
while(!unvisited.empty()) //只有UNVISITED不空
{
current=(unvisited.top()); //当前应该访问的
unvisited.pop();
if(current->right!=NULL)
unvisited.push(current->right); // 把右边压入 因为右边的访问次序是在左边之后
if(current->left!=NULL)
unvisited.push(current->left);
visited.push(current);
cout<<current->self<<endl;
}
”
这道题来举例（迷宫）
1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 |
记录起点为（1,1）找到所有的到（4,4）的路径.
pascal程序如下：
const
b:array[1..4,1..4]of integer=(（1,1,1,1）,(0,1,0,1）,(0,1,0,1）,(0,1,1,1）);
c:array[1..4,1..2]of -1..1=((0,1）,(0,-1）,（1,0),(-1,0));
var
a:array[1..16,1..2]of integer;
procedure print;
var
i,j:integer;
begin
for i:=1 to 4 do
begin
for j:=1 to 4 do
write(b[i,j]:3）;
writeln;
end;
writeln('--------------');
end;
procedure try(k:integer);
var
i:integer;
begin
if (a[k,1]=4）and(a[k,2]=4） then
begin
print;
exit;
end;
for i:=1 to 4 do
begin
a[k+1,1]:=a[k,1]+c[i,1];
a[k+1,2]:=a[k,2]+c[i,2];
if (a[k+1,1]>=1） and (a[k+1,1]<=4 )and (a[k+1,2]>=1） and (a[k+1,2]<=4） and
（b[a[k+1,1],a[k+1,2]]=1） then
begin
b[a[k+1,1],a[k+1,2]]:=2;
try(k+1）;
b[a[k+1,1],a[k+1,2]]:=1;
end;
end;
end;
begin
a[1,1]:=1;
a[1,2]:=1;
b[1,1]:=2;
try（1）;
end.
这个程序的意思就是：进行搜索一条路，直到不能走为止，换另一条路。
