我一直在开发一个程序来在Java中实现DFS(通过将邻接矩阵作为文件的输入)。基本上，假设顶点按数字顺序行进，我想打印顶点成为死胡同的顺序、图中连接组件的数量、树边和后边缘。但我还没有完全到达那里。当我运行我的程序时，我得到数字"1"作为输出，仅此而已。我已经尝试调试DFS类的某些部分，但我仍然无法弄清楚我出了什么问题。这是我的代码：
一个基本的"驱动程序"类：
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类：
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
看看这部分：
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 出现在几个地方。它实际上是深度优先搜索算法中的一个关键值，它实际上是不正确的。它应该是 8。它不应该是硬编码的，它应该从矩阵的大小派生出来。
- 在构造函数中进行计算不是一个好的做法。构造函数的目的是创建一个对象。深度优先逻辑可以移动到静态实用程序方法，当前代码中没有任何内容可以保证专用类。
修复上述问题以及一些小问题，可以实现更简单、更干净：
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));
}
}
}
}