在使用栈实现DFS遍历时,如果元素已经在栈中但没有被访问,是否需要将元素压入栈中?
最佳答案
Do we need to push the element into the stack if it's already inside the stack but not visited?
答案是不,因为这是进入循环的一种方式..
如果您使用深度优先搜索遍历图,您很可能会陷入循环。
避免该问题的最佳方法是使用禁忌列表,它保留所有已访问节点的 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);
}
}
}
关于algorithm - 图论深度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13659018/