java - DFS Java 实现 : how to write "Element in deque/stack"

Question

我卡在 DFS java 实现中的一行中间:如何表达“双端队列/堆栈中的顶点？”

我需要在 for 循环中写一行来表示顶点“u”在双端队列/堆栈中。初始值为“toExplore”的第一项。

下面是我的代码:

public List<Integer> DepthFirstList(Integer v)
{
    List<Integer> vertices = new ArrayList<Integer>(); 
    Deque<Integer> toExplore = new ArrayDeque<Integer>(); //The deque,used as the stack in DFS
    List<Integer> visited = new ArrayList<Integer>();
    toExplore.push(v);
    visited.add(v);
    while(!toExplore.isEmpty())
    {
        boolean hasNeighbor=false;
        for()//To be more precise, u should be a vertex never visited. How can I make this change?
        {
            if(g.hasEdge(v, u)) 
            {
                toExplore.push(u);
                visited.add(u);
                hasNeighbor=true;
                break;
            }

        }
        if(hasNeighbor==false) 
        {
            toExplore.pop();
            vertices.add(v);
        }
        else hasNeighbor=false;
    }
    return vertices;
}

Answer 1

将您的 for 循环替换为以下内容应该有效:

v = toExplore.peek();
for (int u: getAdjList(v).keySet())
{
   if (!visited.contains(u))
   {
      ...
   }
}

邻接表似乎包含其他顶点索引到边权重的映射，因此 keySet 会为我们提供所有顶点的列表。

一些随机笔记:

• 如果允许的话，我会推荐一种递归方法。一旦你了解了递归，它就会简单得多(从长远来看，这绝对是一件让人感到舒服的好事)。但是以非递归方式编写递归算法当然是一种很好的编程习惯。

• 如 Louis 所述，如果可以的话，将 visited 设为 Set (HashSet) 会好得多。这将允许预期的 O(1)(恒定时间)查找，而不是 O(n)(线性时间)。

• 此外，我可能会将 toExplore 设为 Stack，因为您只会使用基于堆栈的方法。