图论深度优先搜索

Question

使用栈来实现深度优先搜索时，如果一个元素已经在栈中但尚未被访问，我们是否需要将其推入栈中？

- Sekharan Natarajan

---

请包含一些代码以展示你尝试过什么。 - Serge Belov

不需要将已经在堆栈中的节点再次推入。 - axiom

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);
        }
    }

}

- Khaled.K