DFS подвергается переполнению стека при поиске моста в графе - PullRequest
Новая
       35

DFS подвергается переполнению стека при поиске моста в графе

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

Мой DFS подвергается переполнению стека при поиске моста на графике.В этом вопросе мне предоставлены ребра вместе с их идентификаторами в графе, имеющем вершины (от 1 до n).Мне нужно выяснить, является ли ребро, связанное с данным идентификатором (q запросов), мостом или нет.Пожалуйста, помогите мне понять, что не так с моим кодом: 

import java.util.*;

class TestClass {

static int time=0;
static class pair{
    int v,id;
    pair(int v,int id){
        this.v=v;
        this.id=id;
    }
}

static class graph{
    static int v;
    static ArrayList<pair>[] adj;
     graph(int v){
         this.v=v;
         adj=new ArrayList[v+1];
         for(int i=1;i<=v;i++)
            adj[i]=new ArrayList<pair>();
     }

    static void addedge(int u,int v,int id){
        adj[u].add(new pair(v,id));
        adj[v].add(new pair(u,id));
    }
}
    static void dfs(graph g,int[] disc,int[] low,int[] parent,boolean[] visited,boolean[] bridge,int src){
        visited[src]=true;
        disc[src]=low[src]=++time;

        for(pair p:g.adj[src]){
            int i=p.v;
            int id=p.id;

            if(!visited[i]){
                //System.out.println(i);
                parent[i]=src;
                dfs(g,disc,low,parent,visited,bridge,i);
                low[src]=Math.min(low[src],low[i]);
                if(low[i]>disc[src]){
                    bridge[id]=true;
                }
            }
            else if(parent[src]!=i){
                low[src]=Math.min(low[src],disc[i]);
            }
        }
    }

public static void main(String args[] ) throws Exception {
    Scanner input=new Scanner(System.in);
    int n=input.nextInt();
    int m=input.nextInt();
    int q=input.nextInt();
    graph g=new graph(n);
    for(int i=0;i<m;i++){
        int u=input.nextInt();
        int v=input.nextInt();
        int id=input.nextInt();
        g.addedge(u,v,id);
    }

    int[] disc=new int[n+1];
    int[] parent=new int[n+1];
    int[] low=new int[n+1];
    boolean[] visited=new boolean[n+1];
    boolean[] bridge=new boolean[m+1];

    for(int i=1;i<=n;i++){
        if(!visited[i]){
            parent[i]=-1;
            dfs(g,disc,low,parent,visited,bridge,i);
        }
    }

    while(q-->0){
        int i=input.nextInt();
        if(bridge[i])
           System.out.println("YES");
        else
           System.out.println("no");
    }
}
}

1 Ответ

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

Пожалуйста, помогите мне понять, что не так с моим кодом

Слишком много кода, чтобы я мог прочитать ... и проанализировать ваши намерения.

A StackOverflowError обычно возникает, когда рекурсивный алгоритм слишком глубоко рекурсирует и заполняет стек Например: 

// This is a recursive infinite loop.  It will throw SOE
public void callMe() {
    callMe();
}

// This is a finite loop but it may throw SOE if 'n' is too big 
// or if it is negative
public void countDown(int n) {
    if (n != 0) {
        countDown(n - 1);
    }
}

Это общая идея ...

Чтобы найти причину проблемы в вашем коде:

  1. Изучите трассировку стека. Это скажет вам, какие методы и какие строки кода задействованы в глубокой рекурсии.

  2. Изучите код и посмотрите, сможете ли вы обнаружить очевидную ошибку.

  3. Запустите код в отладчике вашей IDE. Установите точку останова для ключевого метода (участвующего в рекурсии) и используйте функцию отладчика для отображения локальных переменных, чтобы попытаться понять, что происходит. Метод dfs будет хорошим местом для установки точки останова.

  4. Если 3 не является просветляющим, добавьте в код некоторую печать следов, чтобы помочь вам понять, что происходит. Например, выведите значение src в начале каждого вызова dfs.

...