圖理論深度優先搜索

Question

在使用堆棧實現DFS遍歷時，如果元素已經在堆棧中但未被訪問，是否需要將元素推入堆棧？

Answer 1

如果它已經在 堆棧內但未被訪問，我們是否需要將元素推入堆棧？

答案是沒有，因爲它是進入循環的一種方式..

如果您遍歷圖使用深度優先搜索，你很可能會陷入循環..

避免使用禁忌之列，這使所有訪問過的節點的ID這個問題最好的辦法..

stack.push(init); 

while (!stack.empty()) 
{ 
    current = stack.pop(); 
    taboo.add(current.id); 

    if (isGoal(current)) 
    { 
     break; 
    } 

    for (Node neighbor : getNeighbors(current)) 
    { 
     if (!taboo.contains(neighbor.id)) 
     { 
      stack.push(neighbor); 
     } 
    } 

}