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.

A graph traversal algorithm typically involves a graph of some kind, with nodes that have connectivity. Your question doesn't include any graph structure to search. If you're looking for examples of graph traversal problems, try searching the problem archive on single round matches on top-coder. About half of the mid-difficulty level problems end up reducing to graph traversal. — Jherico

Bernhard Barker Bernhard Barker · Accepted Answer · 2013-12-09T21:41:25

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.

Depth First Search in Java

1 Answers