Java 中大输入的堆栈溢出错误

Question

我正在编写一个 Java 程序，用于搜索并输出图表中的循环。我使用邻接列表来存储我的图形，并将列表存储为 LinkedList。我的程序采用的输入格式为第一行作为图中的节点数，后续每一行有 2 个形成边的节点，例如：

3
1 2
2 3
3 1

我的问题是，当输入变得非常大时（我使用的大图有 10k 个节点，我不知道有多少条边，文件只有 23mb 的边）我得到一个 java.lang .StackOverflowError，但我在小输入时没有收到任何错误。我想知道是否使用其他数据结构来形成邻接列表会更好，或者是否可以使用某种方法来避免此错误，因为我不想只需要更改本地安装的设置Java（因为我必须确保这将在我无法控制设置的其他计算机上运行）。下面是我的代码、Vertex 类和我的主类。感谢您提供的任何帮助！

顶点.java:

package algorithms311;

import java.util.*;

public class Vertex implements Comparable {

    public int id;
    public LinkedList adjVert = new LinkedList();
    public String color = "white";
    public int dTime;
    public int fTime;
    public int prev;

    public Vertex(int idnum) {
        id = idnum;
    }

    public int getId() {
        return id;
    }

    public int compareTo(Object obj) {
        Vertex vert = (Vertex) obj;
        return id-vert.getId();
    }

    @Override public String toString(){
        return "Vertex # " + id;
    }

    public void setColor(String newColor) {
        color = newColor;
    }

    public String getColor() {
        return color;
    }

    public void setDTime(int d) {
        dTime = d;
    }

    public void setFTime(int f) {
        fTime = f;
    }

    public int getDTime() {
        return dTime;
    }

    public int getFTime() {
        return fTime;
    }

    public void setPrev(int v) {
        prev = v;
    }

    public int getPrev() {
        return prev;
    }

    public LinkedList getAdjList() {
        return adjVert;
    }

    public void addAdj(int a) { //adds a vertex id to this vertex's adj list
        adjVert.add(a);
    }
}

CS311.java:

package algorithms311;

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

public class CS311 {

    public static final String GRAPH= "largegraph1";

    public static int time = 0;


    public static LinkedList[] DFS(Vertex[] v) {

        LinkedList[] l = new LinkedList[2];
        l[0] = new LinkedList();
        l[1] = new LinkedList(); //initialize the array with blank lists, otherwise we get a nullpointerexception

        for(int i = 0; i < v.length; i++) {
            v[i].setColor("white");
            v[i].setPrev(-1);
        }
        time = 0;
        for(int i = 0; i < v.length; i++) {
            if(v[i].getColor().equals("white")) {
                l = DFSVisit(v, i, l);
            }
        }
        return l;
    }

    public static LinkedList[] DFSVisit(Vertex[] v, int i, LinkedList[] l) { //params are a vertex of nodes and the node id you want to DFS from

        LinkedList[] VOandBE = new LinkedList[2]; //two lists: visit orders and back edges

        VOandBE[0] = l[0]; // l[0] is visit Order, a linked list of ints

        VOandBE[1] = l[1]; // l[1] is back Edges, a linked list of arrays[2] of ints

        VOandBE[0].add(v[i].getId());

        v[i].setColor("gray");  //color[vertex i] <- GRAY
        time++;                 //time <- time+1
        v[i].setDTime(time);    //d[vertex i] <- time

        LinkedList adjList = v[i].getAdjList(); // adjList for the current vertex

        for(int j = 0; j < adjList.size(); j++) {   //for each v in adj[vertex i]

            if(v[(Integer)adjList.get(j)].getColor().equals("gray") && v[i].getPrev() != v[(Integer)adjList.get(j)].getId()) { //  if color[v] = gray and Predecessor[u] != v do
                int[] edge = new int[2]; //pair of vertices
                edge[0] = i; //from u
                edge[1] = (Integer)adjList.get(j); //to v
                VOandBE[1].add(edge);
            }
            if(v[(Integer)adjList.get(j)].getColor().equals("white")) { //do if color[v] = WHITE
                v[(Integer)adjList.get(j)].setPrev(i);  //then "pi"[v] <- vertex i
                DFSVisit(v, (Integer)adjList.get(j), VOandBE);   //DFS-Visit(v)
            }
        }

        VOandBE[0].add(v[i].getId());

        v[i].setColor("black");
        time++;
        v[i].setFTime(time);

        return VOandBE;
    }


    public static void main(String[] args) {
        try {

            // --Read First Line of Input File
            // --Find Number of Vertices

            FileReader file1 = new FileReader("W:\\Documents\\NetBeansProjects\\algorithms311\\src\\algorithms311\\" + GRAPH);
            BufferedReader bReaderNumEdges = new BufferedReader(file1);

            String numVertS = bReaderNumEdges.readLine();
            int numVert = Integer.parseInt(numVertS);

            System.out.println(numVert + " vertices");





            // --Make Vertices

            Vertex vertex[] = new Vertex[numVert];

            for(int k = 0; k <= numVert - 1; k++) {
                vertex[k] = new Vertex(k);
            }

            // --Adj Lists


            FileReader file2 = new FileReader("W:\\Documents\\NetBeansProjects\\algorithms311\\src\\algorithms311\\" + GRAPH);
            BufferedReader bReaderEdges = new BufferedReader(file2);
            bReaderEdges.readLine(); //skip first line, that's how many vertices there are

            String edge;

            while((edge = bReaderEdges.readLine()) != null) {

                StringTokenizer ST = new StringTokenizer(edge);

                int vArr[] = new int[2];
                for(int j = 0; ST.hasMoreTokens(); j++) {
                    vArr[j] = Integer.parseInt(ST.nextToken());
                }


                vertex[vArr[0]-1].addAdj(vArr[1]-1);
                vertex[vArr[1]-1].addAdj(vArr[0]-1);

            }

            for(int i = 0; i < vertex.length; i++) {
                System.out.println(vertex[i] + ", adj nodes: " + vertex[i].getAdjList());
            }

            LinkedList[] l = new LinkedList[2];
            l = DFS(vertex);

            System.out.println("");
            System.out.println("Visited Nodes: " + l[0]);
            System.out.println("");
            System.out.print("Back Edges: ");

            for(int i = 0; i < l[1].size(); i++) {
                int[] q = (int[])(l[1].get(i));
                System.out.println("[" + q[0] + "," + q[1] + "] ");
            }

            for(int i = 0; i < l[1].size(); i++) { //iterate through the list of back edges
                int[] q = (int[])(l[1].get(i)); // q = pair of vertices that make up a back edge
                int u = q[0]; // edge (u,v)
                int v = q[1];

                LinkedList cycle = new LinkedList();

                if(l[0].indexOf(u) < l[0].indexOf(v)) { //check if u is before v
                    for(int z = l[0].indexOf(u); z <= l[0].indexOf(v); z++) { //if it is, look for u first; from u to v
                        cycle.add(l[0].get(z));
                    }
                }
                else if(l[0].indexOf(v) < l[0].indexOf(u)) {
                    for(int z = l[0].indexOf(v); z <= l[0].indexOf(u); z++) { //if it is, look for u first; from u to v
                        cycle.add(l[0].get(z));
                    }
                }

                System.out.println("");
                System.out.println("Cycle detected! : " + cycle);
                if((cycle.size() & 1) != 0) {
                    System.out.println("Cycle is odd, graph is not 2-colorable!");
                }
                else {
                    System.out.println("Cycle is even, we're okay!");
                }
            }

        }

        catch (IOException e) {
            System.out.println("AHHHH");
            e.printStackTrace();
        }
    }
}

Answer 1

问题很可能是 DFSVisit 中的递归调用。如果您不想采用在调用 JVM 时增加 Java 堆栈大小的“简单”答案，您可能需要考虑重写 DFSVisit 以使用迭代算法而不是递归算法。虽然深度优先搜索更容易以递归方式定义，但可以使用该算法的迭代方法。

例如：这个博客文章

Answer 2

堆栈是内存中的一个区域，用于存储执行上下文和传递参数。每次代码调用一个方法时，都会使用一点堆栈，并且堆栈指针会增加以指向下一个可用位置。当该方法返回时，堆栈指针减少并释放堆栈的一部分。

如果应用程序大量使用递归，堆栈很快就会成为瓶颈，因为如果递归深度没有限制，则所需的堆栈数量也没有限制。因此，您有两个选择：增加 Java 堆栈（-Xss JVM 参数，这只会在您达到新限制之前有所帮助）或更改算法，以便递归深度不那么深。

我不确定您是否在寻找通用答案，但从简要浏览您的代码来看，您的问题似乎是递归。

Answer 3

如果您确定您的算法是正确的并且您所做的递归调用的深度不是偶然的，那么无需更改算法的解决方案是：

• 添加到 JVM 命令行，例如 -Xss128m 以设置 128 MB 堆栈大小（不是在多线程程序中这是一个很好的解决方案，因为它为每个线程设置默认堆栈大小，而不仅仅是运行任务的特定线程）；
• 在自己的线程中运行您的任务，您可以使用特定于该线程的堆栈大小进行初始化（并在程序本身内设置堆栈大小） - 请参阅我在 修复 StackOverflowError，但本质上堆栈大小是 Thread() 构造函数的参数；
• 根本不要使用递归调用——相反，使用显式的 Stack 或 Queue 对象来模拟递归调用（这可以说给了你更多的控制权）。