javasearchiterative-deepening

Iterative deepening search using my DFS


I have a DFS search and now I am trying to implement Iterative deepening search with this DFS but I really do not understand what should I do. I have tried many ways but finally I found It was wrong! Do you have any suggestion that what changes should I do?

public void dfs()
    {
        Stack s=new Stack();
        s.push(this.rootNode);
        rootNode.visited=true;
        printNode(rootNode);
        while(!s.isEmpty())
        {
            Node n=(Node)s.peek();
            Node child=getUnvisitedChildNode(n);
            if(child!=null)
            {
                child.visited=true;
                printNode(child);
                s.push(child);
            }
            else
            {
                s.pop();
            }
        }
        clearNodes();
    }

Solution

  • Alright, let's try something.

    You need to change your function to limit the depth of the search. To prevent the lower level nodes to be printed multiple times, I will only print the nodes at maximum depth.

    This gives:

    public void ids(int limit)
        {
            for (int n = 1; n <= limit; ++n)
            {
                dfs(n);
            }
        }
    
    public void dfs(int limit)
        {
            Stack s=new Stack();
            s.push(this.rootNode);
            rootNode.visited=true;
            while(!s.isEmpty())
            {
                Node n=(Node)s.peek();
    
                if (stack.size() == limit)
                {
                    printNode(n);
                    s.pop();
                } else {
                    Node child=getUnvisitedChildNode(n);
                    if(child!=null)
                    {
                        child.visited=true;
                        s.push(child);
                    }
                    else
                    {
                        s.pop();
                    }
                }
            }
            clearNodes();
        }