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

Answer 1

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

• user7939273: Thanks for the suggestions. If I wanted to edit my code without prepending the size into my file, what should I use? I tried using int[][] adjMatrix = new int[input][input] before, but kept getting an ArrayIndexOutofBounds Exception.
• janos: @GarrettMcClure if you don't want to edit the input file, then instead of int input = scanner.nextInt(); you can hardcode the count int input = 8;. Let me know if you need more help.
• user7939273: That fixed my exception, but my output is 1 2 6 7 5. For first-encountered, it should be 1 2 6 7 4 3 5 8.
• janos: @GarrettMcClure If I understood the logic correctly, it should be 1 2 6 7 8 3 4 5. And you need to fix two things to get there. It should be int[] visited = new int[8]; and depthFirstSearch(firstNode, 8);. Let me know if you need more help.
• janos: @GarrettMcClure I updated my post with a simplified implementation that also corrects some important problems in the original