15,946,988 members
See more:
can someone explain to me how int v is used as an index for the list, it's just a value in the specified index of the list, then why we check `if color[v]==GRAY`

C++
```#include <iostream>
#include <list>

enum Color{WHITE, GRAY, BLACK};

class Graph
{
int V;
bool DFSUtil(int v, int color[]);

public:
Graph(int V);
bool isCyclic();
};

Graph::Graph(int V)
{
this->V=V;
}

{
}

bool Graph::DFSUtil(int u, int color[])
{

color[u]=GRAY;

std::list<int>::iterator it;
{
int v=*it;

if(color[v]==GRAY)
{
return true;
}
if(color[v]==WHITE && DFSUtil(v, color))
{
return true;
}

}
color[u]=BLACK;
return false;
}

bool Graph::isCyclic()
{
int *color=new int[V];
for(int i=0; i<V; i++)
{
color[i]=WHITE;
}
for(int i=0; i<V; i++)
{
if(color[i]==WHITE)
{
if(DFSUtil(i, color))
{
return true;
}
}
}

return false;
}

int main()
{
// Create a graph given in the above diagram
Graph g(4);

if (g.isCyclic())
std::cout << "Graph contains cycle";
else
std::cout << "Graph doesn't contain cycle";

return 0;
}```

What I have tried:

I have tried to understand it with debugging
Posted
Updated 30-Jan-18 20:14pm
v2
nv3 30-Jan-18 17:15pm
The array color is an array with the same number of elements as the Graph has nodes. Think of each node as having a node number of 0 to V-1. Line

int v=*it;

extracts a node number of one of the adjacency lists. We can than check the color of this node by color[v]. Think of color as an additional property of every graph node. As it is only used in the isCyclic function it is only allocated there and kept as a parallel array.

Note also the bugs in this code: color is never freed! And neither are the adjacency lists!
Member 13277493 30-Jan-18 17:23pm
thank you very much, I will fix them. And one more question, they are as many linked lists as the vertices are, am I right? For each vertex, there is a linked list created by its adjacent vertices.

Solution 1

Yes, for for every vertex gets an entry in the list created, but you list has some small by using an int pointer, but using a cast to insert an entry.

Important tip: use for the class member V a long and better name like "index" or vertex to seperate it clearer from input vars. Vars are normally in lower case.

The code gets clearer and more fun to read:

C++
```Graph::Graph(int v)
{
this->vertex = v;
}```

nv3 31-Jan-18 11:44am
I don't think that "vertex" is good name for V, as it refers to the maximum number of vertices supported by that object. "maxVertices" would probably give a better representation.

But that is not the only bad practice in the code. "adjList" should be "adjLists" as it is a collection of lists. And I would actually recommend to use an array instead of a list in this context.
KarstenK 1-Feb-18 3:18am
ofcourse the best fitting name should get choosed ;-)