How to find if a graph has a cycle?

Question

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().

Answer 1

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