Graph - Adjacency list - DFS

/***

Graph based
http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

***/

// adjacent list represented graph

class graph

{

                int V; // # of vertices

                list<int> *adj; //Pointer to an array containing adjacency lists

                void DFSUtil(int v, bool *visited); //func used by DFS, bool array marks visited

public:

                graph(int V);

                void add_edge(int v, int w); //edge between w and v

                void DFS(int v);

};

graph::graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

void graph::add_edge(int v, int w)

{

    adj[v].push_back(w); // Add w to v’s list.

}

void graph::DFSUtil(int v, bool *visited) {

                //mark current node as visited and print it

                visited[v] = true;

                cout<<v<<" ";

                //recur for all the vertices adjacent to this vertex

                list<int>::iterator it;

                for(it = adj[v].begin(); it != adj[v].end(); it++) {

                                if(!visited[*it]) DFSUtil(*it, visited);

                }

}

void graph::DFS(int v) {

                //mark all the vertices as not visited

                bool *visited = new bool[V];

                for(int i = 0; i<V; i++) visited[i] = false;

                //call the recur helper function to print DFS traversal start from given node

                //DFSUtil(v, visited);

                //if need print all vertices even for disconnected node, traverse all vertex.

                for(int i = 0; i<V; i++)

                                if(!visited[i]) DFSUtil(i, visited);

}