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