DFS Java implementation: how to write "Element in deque/stack"

Question

I am stuck in the middle of a line in DFS java implementation: how can I express "a vertex in a deque/stack?"

I need to write a line in the for loop to express vertex "u" is in the deque/stack. The initial value is the first item of "toExplore".

Below is my code:

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

Replacing your for-loop with the below should work:

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

It seems like the adjacency list contains a mapping of the other vertex index to the edge weight, so the keySet would give us a list of all the vertices.

Some random notes:

• I would recommend a recursive method, if you're allowed. It's a lot simpler once you get your head around recursion (which is definitely a good thing to be comfortable with in the long run). But writing recursive algorithms non-recursively is certainly good programming practice.

• As Louis mentioned, making visited a Set (HashSet) would be much better, if able. This would allow for expected O(1) (constant time) lookup, as opposed to O(n) (linear time).

• Also, I'd probably make toExplore a Stack as you'd only be using stack-based methods.