Java 如何判断一个图是否有环？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19650950/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to find if a graph has a cycle?
提问by as3rdaccount
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.
我是新手学习图。作为我练习的一部分，我被要求在 Graph 类中添加一个方法 hasCycle() 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.
我的方法，按照本论坛中的建议进行 DFS 此处Find a cycle in an undirected graph vs find one in a direct graph。
But I am struggling how to implement this using the existing dfs method in the first link.
但是我正在努力如何使用第一个链接中现有的 dfs 方法来实现这一点。
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.
我在这里有两个问题：首先，当我在 DFSApp 类中调用 hasCycle() 而不是 theGraph.dfs() 行时，我陷入了无限递归；其次，我没有按照作业要求使用给定的 dfs()。
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().
现在我只专注于在不使用 dfs() 的情况下实现正确的单独 hasCycle() 方法。
采纳答案by Turix
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:
您需要检查递归调用返回的值hasCycle(j)。例如：
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.
如果您确实遇到了一个循环并将 true 一直返回到顶层，这将“展开堆栈”。
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 jwill be marked as visited.
此外，虽然这是一个次要的点并且不会真正影响功能，但是在您递归调用之前的行hasCycle(j)有几个问题。首先，它应该是一个等号而不是双等号。其次，它实际上是多余的，因为在递归调用中会发生的第一件事hasCycle(j)是该节点j将被标记为已访问。
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:
在@mehrmoudi 的评论后编辑：
Wow. The above wasn't quite right! Sorry!! In the fix below, I added the parentparameter.
哇。上面说的不太对！对不起！！在下面的修复中，我添加了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;
}
