Java - Adjacency Matrix and DFS

Question

I've been working on a program to implement a DFS in Java (by taking an adjacency matrix as input from a file). Basically, assuming vertices are traveled in numerical order, I would like to print the order that vertices become dead ends, the number of connected components in the graph, the tree edges and the back edges. But I'm not completely there yet. When I run my program, I get the number "1" as output, and nothing more. I've tried debugging certain parts of the DFS class, but I still can't quite figure out where I'm going wrong. Here is my code:

A basic "Driver" class:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Driver {

public static void main(String[] args) throws FileNotFoundException {
    Scanner scanner = new Scanner(new File("sample1.txt"));
    scanner.useDelimiter("[\\s,]+");

    int input = scanner.nextInt();
    int[][] adjMatrix = new int[8][8];

    for(int i=0; i < input; i++) {
        for (int j=0; j < input; j++) {
             adjMatrix[i][j] = scanner.nextInt();
        }
    }
    scanner.close();

    new DFS(adjMatrix);

}

}

DFS class:

import java.util.Stack;

public class DFS {
Stack<Integer> stack;
int first;
int[][] adjMatrix;
int[] visited = new int[7];

public DFS(int[][] Matrix) {

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

public void depthFirstSearch(int first,int n){
     int v,i;

     stack.push(first);

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

And the matrix from the input file looks like this:

0 1 0 0 1 1 0 0
1 0 0 0 0 1 1 0
0 0 0 1 0 0 1 0
0 0 1 0 0 0 0 1
1 0 0 0 0 1 0 0
1 1 0 0 1 0 0 0
0 1 1 0 0 0 0 1
0 0 0 1 0 0 1 0

janos janos · Accepted Answer · 2018-03-19T19:08:08

Take a look at this part:

int input = scanner.nextInt();
int[][] adjMatrix = new int[8][8];

for(int i=0; i < input; i++) {
    for (int j=0; j < input; j++) {
         adjMatrix[i][j] = scanner.nextInt();
    }
}

First you read a number, input. Then you read input rows, in each row input columns.

This is your input data:

0 1 0 0 1 1 0 0
1 0 0 0 0 1 1 0
0 0 0 1 0 0 1 0
0 0 1 0 0 0 0 1
1 0 0 0 0 1 0 0
1 1 0 0 1 0 0 0
0 1 1 0 0 0 0 1
0 0 0 1 0 0 1 0

What is the first number, that will be read by scanner.nextInt(). It's 0. So the loop will do nothing.

Prepend the number 8 to your input, that is:

8
0 1 0 0 1 1 0 0
1 0 0 0 0 1 1 0
0 0 0 1 0 0 1 0
0 0 1 0 0 0 0 1
1 0 0 0 0 1 0 0
1 1 0 0 1 0 0 0
0 1 1 0 0 0 0 1
0 0 0 1 0 0 1 0

Btw, it's a good idea to verify that you have correctly read the matrix. Here's an easy way to do that:

for (int[] row : adjMatrix) {
    System.out.println(Arrays.toString(row));
}

There are several other issues in this implementation:

The number 7 appears in a couple of places. It's actually a crucial value in the depth-first-search algorithm, and it's actually incorrect. It should be 8. And it should not be hardcoded, it should be derived from the size of the matrix.
It's not a good practice to do computation in a constructor. The purpose of a constructor is to create an object. The depth-first-logic could be moved to a static utility method, there's nothing in the current code to warrant a dedicated class.

Fixing the above issues, and a few minor ones too, the implementation can be written a bit simpler and cleaner:

public static void dfs(int[][] matrix) {
    boolean[] visited = new boolean[matrix.length];

    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0);

    while (!stack.isEmpty()) {
        int v = stack.pop();
        if (!visited[v]) {
            System.out.print("\n" + (v + 1));
            visited[v] = true;
        }
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[v][i] == 1 && !visited[i]) {
                visited[i] = true;
                stack.push(v);
                v = i;
                System.out.print(" " + (i + 1));
            }
        }
    }
}

Java - Adjacency Matrix and DFS

1 Answers