Click here to Skip to main content
15,946,988 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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;
    std::list<int>*adjList;
    bool DFSUtil(int v, int color[]);

public:
    Graph(int V);
    void addEdge(int v, int w);
    bool isCyclic();
};

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

void Graph::addEdge(int v, int w)
{
    adjList[v].push_back(w);
}

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

    color[u]=GRAY;

    std::list<int>::iterator it;
    for(it=adjList[u].begin(); it!=adjList[u].end(); 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);
    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())
        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
Comments
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.

1 solution

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;
    adjList = new std::list<int>[v];
}
 
Share this answer
 
Comments
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 ;-)

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900