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;


    while (!s.empty()) {
        int np_vertex = s.top();
        // 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]) {
        // Graph with Adjacency List
        else {
            vector<int>::iterator it = adjList[np_vertex].begin();
            for (; it != adjList[np_vertex].end(); ++it)
                if (!visited[*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;
  • \$\begingroup\$ Could you maybe make your code example fully self-contained? For instance, I wonder what the data structure representing a graph looks like. \$\endgroup\$
    – Juho
    Commented Apr 13, 2016 at 16:16

1 Answer 1


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 agree to our terms of service and acknowledge you have read our privacy policy.

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