Detect cycle in undirected graph

Question

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

• Juho: Could you maybe make your code example fully self-contained? For instance, I wonder what the data structure representing a graph looks like.

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.