如何查找图形是否具有循环？ [英] How to find if a graph has a cycle?

问题描述

我知道这个问题已经在这个论坛以及互联网上的其他地方问过很多次了。但是在您张开双爪攻击我之前，请先忍受我。

我是一个新手学习图。作为练习的一部分，我被允许在Graph类中添加方法hasCycle（）在这里
http://homepage.cs.uiowa.edu/~sriram/21/fall05/ExamplePrograms/ReaderFiles/Chap13/dfs/dfs.java 。

我的方法，按照本论坛此处在无向图中找到一个循环与在有向图中找到一个循环。 p>

但是我在第一个链接中如何使用现有的dfs方法来实现这一目标。

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

  public boolean hasCycle（int start）
 {
 vertexList [start] .wasVisited =真正; 
 for（int j = 0; j< MAX_VERTS; j ++）
 {
 if（adjMat [start] [j] == 1&& vertexList [j] .wasVisited = = true）
返回true; 
 else if（adjMat [start] [j] == 1&& vertexList [j] .wasVisited == false）
 {
 vertexList [start] .wasVisited == true; 
 hasCycle（j）; 
} 
} 
返回false； 
} 
  

我在这里遇到两个问题：
首先，我陷入了困境当我在DFSApp类中调用hasCycle（）而不是
theGraph.dfs（）行时进行无限递归；
其次，我没有使用作业所要求的dfs（）。

任何朝着正确道路前进的方向都可以被我理解在这里做错了。

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

解决方案

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

您需要检查从递归调用 hasCycle（ j）。例如：

 如果（hasCycle（j））
返回true； 
  

如果您确实打了一个周期并返回true，则将展开堆栈

此外，尽管这只是一个小问题，并且不会真正影响功能，但递归调用之前的行hasCycle（ j）有两个问题。首先，它应该是单个等号而不是双。其次，它实际上是多余的，因为对 hasCycle（j）的递归调用中发生的第一件事是节点 j



请记住，这是您的代码的简化：

 布尔布尔值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）））
返回true； 
} 
返回false； 
} 
  





---

@mehrmoudi的评论：

哇。上面的说法不太正确！抱歉！！在下面的修复程序中，我添加了 parent 参数。

  public布尔值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）））
返回true; 
} 
返回false； 
} 
  

I know this question has been asked many times in this forum and everywhere else in the internet. But before you attack me with your claws outstretched please bear with me.

I am a newbie learning graph. As part of my excercise I am given to add a method hasCycle() in the Graph class here http://homepage.cs.uiowa.edu/~sriram/21/fall05/ExamplePrograms/ReaderFiles/Chap13/dfs/dfs.java.

My approach, doing a DFS as suggested in this forum here Finding a cycle in an undirected graph vs finding one in a directed graph.

But I am struggling how to implement this using the existing dfs method in the first link.

My approach so far has been:

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;
}

I have two problems here: First I am stuck into an infinite recursion when I call hasCycle() in the DFSApp class instead of the line theGraph.dfs(); Second I am not using the given dfs() as reuired by my homework.

Any direction to the right path would be appreciated in terms of what I am doing wrong here.

For now I am just concentrating on implementing a correct separate hasCycle() method without using dfs().

解决方案

Note: this answer assumes that the graph is undirected (put another way, the adjacency matrix is symmetric). For a directed graph, the answer is more complex.

You need to check the value returned from the recursive call to hasCycle(j). For example:

if (hasCycle(j))
    return true;

This will "unwind the stack" if you do hit a cycle and return true's all the way to the top level.

Also, although this is a minor point and doesn't really affect the functionality, the line before your recursive call to hasCycle(j) has a couple problems. First, it should be a single equals sign there instead of a double. Second, it is actually redundant because the first thing that will happen in the recursive call to hasCycle(j) is that node j will be marked as visited.

With that in mind, here's a simplification of your code:

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;
}

---

Edited after @mehrmoudi's comment:

Wow. The above wasn't quite right! Sorry!! In the fix below, I added the parent parameter.

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;
}

这篇关于如何查找图形是否具有循环？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！