0

I need to count a number of bridges in graph, but when I put a test with over 100000 vertexes I randomly get a stackoverflow, sometimes I get a right result and sometimes I get stackoverflow. What does go wrong? (lane 9, to= j.next)

public int findBridgeshelp(int v, int p, boolean[] used, int[] tin, int[] fup, int timer){
    used[v] = true;
    tin[v] = fup[v] = timer++;
    Iterator<Integer> j = lists[v].iterator();
    int count=0;
    for (int i=0; i<lists[v].size(); ++i) {
        int to=0;
        if(j.hasNext())
            to= j.next();
        if (to == p)  continue;
        if (used[to])
            fup[v] = Math.min(fup[v], tin[to]);
        else {
            count=count+ findBridgeshelp(to, v, used, tin, fup, timer);
            fup[v] = Math.min(fup[v], fup[to]);
            if (fup[to] > tin[v])
                count++;
        }
    }
    return count;
}
9
  • 1
    You have a recursive function, maybe you're getting an infinite recursion. You need to debug your code. Or rewrite it in non-recursive manner. Commented Mar 5, 2018 at 19:04
  • Do you need to do this recursively? Commented Mar 5, 2018 at 19:05
  • @Brian That's palliative. Not a duplicate. Commented Mar 5, 2018 at 19:05
  • @lexicore If the code sometimes returns and sometimes does not, then it's very likely that it's just a stack memory error, which is exactly what a StackOverflowError is. Given that the testing fails periodically with a very large number of vertices, but assumably not less, this is even more likely. Commented Mar 5, 2018 at 19:06
  • @Brian I do not think the problem is the small stack. I think the problem is in the code. You write "just a stack memory error" as it would excuse the code. Commented Mar 5, 2018 at 19:10

0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.