Detect Cycle In A Graph - C++ solution, Julia studied code and put some comments

DetectCycleInAGraph.cpp

// A C++ Program to detect cycle in a graph
#include<iostream>
#include <list>
#include <limits.h>

using namespace std;

class Graph
{
	int V;												 // No. of vertices
	list<int> *adj;										 // Pointer to an array containing adjacency lists

	bool isCyclicUtil(int v, bool visited[], bool *rs);  // used by isCyclic()

	public:

		Graph(int V);					// Constructor
		void addEdge(int v, int w);		// to add an edge to graph
		bool isCyclic();				// returns true if there is a cycle in this graph
};

Graph::Graph(int V)
{
	this->V = V;
	adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
	adj[v].push_back(w);     // Add w to v’s list.
}

// This function is a variation of DFSUytil() in http://www.geeksforgeeks.org/archives/18212
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
	if (visited[v] == false)
	{
		// Mark the current node as visited and part of recursion stack
		visited[v] = true;
		recStack[v] = true;

		// Recur for all the vertices adjacent to this vertex
		list<int>::iterator i;
		for (i = adj[v].begin(); i != adj[v].end(); ++i)
		{
			if (!visited[*i] && isCyclicUtil(*i, visited, recStack))
				return true;
			else if (recStack[*i])
				return true;
		}

	}

	recStack[v] = false;  // remove the vertex from recursion stack
	return false;
}

// Returns true if the graph contains a cycle, else false.
// This function is a variation of DFS() in http://www.geeksforgeeks.org/archives/18212
bool Graph::isCyclic()
{
	// Mark all the vertices as not visited and not part of recursion
	// stack
	bool *visited = new bool[V];
	bool *recStack = new bool[V];
	for (int i = 0; i < V; i++)
	{
		visited[i] = false;
		recStack[i] = false;
	}

	// Call the recursive helper function to detect cycle in different
	// DFS trees
	for (int i = 0; i < V; i++)
		if (isCyclicUtil(i, visited, recStack))
			return true;

	return false;
}

/*
April 23, 2015 

Julia's first practice - a graph in 2016
Just do two things to construct a graph:
1. Call constrcutor Graph, input how many vertices in the graph;
2. Next, one by one add edges for the graph, remember that the edge is directed, from start to end
3. Next, check the Graph class definition
4. Next, check addEdge function:
   in the Graph class, there is the list for each vertices. 
   class Graph definition for edge:
   list<int> *adj;	
   class Graph addEdge function - construct function:
   adj = new list<int>[V];   // now, the adj is created an array of list<int>; for each vertice, there is a list list<int>[i], i = 0, 1, ... V

5. Now, we are work on isCyclic checking function. 


*/
int main()
{
	// Create a graph given in the above diagram
	Graph g(4);
	g.addEdge(0, 1);
	g.addEdge(0, 2);
	g.addEdge(1, 2);
	g.addEdge(2, 0);
	g.addEdge(2, 3);
	g.addEdge(3, 3);

	if (g.isCyclic())
		cout << "Graph contains cycle";
	else
		cout << "Graph doesn't contain cycle";
	return 0;
}