0

这是我编写的使用 Kosaraju 的两次通过算法查找 SCC 的代码。当我运行 main 方法时，我在 SCC.revDFS 上得到一个 StackOverFlowError。有大量递归调用时如何避免堆栈溢出错误？

import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Arrays;
import java.util.Scanner;

public class SCC {
    int n = 875714;
    Map<Integer,List<Integer>> adjList;
    Map<Integer,List<Integer>> adjListRev;
    int[] ft;
    int t;
    int s;
    boolean[] marked;
    int[] leaders;

    public SCC() {
        init();
        t = 0;
        s = 0;
        marked = new boolean[n + 1];
        leaders = new int[n + 1];
    }

    void init() {
        adjList = new HashMap<Integer,List<Integer>>();
        adjListRev = new HashMap<Integer,List<Integer>>();
        ft = new int[n + 1];
        List<Integer> adj;
        try {
            Scanner scanner = new Scanner (new InputStreamReader(this.getClass().
                    getClassLoader().getResourceAsStream("SCC.txt")));
            while(scanner.hasNextLine()) {
                String s = scanner.nextLine().trim();
                String[] num = s.split(" ");
                if (!adjList.containsKey(Integer.parseInt(num[0]))) {
                    adjList.put(Integer.parseInt(num[0]), new ArrayList<Integer>());
                }
                adj = adjList.get(Integer.parseInt(num[0]));
                adj.add(Integer.parseInt(num[1]));
                adjList.put(Integer.parseInt(num[0]), adj);

                if (!adjListRev.containsKey(Integer.parseInt(num[1]))) {
                    adjListRev.put(Integer.parseInt(num[1]), new ArrayList<Integer>());
                }
                adj = adjListRev.get(Integer.parseInt(num[1]));
                adj.add(Integer.parseInt(num[0]));
                adjListRev.put(Integer.parseInt(num[1]), adj);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public void DFS_Loop() {

        for (int i = 1; i < n + 1; i++) {
            marked[i] = false;
        }
        for (int i = n; i > 0; i--) {
            if (!marked[i]) {
                revDFS(i);
            }
        }
        for (int i = 1; i < n + 1; i++) {
            marked[i] = false;
            leaders[i] = 0;
        }
        for (int i = n; i > 0; i--) {
            if (!marked[ft[i]]) {
                s = ft[i];
                DFS(ft[i]);
            }
        }
    }

    public void revDFS(int i) {
        marked[i] = true;
        List<Integer> edges = adjListRev.get(i);
        if (edges != null) {
            for (int j: edges) {
                if (!marked[j]) {
                    revDFS(j);
                }
            }
        }
        t += 1;
        ft[t] = i;
    }

    public void DFS(int i) {
        marked[i] = true;
        leaders[s] += 1;
        List<Integer> edges = adjList.get(i);
        if (edges != null) {
            for (int j: edges) {
                if (!marked[j]) {
                    DFS(j);
                }
            }
        }
    }

    public static void main(String[] args) {
        SCC scc = new SCC();
        scc.DFS_Loop();
        Arrays.sort(scc.leaders);
        for (int i = scc.n; i < scc.n - 5; i--) {
            System.out.println(scc.leaders[i]);
        }
    }
}
4

3 回答 3

0

您已经递归地实现了 Dfs 函数，这会导致“堆栈溢出”。要克服这个问题，您需要使用堆栈数据结构来实现它。有关更多动机，请参见下面的链接 https://github.com/sinamalakouti/MyFavoriteAlgorithmProblems

于 2017-05-29T04:44:16.367 回答
0

也许您可以尝试将逻辑转换为迭代方法。另外，请检查您是否正确处理了基本情况和边缘情况。

于 2017-05-01T22:11:29.603 回答
0

将递归函数转换为迭代函数的基本思想是递归函数使用堆栈中的参数。

因此，您可以创建一个堆栈并将值推入其中，然后循环使用它们。

public void _revDFS(int _i) {
    LinkedList<Integer> stack = new LinkedList<>();
    stack.push(_i);

    while(!stack.isEmpty()){
        int i = stack.pop();
        marked[i] = true;
        List<Integer> edges = adjListRev.get(i);
        if (edges != null) {
            for (int j: edges) {
                if (!marked[j]) {
                    stack.push(j);
                    //revDFS(j);
                }
            }
        }
        t += 1;
        ft[t] = i;
    }
}

我无法真正对其进行测试以查看我是否犯了某种错误并且revDFS是一个具有很多副作用并且它不返回值的函数，因此有点难以理解它。

但要点是，您可以将边缘索引推送到堆栈上，然后使用它们，而不是调用函数本身。

子边缘将以相反的顺序处理，因此如果您想保持与原始边缘相同的处理顺序，您应该以相反的顺序阅读边缘：

            ListIterator<Integer> li = edges.listIterator(edges.size());
            while(li.hasPrevious()){
                int j = li.previous();
                if (!marked[j]) {
                    stack.push(j);
                    //revDFS(j);
                }
            }
于 2017-05-02T00:04:17.143 回答