patterncppMinor
Detect cycle in undirected graph
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.
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.