如何判断一个图是否有环？

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

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

我的方法是按照本论坛的建议进行 DFS在无向图中查找循环与在有向图中查找循环 https://stackoverflow.com/questions/10972028/finding-a-cycle-in-an-undirected-graph-vs-finding-one-in-a-directed-graph?rq=1.

但我正在努力如何使用第一个链接中现有的 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() 。

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

现在我只是专注于实现一个正确的单独的 hasCycle() 方法，而不使用 dfs()。

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

您需要检查递归调用返回的值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;
}