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());
    }
 
}