HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Detect cycle in undirected graph

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
cycleundirectedgraphdetect

Problem

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

Solution

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.

Context

StackExchange Code Review Q#125512, answer score: 2

Revisions (0)

No revisions yet.