DFS and BFS in directed graph

graph.h.cpp

/* Implement a directed graph using adjacency list representation
 * Depth First Traversal for a Graph: http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/
 * Breadth First Traversal for a Graph http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/
 * Connectivity in a directed graph: http://www.geeksforgeeks.org/connectivity-in-a-directed-graph/
 */

#ifndef GRAPH_H
#define GRAPH_H

#include <iostream>
#include <list>

using namespace std;

class Graph {
public:
	Graph(int n) : V(n), adj(new list<int>[V]) {}
	~Graph() { delete[] adj; }
	void addEdge(int v, int w) { adj[v].push_back(w); } // add w to v's adjacent list
	void DFS(int v); // DFS traversal of the vertices reachable from v
	void DFS(); // DFS traversal of the complete graph
	void BFS(int v); // BFS traversal from vertex v
	void BFS(); // BFS traversal of the complete graph
private:
	int V; // number of vertices
	list<int> *adj; // array of adjacent lists
	void DFSUtil(int v, bool visited[]); // DFS starting from v to w
};

void Graph::DFSUtil(int v, bool visited[])
{
	visited[v] = true; // Mark the current node as visited and print it
	cout << v << " ";
	for (auto it = adj[v].begin(); it != adj[v].end(); ++it) { // Recur for all the vertices adjacent to this vertex
		if (!visited[*it])
			DFSUtil(*it, visited);
	}
}

// Time Complexity : O(V + E)
void Graph::DFS(int v)
{
	bool *visited = new bool[V]; // Mark all the vertices as not visited
	for (int i = 0; i != V; ++i)
		visited[i] = false;
	DFSUtil(v, visited); // Call the recursive helper function to print DFS traversal
}

// Time Complexity : O(V + E)
void Graph::DFS()
{
	bool *visited = new bool[V];
	for (int i = 0; i != V; ++i)
		visited[i] = false;
	for (int i = 0; i != V; ++i) {
		if (!visited[i])
			DFSUtil(i, visited);
	}
}

// Time Complexity : O(V + E)
void Graph::BFS(int s)
{
	bool *visited = new bool[V];
	for (int i = 0; i != V; ++i) // Mark all the vertices as not visited
		visited[i] = false;
	list<int> queue; // Create a queue for BFS
	visited[s] = true; // Mark the current node as visited and enqueue it
	queue.push_back(s);
	while (!queue.empty()) {
		s = queue.front(); // Dequeue a vertex from queue and print it
		cout << s << " ";
		queue.pop_front();
		// Get all adjacent vertices of the dequeued vertex s
		// If a adjacent has not been visited, then mark it visited and enqueue it
		for (auto i = adj[s].begin(); i != adj[s].end(); ++i) {
			if (!visited[*i]) {
				visited[*i] = true;
				queue.push_back(*i);
			}
		}
	}
}

// Time Complexity : O(V + E)
void Graph::BFS()
{
	bool *visited = new bool[V];
	for (int i = 0; i != V; ++i)
		visited[i] = false;
	list<int> queue;
	for (int s = 0; s != V; ++s) {
		if (!visited[s]) {
			visited[s] = true;
			queue.push_back(s);
			while (!queue.empty()) {
				int t = queue.front();
				cout << t << " ";
				queue.pop_front();
				for (auto i = adj[t].begin(); i != adj[t].end(); ++i) {
					if (!visited[*i]) {
						visited[*i] = true;
						queue.push_back(*i);
					}
				}
			}
		}
	}
}

#endif

graph_test.cpp

#include "graph.h"

int main()
{
	Graph g(7);
	g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(0, 3);
	g.addEdge(1, 3); g.addEdge(1, 4);
	g.addEdge(2, 5);
	g.addEdge(3, 2); g.addEdge(3, 5); g.addEdge(3, 6);
	g.addEdge(4, 3); g.addEdge(4, 6);
	g.addEdge(6, 5);
	cout << "DFS from vertex 1:" << endl;
	g.DFS(1); cout << endl;
	cout << "DFS from vertex 3:" << endl;
	g.DFS(3); cout << endl;
	cout << "complete DFS:" << endl;
	g.DFS(); cout << endl;
	cout << "BFS from vertex 0:" << endl;
	g.BFS(0); cout << endl;
	cout << "BFS from vertex 1:" << endl;
	g.BFS(1); cout << endl;
	cout << "complete BFS:" << endl;
	g.BFS(); cout << endl;
	return 0;
}