1）深度优先遍历（deep first traverse）
定义：假设给定图G的初态是所有顶点均未曾访问过，在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止，这里定义使用的就是递归定义。
图的深度优先遍历类似于树的前序遍历，采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历
递归方式实现深度遍历的编码思想：所谓深度优先就是以纵向优先的方式遍历节点。我们从当前节点curr出发，如果当前节点被访问过，就返回，否则将该节点标记为访问过的节点，然后在递归访问当前节点的所有邻接节点。
伪代码：
function traverse（Node node）｛ //递归方式实现的深度优先遍历
if(node.isVisited){ //如果当前节点已经被访问过
return; //这个是递归出口
}
node.isVisited=true; //将当前节点置为已经访问
for(var i=0;i<node.brother.length;i++){
traverse(node.brother[i]); //访问当前node的所有邻接节点
}
return; //结束
｝
栈和回溯方式实现深度遍历的编码思想：首先我们需要一个栈结构来存放需要被访问的节点，当然栈的第一个元素是我们传入的node节点，如果这个栈里面还有节点的话，拿出栈顶节点，访问该节点，然后将这个节点的所有未被访问的邻接节点压入栈中，具体过程请看下图：
首先1入栈，1出栈，1被标记为被访问，1的邻接节点2,7,8入栈，8出栈，8被标记为被访问，8的邻接节点9,12入栈，现在栈中的节点为2，7，9，12，然后12出栈，12被访问，由于12没有邻接节点，所以没有节点被加入，9出栈，9被访问，10,11入栈，现在栈中的节点是2,7,10,11，接下来11出栈，11被访问，由于11没有邻接节点，所以没有节点被加入，10出栈，10被访问，现在栈中的节点为2,7,接下来的依次类推即可，下面的代码就描述了这个过程。
伪代码：
function dft(Node node){ //栈方式实现的深度优先遍历，栈回溯法
var stack=[],temp;
stack.push(node); //初始化栈结构，将当前要访问的节点放入栈中
while(stack.isNotEmpty()){
temp=stack.pop(); //拿到当前要访问的节点
temp.isVisited=true; //将当前节点置为已经访问
for(var i=0;i<temp.brother.length;i++){
if(!temp.brother[i].isVisited){
stack.push(temp.brother[i]); //将当前节点未被访问的邻接节点加入栈中
}
}
}
}
（2）广度有限遍历（broad first traverse）
定义：广度优先遍历是连通图的一种遍历策略，它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域。也就是从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点；
队列实现广度优先遍历思想：所谓的广度优先指的是从当前节点curr出发，将该节点标记为已经访问过的节点，然后在依次访问curr的没有被访问的邻接节点，然后在依次访问邻接节点的邻接节点，直到所有的节点被访问。具体过程请看下图：
首先，1入队，1出队，1被访问，2,7,8入队，2出队，2被访问，3,6入队，现在队列为7,8,3,6，然后7出队，由于没有和7邻接的节点，依次没有节点入队，8出队，8被访问，9,12入队，现在队列为3,6,9,12，接下来3出队，3被访问，4,5入队，依次类推，下面的代码就描述了这个过程。
伪代码：
function bft(Node node){
var queue=[],temp; //队列结构，是待访问的节点队列，这些节点被排了顺序，按顺序被访问
queue.push(node); //初始化队列结构
while(queue.isNotEmpty())｛ //当队列不为空的时候
temp=queue.shift(); //取得当前的节点元素
temp.isVisited=true; //将当前节点置为已经访问
for(var i=0;i<temp.brother.length;i++){
if(!temp.brother[i].isVisited){ //如果当前节点的邻接节点没有被访问过
queue.push(temp.brother[i]); //将这个邻接节点加入待访问队列
}
}
｝
}
（3）总结
使用递归和不使用递归的区别，假设到达目标需要begin->step1->step2->step3->…->stepN->target,其中stepN表示解决方案N，然后递归的方法是先拿到解决N，然后在退一步，拿到解决方案stepN-1,依次类推，直到最终拿到step1解决方案，而非递归方法是先拿到step1，然后在拿step2，最终拿到stepN。
