DFS Java 实现：如何编写 "Element in deque/stack"

Question

在DFS java实现中，我被困在了一行的中间：如何表达"deque/stack中的顶点？"

我需要在for循环中写一行来表示顶点"u"在deque/stack中。初始值是"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，因为您只会使用基于堆栈的方法。