Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 2 of 2

Thread: DFS in Graphs

  1. #1
    New to the CF scene
    Join Date
    Apr 2011
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    DFS in Graphs

    This is the implementation of DFS using stacks, but when I try to run this it gives an infinite loop at the first vertex. Graph class has a array of nodes as it's attribute. The node class is used for both Vertices and Edges. I've tested whether the graph is read in correctly or not and it has been. I could provide the input file and the readFile method used to generate the graph. I don't know why it gets stuck in an infinite loop here.

    Code:
    public static void dfs(Node start)
    {
    //DFS uses Stack data structure
    Stack s=new Stack();
    s.push(start);
    start.visited=true;
    System.out.println(start.item);
    while(!s.isEmpty())
    {
        Node n= (Node)s.peek();
                Node child=getUnvisitedChildNode(n);
        if(child!=null)
        {
            child.visited=true;
            System.out.println(child.item);
            s.push(child);
        }
    
        else
        {
            s.pop();
        }
    }
    
    }
    
    public static Node getUnvisitedChildNode(Node n){
    Node missing_child = new Node();
    Node counter = new Node(n.item);
    while(counter!=null){
         if (!counter.visited)
             missing_child = counter;
    counter = counter.next;
    
    }
    
    
    return missing_child;
    }
    Last edited by antislayer; 04-24-2011 at 04:35 PM.

  • #2
    God Emperor Fou-Lu's Avatar
    Join Date
    Sep 2002
    Location
    Saskatoon, Saskatchewan
    Posts
    16,979
    Thanks
    4
    Thanked 2,659 Times in 2,628 Posts
    The problem will be here:
    Code:
    Node counter = new Node(n.item);
    Counter is a semi-cloned node, and I assume that .item doesn't include an edge or node list. Real problem here is you are not modifying the real node's visited status. So you essentially are trying to fetch the first child of the first child over and over again since it doesn't realize its been visited.
    I don't like the idea of having visited incorporated as a part of the Node class. If you do this, it means you need to go through and reset all item's visited status either prior to or after any traversal. A better option is to track the visited status in an array or collection, and compare it when you are iterating the whiles.
    PHP Code:
    header('HTTP/1.1 420 Enhance Your Calm'); 


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •