Depth First Search in Java

Question

I have an assignment that needs an implementation of DFS in java.

The stab was written as below:

public List<Integer> DepthFirstList(Integer v) 
{
    List<Integer> vertices = new ArrayList<Integer>();
    Deque<Integer> toExplore = new ArrayDeque<Integer>();
    List<Integer> visited = new ArrayList<Integer>();
    return vertices;
}

It takes an argument of v (which is the starting point as an integer), and traverses all the graph. I understand that toExplore is the stack of a sequence of all nodes. "visited" is the array to include whether the nodes are visted (By assigning "0" or "1"), and they are initialized to all "0". But what is the "vertices" that needs to return?

A typical graph would be something like below:

9//Number of vertices
0: {1,6} {8,2} {5,4}//{edge with, weight}
1: {0,6} {2,7} {4,9}
2: {3,4} {4,3} {1,7}
3: {1,5} {5,3}
4: {2,3} {6,1}
5: {3,3} {0,7}
6: {4,1} {1,2}

Code to read the input has already been written.

Answer 1

But what is the "vertices" that needs to return?

Based on the name of the function, I imagine you should return a list of visited vertices in the order they are visited.

Unless I'm missing something, this would be the same as visited, which is somewhat redundant. But visited really should be a Set for efficient lookup, which would make having vertices make more sense.

But I can't know for sure what your teacher was thinking. You should probably go and ask them to make sure.

I'm assuming (based on your question) that you're not looking for help writing this function, just understanding this part.