java - 深度优先搜索导致 StackOverFlowError

Question

我有一个作业，我必须创建通过有向图运行深度优先搜索，并将遍历作为链接列表返回。我相信 DFS 的代码是正确的，因为它似乎与教科书相符，并且当我逐步完成这些步骤时，它是有意义的。如果我在每个顶点被标记时将其打印出来，它会让打印机一遍又一遍地导致堆栈溢出错误。

 private static boolean[] marked;
 private static LinkedList<Integer> ret;

 public static LinkedList<Integer> dfs(Digraph g, int s) {

     marked = new boolean[g.V()];

    ret = new LinkedList<>();

    marked[s] = true;
    System.out.print(s);

    ret.add(s);



   for (int i : g.adj(s)) {
       if (!marked[i]) {
          dfs(g, i);

     }
   }

   return ret;
  }

我的猜测是每次我调用 dfs 时标记的 boolean[] 都会重置。我尝试将其放在方法之外，但因为该方法是静态的并且我无法更改它(给定赋值参数)，所以我遇到了静态非静态问题，我不太确定如何修复。

Answer 1

是的，你的问题确实是因为 boolean 值在某种意义上被重置了。重置发生在这一行:

marked = new boolean[g.V()];

在这一行中，您将在新函数调用中创建一个新的 boolean 数组，该数组与原始数组不同。然后您将检查新数组，其中不包含旧数组的更改。

我建议您创建一个包装函数来初始化 dfs 进程，然后将数组传递到 dfs 函数的每次调用中。

如果您不想添加额外的参数，只需在方法外部创建一个静态变量即可:

private static boolean[] marked;

然后在适当的时候初始化它