我有一个 DFS 访问递归方​​法，有时会抛出 StackOverflowError。由于图的大小很大(大约 20000 个顶点)，递归调用很多，所以我尝试使用 -Xss10M 运行并且一切正常。 我只是想了解为什么在方法的开头添加 System.out.println，即使没有 -Xss10M，该方法也不会抛出任何 StackOverflowError。怎么可能？

这是DFS的访问方式:

private int dfsVisit(Vertex<T> v, int time){
  // System.out.println("Hello");
  Vertex<T> n;
  time++;
  v.d = time;
  v.color = Vertex.Color.GRAY;
  for (Map.Entry<Vertex<T>, Float> a : v.neighbours.entrySet()){
     n = a.getKey();
     if(n.color == Vertex.Color.WHITE){
        n.previous = v;
        time = dfsVisit(n, time);
     }
  }
  v.color = Vertex.Color.BLACK;
  time++;
  v.f = time;

  return time;
}

这是完整的代码

import java.io.*;
import java.util.*;

class Graph<T> {
   private final Map<T, Vertex<T>> graph; 

   public static class Edge<T>{
      public final T v1, v2;
      public final float dist;

      public Edge(T v1, T v2, float dist) {
         this.v1 = v1;
         this.v2 = v2;
         this.dist = dist;
      }
   }

   public static class Vertex<T> implements Comparable<Vertex>{ // SPOSTARE VAR IST NEL COSTRUTTORE
      public enum Color {WHITE, GRAY, BLACK, UNKNOWN};
      public final T name;
      public float dist;
      public Vertex<T> previous;
      public final Map<Vertex<T>, Float> neighbours;
      public Color color;
      public int d, f;

      public Vertex(T name) {
         this.name = name;
         dist = Float.MAX_VALUE; 
         previous = null;
         neighbours = new HashMap<Vertex<T>, Float>(); // adjacency list
         color = Color.UNKNOWN;
         d = 0;
         f = 0;
      }

      private void printPath() {
         if (this == this.previous) { 
            System.out.print(this.name);
         } else if (this.previous == null) {
            System.out.print(this.name + " unreached");
         } else {
            this.previous.printPath();
            System.out.print(" -> " + this.name + "(" + this.dist + ")");
         }
      }

      public int compareTo(Vertex other){
         if(this.dist == other.dist)
            return 0;
         else if(this.dist > other.dist)
            return 1;
         else
            return -1;
      }

   }

   // Builds a graph from an array of edges 
   public Graph(ArrayList<Graph.Edge> edges) {
      graph = new HashMap<>(edges.size());

      // add vertices
      for (Edge<T> e : edges) {
         if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex<>(e.v1));
         if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex<>(e.v2));
      }

      // create adjacency list
      for (Edge<T> e : edges) {
         graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
         graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); 
      }
   }


   public void dijkstra(T startName) {
      if (!graph.containsKey(startName)) {
         System.err.println("Graph doesn't contain start vertex " + startName);
         return;
      }
      final Vertex<T> source = graph.get(startName);
      NavigableSet<Vertex<T>> q = new TreeSet<>(); // priority queue

      // set-up vertices
      for (Vertex<T> v : graph.values()) {
         v.previous = v == source ? source : null;
         v.dist = v == source ? 0 : Float.MAX_VALUE;
         q.add(v);
      }

      dijkstra(q);
   }

   private void dijkstra(final NavigableSet<Vertex<T>> q) {      
      Vertex<T> u, v;
      while (!q.isEmpty()) {

         u = q.pollFirst();
         if (u.dist == Float.MAX_VALUE) break; //???????????


         for (Map.Entry<Vertex<T>, Float> a : u.neighbours.entrySet()) {
            v = a.getKey(); 

            final float alternateDist = u.dist + a.getValue();
            if (alternateDist < v.dist) { 
               q.remove(v);
               v.dist = alternateDist;
               v.previous = u;
               q.add(v);
            } 
         }
      }
   }


   public void printPath(T endName) {
      if (!graph.containsKey(endName)) {
         System.err.println("Graph doesn't contain end vertex " + "\"" + endName + "\"" );
         return;
      }

      graph.get(endName).printPath();
      System.out.println();
   }

   public void printAllPaths() {
      for (Vertex<T> v : graph.values()) {
         v.printPath();
         System.out.println();
      }
   }

   public Vertex<T> getVertex(T key){
      if(graph.containsKey(key))
         return graph.get(key);
      return null;
   }

   public void printAdjacencyList(){
      System.out.println("Adjacency list:");
      for(Vertex<T> v : graph.values()){
         System.out.print(v.name + ":\t");
         for (Map.Entry<Vertex<T>, Float> a : v.neighbours.entrySet()){
             System.out.print(a.getKey().name + "(" + a.getValue() + ") | ");
         }
         System.out.println();
      }

   }
   /*
   P.S. I know that if only used to calculate the connected components of the graph, dfs visit 
   could be written differently but I preferred to write it in a more general way, so that it 
   can be reused if necessary.
   */
   private int dfsVisit(Vertex<T> v, int time){
     // System.out.println("ciao");
      Vertex<T> n;
      time++;
      v.d = time;
      v.color = Vertex.Color.GRAY;
      for (Map.Entry<Vertex<T>, Float> a : v.neighbours.entrySet()){
         n = a.getKey();
         if(n.color == Vertex.Color.WHITE){
            n.previous = v;
            time = dfsVisit(n, time);
         }
      }
      v.color = Vertex.Color.BLACK;
      time++;
      v.f = time;

      return time;
   }

   /*
   Print the size of the connected components of the graph
   */
   public void connectedComponents(){
      for(Vertex<T> v : graph.values()){
         v.color = Vertex.Color.WHITE;
         v.previous = null;
      }

      for(Vertex<T> v : graph.values()){
         if(v.color == Vertex.Color.WHITE)
             System.out.println(dfsVisit(v, 0)/2);
      }

   }



}

这是测试类

import java.io.*;
import java.util.*;

public class Dijkstra {

   private static ArrayList<Graph.Edge> a = new ArrayList<Graph.Edge>();
   private static final String START = "torino";
   private static final String END = "catania";

   public static void main(String[] args) {
      String fileName = "italian_dist_graph.txt";
      try{
         Scanner inputStream = new Scanner(new File(fileName));
         String record;
         while(inputStream.hasNextLine()){
            record = inputStream.nextLine();
            String[] array = record.split(",");
            String from = array[0];
            String to = array[1];
            float dist = Float.parseFloat(array[2]);
            a.add(new Graph.Edge(from, to, dist));
         }
         inputStream.close();
      } catch(FileNotFoundException e){
         System.out.println("Impossibile trovare il file "+fileName);
      }



      Graph<String> g = new Graph<String>(a);

      g.dijkstra(START);
      g.printPath(END);
     //System.out.printf("%f\n", g.getVertex(END).dist/1000.0f);
      g.connectedComponents();
   }
}

注意尝试评论 g.dijkstra(START) 和 g.printPath(END)；一切似乎都正常。

这是数据集的链接

https://drive.google.com/open?id=0B7XZY8cd0L_fZVl1aERlRmhQN0k

最佳答案

一些一般性建议:
您的代码混合了顶点的属性，这些属性与 dfs 的单次运行相关，并且是顶点的直接属性。 坏坏坏风格。这很可能会破坏任何更复杂的算法，可能会产生意外行为，并且需要在每次运行后清除状态，以确保代码的稳定性。相反，保持与算法的单次运行相关的状态仅对该函数可见。例如。将状态存储在 Map 中，使用装饰器模式创建提供附加属性并具有方法局部作用域等的数据结构。例如:在同一个图上运行代码两次(相同的 Object)具有相同的输入而不清除所有状态将导致错误的结果 (1)。

此外:创建 DFS 的迭代版本并不难，所以您应该尝试一下，特别是因为您的图形看起来非常大。

至于为什么您的代码以其方式工作(或不工作):
这很难说，因为它取决于很多因素。您没有提供完整的代码，所以我无法重新运行任何测试，也无法验证一切是否按预期方式运行。最可能的答案:

Vertex 使用 Object 提供的默认哈希码。这导致邻居 map 中条目的随机排序，因此特定路径的遍历顺序在每次运行中都是随机的，并且很可能不同。因此，您正在使用随机路径遍历图形，每次运行很可能(特别是由于图形的大小)不同。原因不是 System.out.println，而是一个事实，即您的代码每次运行时都会生成不同的结构(来自排序 POV，而不是数学)，加上巧合，由于某些非常奇怪的原因，图表的每次构建都没有达到 StackOverflow 所需的递归深度，并且使用 System.out.println 编译的代码一起出现。

Java 编译器或 JIT 以一种奇怪的方式修改代码的行为。现代编译器倾向于生成非常奇怪的代码，以尝试优化他们可以推迟的所有内容。

关于java - 运行深度优先搜索时出现 StackOverflowError(无向图)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37489743/