Почему я получаю StackOverFlowError при попытке DFS на этом графике найти сильно связанный компонент? - PullRequest
Новая
       42

Почему я получаю StackOverFlowError при попытке DFS на этом графике найти сильно связанный компонент?

0 голосов
/ 12 мая 2018

Я пытаюсь написать алгоритм, который определяет, является ли граф сильно связанным или нет. Я думаю, что мой код почти правильный, хотя я продолжаю получать StackOverFlowError. Я лично думаю, что из-за цикла в графе, с которым я тестирую свой алгоритм, мой код этого не понимает и зацикливается. Но я использую массив, чтобы увидеть, был ли узел уже посещен! Так что этого не должно случиться! Пожалуйста, помогите мне понять, что не так с моим кодом. В любом случае это мой код: 

 static void dfs(int src,boolean[] visited,Stack<Integer> stack){
        visited[src]=true;
        for(Integer i:adj[src]){
            if(!visited[i]){
                dfs(i,visited,stack);
            }
        }
        stack.push(src);
    }

Вот так я и назвал свою функцию DFS из main: 

Stack<Integer> stack=new Stack<Integer>();
    boolean[] visited=new boolean[n+1];
    for(int i=1;i<=n;i++){
        if(!visited[i]){
            g.dfs(i,visited,stack);
        }
    }

1 Ответ

0 голосов
/ 12 мая 2018

Есть два возможных объяснения:

  1. Есть цикл, и ваш код обнаружения цикла не работает.
  2. График слишком глубокий;т. е. ваш код работал бы, если бы стек был больше.

Глядя на ваш код, я думаю, что второе объяснение правильное.

Пример: предположим, что ваш граф на самом делецепочка из N узлов в линии.Чтобы добраться до последнего узла в списке, вам нужно совершать рекурсивные вызовы N на глубину.Для достаточно большого N это приведет к переполнению стека.

...