graph.h

// Author: Selcuk Orhan Demirel
// Date: 01/13/2011

// Demonstrates Depth First and Breadth First Traversal on Graphs
// Graph class implementation

include <iostream>
#include <Queue>
#include <Stack>

using namespace std;

class Graph
{
public:
	Graph(int NOV);
	~Graph();
	void setEdge(int v1, int v2);
	void print();
	void BFS(int v);
	void DFS(int v);
	int edgeNumber() { return edge; }
private:
	int **GMatrix;
	int *visited;
	int vertex;
	int edge;
};

Graph::Graph(int NOV)
{
	edge = 0;
	vertex = NOV;

	GMatrix = new int*[NOV];

	for(int i=0;i<NOV;i++)
	{
		GMatrix[i] = new int[NOV];
		for(int j=0;j<NOV;j++)
		{
			GMatrix[i][j] = 0;
		}
	}

	visited = new int[NOV];
}

Graph::~Graph()
{
	delete [] visited;
	for(int i=0;i<vertex;i++)
		delete [] GMatrix[i];
	delete [] GMatrix;
}

void Graph::setEdge(int v1, int v2)
{
	if(GMatrix[v1][v2]==0)
	{
		GMatrix[v1][v2] = 1;
		edge++;
	}
}

void Graph::print()
{
	for(int i=0;i<vertex;i++)
	{
		for(int j=0;j<vertex;j++)
		{
			cout << GMatrix[i][j] << "\t";
		}
		cout << endl;
	}
}

void Graph::BFS(int v)
{
	for(int i=0;i<vertex;i++)
		visited[i] = 0;

	queue<int> q;
	q.push(v);
	while(!q.empty())
	{
		int s = q.front();
		q.pop();
		visited[s] = 1;
		cout << s << " ";

		for(int i=0;i<vertex;i++)
		{
			if(GMatrix[s][i] != 0 && visited[i] == 0)
			{
				q.push(i);
				visited[i] = 1;
			}
		}
	}

}

void Graph::DFS(int v)
{
	for(int i=0;i<vertex;i++)
		visited[i] = 0;

	stack<int> s;
	s.push(v);
	while(!s.empty())
	{
		int k = s.top();
		s.pop();
		visited[k] = 1;
		cout << k << " ";

		for(int i=0;i<vertex;i++)
		{
			if(GMatrix[k][i] != 0 && visited[i] == 0)
			{
				s.push(i);
				visited[i] = 1;
			}
		}
	}
	
}

graphtest.cpp

// Author: Selcuk Orhan Demirel
// Date: 01/13/2011

// Demonstrates Depth First and Breadth First Traversal on Graphs
// Test code

#include "graph.h"
using namespace std;

int main()
{
	
	Graph g(4);
	g.setEdge(0,1);
	g.setEdge(0,2);
	g.setEdge(1,2);
	g.setEdge(2,3);
	g.print();
	g.BFS(0);
	g.DFS(0);
	system("PAUSE");
	return 0;
}