Depth first traversal of connected graph using jung not showing right traversal

Question

I am implementing depth first traversal of a graph drawn by the user using jung.

I have following code at this moment:

 public <V,E> void dftdraw(Graph<V,E> g) {
    V start = null;      
    for (V v:g.getVertices()){
        if(v.toString().equals("0"))
           start = v; 
    }

    Set visited = new HashSet();
    LinkedList stack = new LinkedList();
    stack.add(start);
    System.out.println(start.toString());
    // traverse through graph in depth-first order
    while (!stack.isEmpty())
    {
        V v = (V)stack.removeFirst();
        visited.add(v);
        Set neighbors = (Set) g.getNeighbors(v);

        for (Iterator n_it = neighbors.iterator(); n_it.hasNext(); )
        {
            V w = (V)n_it.next();

            if (!visited.contains(w)){
                System.out.println(w.toString());
                stack.addFirst(w);
            }
        }
    }
}

But this is not doing depth first, it's first printing out the vertices connected to the starting vertex, and not like, traversing first connected vertex, then traversing through it's connected vertices.

Answer 1

That's because you're printing the vertex too soon. If you want them printed in the visiting order, you need to print at the time you're visiting (after you remove the vertex from stack). Otherwise the algorithm seems OK.

Answer 2

So , now I am doing Depth first traversal , by recursion using the following code :

public <V, E> void dftdraw(Graph<V, E> g) {

    V start = null;

    for (V v : g.getVertices()) {
        if (v.toString().equals(jTextField2.getText())) {
            start = v;
        }

    }

    if(!visiteddfs.contains(start)) {
        dfspath(g,start);
    }


    for(int i=0;i<l2.size();i++){

        jTextField4.setText(jTextField4.getText() + " " + l2.get(i));
    }

}

public <V,E> void dfspath(Graph<V,E> g,V v){

    visiteddfs.add(v);
    l2.add(v);
    Set neighbors = (Set) g.getNeighbors(v);
        //System.out.println(v);

        for (Iterator n_it = neighbors.iterator(); n_it.hasNext();) {
            V w = (V) n_it.next();

        if(!visiteddfs.contains(w)){

            dfspath(g,w);
        }

    }
    finisheddfs.add(v);

}

and with slight modifications , the code posted in the question is used for breadth first traversal . Here's the code for that :

    public <V, E> void bstdraw(Graph<V, E> g) {

    V start = null;

    for (V v : g.getVertices()) {
        if (v.toString().equals(jTextField1.getText())) {
            start = v;
        }
    }

    Set visited = new HashSet();
    LinkedList stack = new LinkedList();
    stack.add(start);
    visited.add(start);
    l.add(start);
    // traverse through graph in depth-first order
    while (!stack.isEmpty()) {
        V v = (V) stack.removeFirst();
        Set neighbors = (Set) g.getNeighbors(v);
        //System.out.println(v);

        for (Iterator n_it = neighbors.iterator(); n_it.hasNext();) {
            V w = (V) n_it.next();

            if (!visited.contains(w)) {
                l.add(w);
                g2.addEdge("edge" + w, (Integer) v, (Integer) w);
                jPanel4.repaint();
                jPanel4.updateUI();

                visited.add(w);
                stack.addLast(w);

            }
        }
    }

    for (int i = 0; i < l.size(); i++) {

        jTextField3.setText(jTextField3.getText() + " " + l.get(i));

    }
}