Below is my code to detect cycle in an undirected graph. Could anyone please review and let me know if I have taken care of all the cases?

The basic idea is to use DFS (non-recursive using stack) and check if already visited vertices are found in the stack.

bool dfsDetectCycle(int vertex, int visited[10]) {
    stack<int> s;

    s.push(vertex);

    while (!s.empty()) {
        int np_vertex = s.top();
        s.pop();
        // visit while poping and check visited
        if (visited[np_vertex]) {
            // if already visited means there is a cycle
            return true;
        }
        visited[np_vertex] = 1;
        cout << np_vertex << "\t";

        // Graph with Adjacency Matrix
        if (!isAdjList) {
            for (int j = 0; j < v; ++j)
                // below !visited[j] is needed to exclude previously visited vertices as well as to exclude parent node of currently in progress vertex
                if (adjMatrix[np_vertex][j] && !visited[j]) {
                    s.push(j);
                }
        }
        // Graph with Adjacency List
        else {
            vector<int>::iterator it = adjList[np_vertex].begin();
            for (; it != adjList[np_vertex].end(); ++it)
                if (!visited[*it])
                    s.push(*it);
        }
    }
    return false;
}

bool hasCycle() {
    if (empty())
        return false;
    int visited[10] = {0};
    for (int i = 0; i < v; ++i) {
        if (!visited[i]) {
            if (dfsDetectCycle(i, visited))
                return true;
        }
    }
    return false;
}
  • Could you maybe make your code example fully self-contained? For instance, I wonder what the data structure representing a graph looks like. – Juho Apr 13 '16 at 16:16
up vote 2 down vote accepted

I think your implementation of the logic is fine. But the variable "isAdjList" should be defined for each of the graph for which you are going to detect cycles . Make sure that you have either an adjacent list or an adjacent matrix for a particular graph and not both.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.