java - Duplicates in depth first search algorithm

Question

I'm writing a program in Java where I must implement three search algorithms, among the three is the depth first graph-search algorithm. My program traverses a connected graph represented internally by an adjacency matrix and uses a frontier and an explored set with each algorithm.

The frontier stores the unexplored child nodes of expanded parent nodes and the explored set stores those nodes which have actually been expanded. The purpose of the explored set is to avoid duplicates and thus avoid infinite loops.

My frontier is implemented using a linked blocking deque and my explored set using a linked hash set.

However, upon testing the initial version of this algorithm implementation I noticed that there were still a small number of duplicates, particularly when the goal node did not exist and the algorithm would surely have to visit every node in the graph. Eventually I realized that this is because when a node is expanded all of its child nodes are added to the frontier but only one of them is explored. Because the graph is a connected one then other paths may exist to the node and this may result in the node being encountered multiple times before it is ever expanded and thus added to the explored set.

This leads me to my question, do i fix it?

The depth first search is supposed to explore one side of the tree formed from the graph first and then backtrack, this means that even if it encounters a less optimal goal node on one side of the tree it should return that instead of a (more optimal) one previously encountered but not yet explored.

However, if I am implementing an explored set for the purpose of avoiding duplicates it seems contradictory that I allow them in certain instances.

I believe the real error may lie in a lack of thorough understanding of the algorithm and I am sincerely hoping for some assistance, thanks in advance.

Answer 1

The algorithm commonly known as depth first search does not need a "frontier", as you call it. This concept is used however with A* graph searches (it is usually called "open set" there).

For standard depth first search, all you need is a stack of nodes: Push the initial node on the stack, then in each step pop one node from the stack, examine it and push all its neighbours(*) on top of the stack. Then, repeat.

(*) remember to mark all nodes that you push on the stack as visited (I believe you call this "explored set" in your questions) and don't push nodes that have already been visited.

By using a stack, you avoid the problem you describe.

If you actually want to maintain that frontier/open set, make sure that it never contains duplicates: use a data structure that does not allow duplicates (e.g. a set).

(Sidenote: If your graph nodes have a natural numbering and you expect your DFS to visit the majority of notes, you may as well use an array/vector for your explored set/closed set.)