Click here to Skip to main content
14,641,293 members
Rate this:
Please Sign up or sign in to vote.
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

#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

Rate this:
Please Sign up or sign in to vote.

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:

Graph::Graph(int v)
{
    this->vertex = v;
    adjList = new std::list<int>[v];
}
   
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, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100