Depth First Traversal and Adj Matrix

Question

I'm trying to do a depth first traversal. I have no idea if I'm even close. Right now it's printing 1 3 4 5. It should be printing 1 2 4 7 3 5 6. Any help or advice is appreciated. Thanks. :)

Class:

 public class myGraphs {
     Stack<Integer> st;
     int vFirst;

     int[][] adjMatrix;
     int[] isVisited = new int[7];


     public myGraphs(int[][] Matrix) {
         this.adjMatrix = Matrix;
         st = new Stack<Integer>();
         int i;
         int[] node = {1, 2, 3, 4, 5, 6, 7};
         int firstNode = node[0];

         for (i = 1; i < node.length - 1; i++) {
             depthFirst(firstNode, node[i]);
         }
    }

    public void depthFirst(int vFirst, int n) {
        int v, i;

        st.push(vFirst);

        while (!st.isEmpty()) {
            v = st.pop();
            if (isVisited[v]==0) {
                System.out.print("\n"+v);
                isVisited[v]=1;
            }

            for ( i=1;i<=n;i++) {
                if ((adjMatrix[v][i] == 1) && (isVisited[i] == 0)) {
                    st.push(v);
                    isVisited[i]=1;
                    System.out.print(" " + i);
                    v = i;
                }
            }
        }
    }

    //
    public static void main(String[] args) {     
        // 1  2  3  4  5  6  7
        int[][] adjMatrix = { {0, 1, 1, 0, 0, 0, 0},
                              {1, 0, 0, 1, 1, 1, 0},
                              {1, 0, 0, 0, 0, 0, 1},
                              {0, 1, 0, 0, 0, 0, 1},
                              {0, 1, 0, 0, 0, 0, 1},
                              {0, 1, 0, 0, 0, 0 ,0},
                              {0, 0, 1, 1, 1, 0, 0}  };

       new myGraphs(adjMatrix);
     }
}

Solution

If you are looking at Depth First Traversal then following is the code changes you should make

1) First declare your node array as int[] node = {0, 1, 2, 3, 4, 5, 6}. This should be done to avoid array index start (which is 0 ) and your node start number (which is 1). SO here now we assume that new names of your node 1 is 0, node 2 is 1......and node 7 is 6.

2) Instead of doing

for (i = 1; i < node.length-1; i++){
     depthFirst(firstNode, node[i]);
 } 

in myGraphs do : depthFirst(firstNode, 7);

3)In depthFirst instead of for ( i=1;i<=n;i++) use for ( i=0;i<n;i++) While doing System.out.println in function depthFirst add one to the number as 0 represents node 1, 1 represents node 2 and so on.

Below is your fully functional code I modified :

import java.util.Stack;


public class DFS {

    Stack<Integer> st;
      int vFirst;

      int[][] adjMatrix;
      int[] isVisited = new int[7];

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[][] adjMatrix = { {0, 1, 1, 0, 0, 0, 0},
                {1, 0, 0, 1, 1, 1, 0},
                {1, 0, 0, 0, 0, 0, 1},
                {0, 1, 0, 0, 0, 0, 1},
                {0, 1, 0, 0, 0, 0, 1},
                {0, 1, 0, 0, 0, 0 ,0},
                {0, 0, 1, 1, 1, 0, 0}  };


      new DFS(adjMatrix);

    }

    public DFS(int[][] Matrix) {

         this.adjMatrix = Matrix;
         st = new Stack<Integer>();
         int i;
         int[] node = {0, 1, 2, 3, 4, 5, 6};
         int firstNode = node[0];
         depthFirst(firstNode, 7);



          }

          public void depthFirst(int vFirst,int n)
          {
          int v,i;

          st.push(vFirst);

          while(!st.isEmpty())
          {
              v = st.pop();
              if(isVisited[v]==0)
              {
                  System.out.print("\n"+(v+1));
                  isVisited[v]=1;
              }
              for ( i=0;i<n;i++)
              {
                  if((adjMatrix[v][i] == 1) && (isVisited[i] == 0))
                  {
                      st.push(v);
                      isVisited[i]=1;
                      System.out.print(" " + (i+1));
                      v = i;
                  }
              }
          }
}}