Как преодолеть проблему переполнения стека при поиске SCC?

Question

Это код, который я написал, чтобы найти SCC, использующие двухпроходный алгоритм Косараджу. Когда я запускаю метод main, я получаю StackOverFlowError в SCC.revDFS. Как избежать ошибки переполнения стека при большом количестве рекурсивных вызовов?

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]);
        }
    }
}

Answer 1

Основная идея преобразования рекурсивной функции в итеративную функцию заключается в том, что рекурсивная функция использует аргументы из стека.

Таким образом, вы можете создать стек и вставить значения в него, а затем использовать их в цикле.

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);
                }
            }

Answer 2

Может быть, вы можете попытаться преобразовать логику в итеративный подход. Кроме того, проверьте, правильно ли обработаны базовый и крайний случаи.

Answer 3

Вы реализовали свою функцию Dfs рекурсивно, что вызывает "переполнение стека". Чтобы преодолеть эту проблему, вам нужно реализовать ее, используя структуру данных стека. см. ссылку ниже для дополнительной мотивации https://github.com/sinamalakouti/MyFavoriteAlgorithmProblems