无限循环堆栈溢出 - 修改后的DFS中的检测周期

我试图确定无限循环的来源（出现stackoverflow错误），在这一点上我有点疯狂。我试图实现一个修改后的DFS来检测图形中的周期。我在第11页的示例中使用了这个示例：http://www.cs.berkeley.edu/~kamil/teaching/sp03/041403.pdf 无限循环堆栈溢出 - 修改后的DFS中的检测周期

在此实现中，0 = WHITE，1 = GRAY，2 = BLACK。我希望我缺少一些相对简单的东西。

public boolean containsCycle() 
{ 
    for (int i=0; i<n; i++) 
    marks[i] = 0; // Initialize all to zero - unvisited 

    for (int i=0; i<n; i++) { // n = number of vertices in the graph 
    if (marks[i]==0) { 
     if (visit(i)){ 
     return true; 
     } 
    } 
    } 
    return false; 
} 

public boolean visit(int index){ 
    marks[index] = 1; // Visited 

    for (int i=0; i<n; i++){ 
     if(isArc(index,i)){ // isArc() returns true IFF there is a directed edge from index-> 
     if (marks[i]==1) 
     return true; 
     } 
     else if (marks[i]==0) { 
     if(visit(marks[i])) 
     return true; 
     } 
    } 
    marks[index] = 2; 
    return false; 
    }

来源

2013-04-24 user2316407

什么是N'的'的价值和它在哪儿来的？ – glenatron 2013-04-24 16:07:15

'n =图中顶点的数量' – AbstractChaos 2013-04-24 16:08:10

n的值是图中顶点的数量。这是由另一个函数决定的，我已经测试并知道返回正确的n。 – user2316407 2013-04-24 16:08:24

看来，这应该是else if (visit(i))代替else if (visit(marks[i]))

来源

2013-04-24 16:29:42

我不能够感谢你！非常感谢。 – user2316407 2013-04-24 16:44:05

无限循环堆栈溢出 - 修改后的DFS中的检测周期

回答

相关问题