この時点で、無限ループ (stackoverflow エラーが発生) の原因を突き止めようとして、私は少し頭がおかしくなっています。グラフ内のサイクルを検出するために、修正された DFS を実装しようとしています。11 ページのこの例に取り組んでいます: http://www.cs.berkeley.edu/~kamil/teaching/sp03/041403.pdf
この実装では、0 = 白、1 = グレー、2 = 黒です。比較的単純なものが欠けていることを願っています。
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;
}