深度优先遍历

深度优先搜索算法

深度优先搜索算法(DFS)遍历深度区运动的图并使用堆栈记下要获得的下一个顶点，当一个死尾发生时迭代开始搜索。

正如上面给出的例子，DFS算法从A遍历到B到C再到D到E，然后到F，最后到G它采用下列规则。

• 规则 1 − 访问邻近的未访问顶点。标记它已访问。并显示它，最后将其推入堆栈。

• 规则 2 − 如果没有相邻顶点发现，从堆栈中弹出一个顶点。(它会从栈弹出没有相邻顶点的所有顶点)

• 规则 3 − 重复第1条和第2条，直到堆栈为空。

void depthFirstSearch(){
   int i;
	
   //mark first node as visited
   lstVertices[0]->visited = true;
	
   //display the vertex
   displayVertex(0);   
	
   //push vertex index in stack
   push(0);

   while(!isStackEmpty()){
      //get the unvisited vertex of vertex which is at top of the stack
      int unvisitedVertex = getAdjUnvisitedVertex(peek());
		
      //no adjacent vertex found
      if(unvisitedVertex == -1){
         pop();
      }else{
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         push(unvisitedVertex);
      }
   }

   //stack is empty, search is complete, reset the visited flag        
   for(i = 0;i < vertexCount;i++){
      lstVertices[i]->visited = false;
   }        
}