关注码农话题
做一个实实在在的内行人

深度优先遍历

深度优先搜索算法

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

Depth First Search

正如上面给出的例子,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;
   }        
}

入职你的梦想 VS 变现你的技术

IT面试宝典码农市场