Java

Question

我一直在研究在 Java 中实现 DFS 的程序（通过将邻接矩阵作为文件的输入）。基本上，假设顶点按数字顺序移动，我想打印顶点成为死胡同的顺序、图中连通分量的数量、树边和后边。但我还没有完全在那里。当我运行我的程序时，我得到数字“1”作为输出，仅此而已。我试过调试 DFS class 的某些部分，但我仍然不太清楚哪里出错了。这是我的代码：

基础"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;
             }
         }
     }
}
}

输入文件中的矩阵如下所示：

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

看看这部分：

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

首先你读了一个数字，input。然后你阅读 input 行，每行 input 列。

这是您的输入数据：

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

第一个数字是多少，scanner.nextInt() 将读取它。它是 0。所以循环什么都不做。

在输入前加上数字 8，即：

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

顺便说一句，验证您是否正确阅读了矩阵是个好主意。这是一个简单的方法：

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

此实现中还有其他几个问题：

数字 7 出现在几个地方。它实际上是 depth-first-search 算法中的一个关键值，它实际上是不正确的。应该是8。而且应该不是硬编码的，应该是从矩阵的大小推导出来的。
在构造函数中进行计算不是一个好习惯。构造函数的目的是创建一个对象。 depth-first-logic 可以移动到静态实用程序方法，当前代码中没有任何内容可以保证专用 class.

解决了上述问题，还有一些小问题，实现可以写得更简单、更清晰：

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 - 邻接矩阵和 DFS

Java - Adjacency Matrix and DFS

depth-first-search

adjacency-matrix