Depth first depth search

Question

I am trying to implement a first level depth search algorithm in Java. Any idea why this method goes into an infinite loop? Thanks.

public Node search(Graph graph, String nodeName, int ID) { //Get the root node Node root = graph.getRoot(); Stack<Node> stack = new Stack<Node>(); //Add the root to the stack stack.push(root); while(!stack.isEmpty()) { Node n = stack.pop(); //Check to see if node n is the requested node if(n.getName().equals(nodeName)) { //Found return n; }else { //Create an array of the leaf nodes to node n Node[] children = n.getNeighbours(); for(int i =0; i<children.length; i++) { //Add the leaf nodes to the stack stack.push(children[i]); System.out.println(stack.peek()); } } } //Not found so return null return null; } 

Answer 1

If your chart is not a tree, it will have cycles. A node may be his own grandson. You need to prevent the addition of sites that you have already visited to the search tree.

A simple way to do this is through a different data structure:

 Set<Node> visitedNodes = new HashSet<Node>(); //... if ( !visitedNodes.contains(children[i]) ) { stack.push(children[i]); visitedNodes.add(children[i]); } 

Answer 2

If there are cycles on the chart (or they are not directional), you should “mark” the nodes after visiting them, otherwise you will continue to return to them.

Answer 3

If your graph contains any cycles, this is the expected behavior; A simple search by depth will first be visited by an already visited child, endlessly looping.

A simple way to avoid this is to add each node to the HashSet after checking to see if it is looking for a node, and then refuses to add it to the stack if it has already been verified.