如何判断一个图是否存在环？

Question

如何判断一个图是否存在环？

5

我知道这个问题已经在本论坛和互联网上被问了很多次。但在你们用利爪攻击我之前，请先忍耐一下。

我是一个学习图形的新手。作为我的练习，我需要在这里的Graph类中添加一个hasCycle()方法，链接如下： http://homepage.cs.uiowa.edu/~sriram/21/fall05/ExamplePrograms/ReaderFiles/Chap13/dfs/dfs.java。

我的方法是，在这个论坛中建议的那样进行深度优先搜索，链接如下：Finding a cycle in an undirected graph vs finding one in a directed 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()。

如果您能指出我哪里出错了，将不胜感激。

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

- as3rdaccount

我不明白为什么你的代码会无限递归：在调用hasCycle(i)之前，你总是将vertexList[i].wasVisited设置为true；如果vertexList[i].wasVisited为true，你永远不会调用hasCycle(i)；而且一旦vertexList[i].wasVisited为true，你就永远不会将其设置为false。因此，虽然你的方法存在问题（特别是：除非vertexList[start]本身是循环的一部分，否则它将始终返回false），并且可能需要很长时间，但我认为它不应该具有无限递归。你为什么说它会无限递归呢？ - ruakh

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Turix · Accepted Answer

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

您需要检查从递归调用 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;
}