Need HELP in Depth-First-Iterative Graph Traversal

[huiling25]

I was given the pseudo code.. but i still cannot figure out how to do it... how can i find if the vertices are adjacent to the vertex on stack top? I know i have to have an array of true/false (to dictate if the vertex is being visited)...

dfs(v)
{    create a stack s to store visited notes
    s.push(v)
    while(!s.isEmpty())
    {
        if(no unvisited vertices are adjacent to the vertex on stack top)
        {
             //need a method to peep at the top element
             s.pop() //backtrack
        }
        else
        {
             select an unvisited vertex u adjacent to the vertex on stack top
             s.push(u);
             mark u as visited
        }
    }
 
}

Graph.java

public class Graph {
    int        arraySize, graphSize;
    ListNode    node[];
 
            boolean[] visited= new boolean[arraySize];
 
    public Graph() {    // constructor
        arraySize = 10;
        graphSize = 0;
        node = new ListNode[arraySize];
        for (int j=0; j<arraySize; j++) node[j] = null;
    }
    public Graph(int size) {    // constructor
        arraySize = size;
        graphSize = 0;
        node = new ListNode[arraySize];
        for (int j=0; j<arraySize; j++) node[j] = null;
    }
 
    public boolean isEmpty() {
        return graphSize == 0;
    }
    public boolean isFull() {        
        return graphSize == arraySize;
    }
    public int getArraySize() {
        return arraySize;
    }
    public int getGraphSize() {
        return graphSize;
    }
 
    public boolean insertNode(NodeRecord r) { 
        int    j;
 
        if (isFull()) return false;
        for (j=0; j<arraySize; j++)
            if (node[j]==null) 
                break;
        node[j] = new ListNode(r);
        graphSize++;
        return true;
    }
 
//dfs method
public boolean insertEdge(int nodeID, EdgeRecord e) { 
     int    j;
    for (j=0; j<arraySize; j++)
        if (nodeID==((NodeRecord) node[j].getItem()).getID()) 
    break;
     if (j>=arraySize) return false;
    node[j].setNext(new ListNode(e, node[j].getNext()));
    return true;
    } 
    public void print() {
        int        j;
 
      ListNode    link;
 
          System.out.println(graphSize + " nodes read");
    for (j=0; j<graphSize; j++) {
        System.out.print(node[j].getItem()+"-> ");
        link = node[j].getNext();
        while (link!=null) {
             System.out.print(link.getItem());
             link = link.getNext();
        }
        System.out.println();
    }
    }
}

Record.java

public class Record implements Comparable {
    protected int        ID;
    protected String    name;
 
    public Record(int newID) {
        ID = newID;
        name = "";
    }
    public Record(int newID, String newName) {
        ID = newID;
        name = newName;
    }
    //set and get methods
    public int compareTo(Object o) {
         if (!(o  instanceof  Record) throw new IllegalArgumentException("Error: non-Record type object!");
        Record        c = (Record) o;        
        if (ID > c.ID) return 1;
        if (ID < c.ID) return -1;
        return 0;
    }
    public String  toString() {  // add to class Circle 
             return getID()+" ";
    }
}

NodeRecord.java

public class NodeRecord extends Record {
    public NodeRecord(int newID) {
    super(newID);
    }
    public NodeRecord(int newID, String otherInfo) {
    super(newID, otherInfo);
    }
    public int compareTo(Object o) {
    if (!(o  instanceof  NodeRecord)) throw new IllegalArgumentException("Error: non-NodeRecord type object!");
        NodeRecord    c = (NodeRecord) o;        
        if (ID > c.ID) return 1;
        if (ID < c.ID) return -1;
        return 0;
    }
}

EdgeRecord.java

public class EdgeRecord extends Record {
    public EdgeRecord(int newconnectedTo) {
        super(newconnectedTo);
    }
    public EdgeRecord(int newConnectedTo, String newOtherInfo) {
        super(newConnectedTo, newOtherInfo);
    }
    public int getConnectedTo() {
        return ID;
    }
    public String getOtherInfo() {
        return name;
    }
    public EdgeRecord setConnectedTo(int newconnectedTo) {
        ID = newconnectedTo;
        return this;
    }
    public EdgeRecord setotherInfo(String newOtherInfo) {
        name = newOtherInfo;
        return this;
    }
     public int compareTo(Object o) {
    if (!(o  instanceof  EdgeRecord)) throw new IllegalArgumentException("Error: non-EdgeRecord type object!");
        EdgeRecord    c = (EdgeRecord) o;        
        if (ID > c.ID) return 1;
        if (ID < c.ID) return -1;
        return 0;
    }
 
}

Stack.java

public class Stack extends List {
 
    public Stack() {    
        super();
    }
 
    public boolean push(Object newItem) {
        return insert(1, newItem);
    }
 
    public Object pop() {
        return remove(1);
    }
 
        public Object peek(){
 
        return super.getItem(super.size());
    }
 
}

[r035198x]

Bart's article should be able to give you some valuable pointers.

[huiling25]

I have changed my code a little.. I managed to do a little dfs.. but i am unable to get the value of the top item on the stack...

Graph.java

public class Graph {
    int        arraySize, graphSize;
        int row=0,col=0;
    ListNode    node[];
        int[][] matrix;
 
            boolean[] visited;
 
    public Graph() {    // constructor
        arraySize = 10;
        graphSize = 0;
        node = new ListNode[arraySize];
        for (int j=0; j<arraySize; j++) node[j] = null;
 
    }
    public Graph(int size) {    // constructor
        arraySize = size;
        graphSize = 0;
        node = new ListNode[arraySize];
        for (int j=0; j<arraySize; j++) node[j] = null;
                row=size;col=size;
                matrix = new int[row][col];
                 for(int i=0;i<row;i++)
                {
                    for(int j=0;j<col;j++)
                        matrix[i][j]=0;
                }
    }
 
    public boolean isEmpty() {
        return graphSize == 0;
    }
    public boolean isFull() {        
        return graphSize == arraySize;
    }
    public int getArraySize() {
        return arraySize;
    }
    public int getGraphSize() {
        return graphSize;
    }
 
    public boolean insertNode(NodeRecord r) { 
        int    j;
 
        if (isFull()) return false;
        for (j=0; j<arraySize; j++)
            if (node[j]==null) 
                break;
        node[j] = new ListNode(r);
        graphSize++;
        return true;
    }
 
        public boolean insert(int node, int connectedNode) //using this insert method
        {
            if(node>matrix.length || connectedNode>matrix[node].length)
                return false;
            matrix[node][connectedNode]=1;
            matrix[connectedNode][node]=1;
            return true;
        }
 
        public void dfs(int nodeID)
        {
            int j=0;
           visited = new boolean[row];
            Stack s= new Stack();
            for(int i=0;i<row;i++)
                visited[i]=false;
         s.push(nodeID);
            visited[nodeID]=true;
            while(!s.isEmpty())
            {
 
               while(j<col) 
               {
                 //s.peek() keep returning me 0...
                   int element = Integer.parseInt(s.peek().toString());
                   s.push(element);
                    if(visited[j]==true && matrix[element][j]==0)
                    {
                       //if(j!=nodeID)
                        //{
                             System.out.println(element);
                            s.pop();
                        //}
 
                    }
                    else
                    {
                        if(matrix[element][j]==1)
                            s.push(j);
                            visited[j]=true;
 
 
                   }
                   j++;
 
               }
            }
 
        }
 
 
    public void print() {
        for(int i=0;i<row;i++)
                {
                    for(int j=0;j<col;j++)
                    {
                        System.out.print(matrix[i][j]+" ");
                    }
                    System.out.println();
                }
    }
}

Stack.java

public class Stack extends List {
   // int i=0;
    public Stack() {    
        super();
    }
 
    public boolean push(Object newItem) {
           // if(super.size()==0)
        return insert(1, newItem);
            //else
              //  return insert(super.size()+1,newItem);
 
    }
 
    public Object pop() {
        return remove(1);
    }
 
    public Object peek()
    {
        //am i right here?
        return super.getItem(super.size());
    }
}