5

我知道这个问题在这个论坛和互联网上的其他地方已经被问过很多次了。但在你伸出爪子攻击我之前，请耐心等待。

我是新手学习图。作为我练习的一部分，我可以在此处的 Graph 类中添加一个方法 hasCycle() http://homepage.cs.uiowa.edu/~sriram/21/fall05/ExamplePrograms/ReaderFiles/Chap13/dfs/dfs.java .

我的方法，按照这个论坛中的建议进行 DFS Find a cycle in an undirected graph vs find one in a direct graph。

但我正在努力如何使用第一个链接中现有的 dfs 方法来实现这一点。

到目前为止，我的方法是：

public boolean hasCycle(int start)
{
    vertexList[start].wasVisited = true;
    for(int j = 0; j < MAX_VERTS; j++)
    {  
        if(adjMat[start][j]==1 && vertexList[j].wasVisited==true)
        return true;
        else if(adjMat[start][j]==1 && vertexList[j].wasVisited==false)
        {
         vertexList[start].wasVisited == true;
         hasCycle(j);
        }
    }
   return false;
}

我在这里有两个问题：首先，当我在 DFSApp 类中调用 hasCycle() 而不是 theGraph.dfs() 行时，我陷入了无限递归；其次，我没有像作业所要求的那样使用给定的 dfs() 。

就我在这里做错的事情而言，任何通往正确道路的方向都会受到赞赏。

现在我只专注于在不使用 dfs() 的情况下实现正确的单独 hasCycle() 方法。

4

1 回答 1

10

注意：这个答案假设图是无向的（换句话说，邻接矩阵是对称的）。对于有向图，答案更复杂。

您需要检查从递归调用返回的值hasCycle(j)。例如：

if (hasCycle(j))
    return true;

如果您确实遇到了一个循环并将 true 一直返回到顶层，这将“展开堆栈”。

此外，虽然这是一个小问题并且不会真正影响功能，但递归调用之前的行hasCycle(j)有几个问题。首先，它应该是一个单一的等号而不是一个双等号。其次，它实际上是多余的，因为在递归调用中将发生的第一件事hasCycle(j)是该节点j将被标记为已访问。

考虑到这一点，这里是您的代码的简化：

public boolean hasCycle(int start)
{
    vertexList[start].wasVisited = true;
    for (int j = 0; j < MAX_VERTS; j++) {  
        if (adjMat[start][j] == 1  &&  (vertexList[j].wasVisited  ||  hasCycle(j)))
            return true;
    }
    return false;
}

在@mehrmoudi 发表评论后编辑：

哇。楼上说的不太对！对不起！！在下面的修复中，我添加了parent参数。

public boolean hasCycle(int start, int parent)
{
    vertexList[start].wasVisited = true;
    for (int j = 0; j < MAX_VERTS; j++) {  
        if (j != parent  &&  adjMat[start][j] == 1  &&  (vertexList[j].wasVisited  ||  hasCycle(j, start)))
            return true;
    }
    return false;
}
于 2013-10-29T06:24:57.763 回答