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

Answer 1

A working/tested solution in C#, if someone looking for it.

using System;
using System.Collections.Generic;

namespace GraphAdjMatrixDemo
{
    public class Program
    {
        public static void Main(string[] args)
        {
            // 0  1  2  3  4  5  6
            int[,] matrix = {     {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}  };

            bool[] visitMatrix = new bool[matrix.GetLength(0)];
            Program ghDemo = new Program();

            for (int lpRCnt = 0; lpRCnt < matrix.GetLength(0); lpRCnt++)
            {
                for (int lpCCnt = 0; lpCCnt < matrix.GetLength(1); lpCCnt++)
                {
                    Console.Write(string.Format(" {0}  ", matrix[lpRCnt, lpCCnt]));
                }
                Console.WriteLine();
            }

            Console.Write("\nDFS Recursive : ");
            ghDemo.DftRecursive(matrix, visitMatrix, 0);
            Console.Write("\nDFS Iterative : ");
            ghDemo.DftIterative(matrix, 0);

            Console.Read();
        }

        //====================================================================================================================================

        public void DftRecursive(int[,] srcMatrix, bool[] visitMatrix, int vertex)
        {
            visitMatrix[vertex] = true;
            Console.Write(vertex + 1 + "  ");

            for (int neighbour = 0; neighbour < srcMatrix.GetLength(0); neighbour++)
            {
                if (visitMatrix[neighbour] == false && srcMatrix[vertex, neighbour] == 1)
                {
                    DftRecursive(srcMatrix, visitMatrix, neighbour);
                }
            }
        }

        public void DftIterative(int[,] srcMatrix, int srcVertex)
        {
            bool[] visited = new bool[srcMatrix.GetLength(0)];

            Stack<int> vertexStack = new Stack<int>();
            vertexStack.Push(srcVertex);

            while (vertexStack.Count > 0)
            {
                int vertex = vertexStack.Pop();

                if (visited[vertex] == true)
                    continue;

                Console.Write(vertex + 1 + "  ");
                visited[vertex] = true;

                for (int neighbour = 0; neighbour < srcMatrix.GetLength(0); neighbour++) 
                //for (int neighbour = srcMatrix.GetLength(0) - 1; neighbour >= 0; neighbour--)// To make same as recursive
                {
                    if (srcMatrix[vertex, neighbour] == 1 && visited[neighbour] == false)
                    {
                        vertexStack.Push(neighbour);
                    }
                }
            }
        }
    }
}

To make display order of iterative same as recursion, we need to push neighbors in reverse order to stack. Took this logic from Amit answer here

Answer 2

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