如何查找图表是否有周期？

Question

我知道这个问题在这个论坛和互联网上的其他地方都被多次询问过.但在你用爪子伸出来攻击我之前,请耐心等待.

我是一个新手学习图.作为我的练习的一部分,我在这里给你在Graph类中添加一个方法hasCycle() http://homepage.cs.uiowa.edu/~sriram/21/fall05/ExamplePrograms/ReaderFiles/Chap13/dfs/dfs.java.

我的方法,按照此论坛中的建议执行DFS.在无向图中查找循环与在有向图中查找一个循环.

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

Answer 1

注意:这个答案假设图是无向的(换句话说,邻接矩阵是对称的).对于有向图,答案更复杂.

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