graph.cpp

All are the assignments of mine that I have developped in Data Structure Laboratory Hours

/* Ass No. 8
   Program: Graph: 1. Creation of graph Using Adjecency List 2. DSF 3. BSF
   Programmed By: M. R. Sanghavi*/

/* Header File Declaration*/
#include "iostream.h"
#include "conio.h"
/* Class Definition For Node of Tree */
class Vertex
{
	public:
		/* Data Members */
		int nData;
		Vertex *pNext,*pDown;
		/* Memeber Function */
		Vertex * CreateGraph(Vertex *);
		void Display(Vertex *);
		void DSF(Vertex *);
		void BSF(Vertex *);
};
/* Global Declaration & Initialization */
int nTop = 0,nStack[10],nVisit[10],nQueue[10],nFront=0,nRear=-1;
/* Function to Initialize the nVisit Array value to Zero */
void InitializeVisit()
{
	for(int nI=0;nI<10;nI++)
		nVisit[nI]=0;
}
/* Function which Create & Attach the Vertex to Graph */
Vertex * Vertex::CreateGraph(Vertex *pStart)
{
	Vertex *pVTemp,*pT1,*pATemp,*pT2;
	char cAnsVertex,cAnsAdj;
	do
	{
		pVTemp = new Vertex;
		cout<<"\n Enter Vertex :";
		cin>>pVTemp->nData;
		pVTemp->pDown = pVTemp->pNext = NULL;
		if(pStart==NULL)
			pT1 = pStart = pVTemp;
		else
		{
			pT1->pDown = pVTemp;
			pT1 = pVTemp;
		}
		pT2 = pVTemp;
		cout<<"\n Do U want to add Adjencency Vertex For Vertex("<<pVTemp->nData<<")";
		cin>>cAnsAdj;
		while(cAnsAdj == 'y'|| cAnsAdj == 'Y')
		{
			pATemp = new Vertex;
			cout<<"\n Enter Adjecent Vertex :";
			cin>>pATemp->nData;
			pATemp->pNext = NULL;
			pATemp->pDown = NULL;
			pT2->pNext = pATemp;
			pT2 = pATemp;
			cout<<"\n Do U want to add More Adjencency Vertex For Vertex("<<pVTemp->nData<<")";
			cin>>cAnsAdj;
		}
		cout<<"\n Do U want to add More Vertex ";
		cin>>cAnsVertex;
	}while(cAnsVertex == 'Y' || cAnsVertex == 'y');
	return(pStart);
}
/* Function Deisplay a Tree in InOrder Traversal */
void Vertex::Display(Vertex *pStart)
{
	Vertex *pVTemp = pStart,*pATemp;
	while(pVTemp != NULL)
	{
		cout<<"\n"<<pVTemp->nData;
		pATemp = pVTemp->pNext;
		while(pATemp != NULL)
		{
			cout<<"\t"<<pATemp->nData;
			pATemp = pATemp->pNext;
		}
	       pVTemp = pVTemp->pDown;
	}
}
/* Function to Push the Value In to Stack & Make Visited */
void Push(int nVertex)
{
	nStack[++nTop] = nVertex;
	if(nVisit[nVertex] == 0)
		nVisit[nVertex] = 1;
}
/* Function to return the Popped Value from Stack */
int Pop()
{
	return(nStack[--nTop]);
}
/* Function for DSF */
void Vertex::DSF(Vertex *pStart)
{
	int nParent,nFlag,nStartVertex;
	Vertex *pT1,*pT2;
	pT1 = pT2 = pStart;
	cout<<"\n Enter Initial Vertex :";
	cin>>nStartVertex;
	cout<<nStartVertex;
	Push(nStartVertex);
	while(nTop != -1)
	{
		nFlag = 0;
		nParent = Pop();
		pT1 = pStart;
		while(pT1 != NULL)
		{
			if(pT1->nData == nParent)
			{
				pT2 = pT1->pNext;
				while(pT2 != NULL)
				{
					if(nVisit[pT2->nData] == 0)
					{
						cout<<"\t"<<pT2->nData;
						Push(pT1->nData);
						Push(pT2->nData);
						nFlag = 1;
						break;
					}
					else
						pT2 = pT2->pNext;
				}
			}
			if(nFlag == 1)
				break;
			else
				pT1 = pT1->pDown;
		}

	}
}
/* Function to Insert the Value in to Queue */
void Insert(int nVertex)
{
	nQueue[++nRear] = nVertex;
	if(nVisit[nVertex] == 0)
		nVisit[nVertex] = 1;
}
/* Function to Delete the value from Queue */
int Delete()
{
	int nVal;
	if(((nRear == 9)&&(nFront == nRear))||(nFront == nRear+1))
	{
		 nVal = nQueue[nFront];
		 nFront = 0;
		 nRear = -1;
	}
	else
		nVal = nQueue[nFront++];
	return(nVal);
}
void Vertex::BSF(Vertex *pStart)
{
	int nStartVertex,nParent,nFlag;
	Vertex *pT1,*pT2;
	pT1 = pT2 = pStart;
	cout<<"\n Enter Initial Vertex :";
	cin>>nStartVertex;
	cout<<"\n"<<nStartVertex;
	Insert(nStartVertex);
	while((nRear != 1) || (nFront != nRear+1))
	{
		nParent = Delete();
		pT1 = pStart;
		nFlag = 0;
		while(pT1 != NULL)
		{
			if(pT1->nData == nParent)
			{
				pT2 =pT1->pNext;
				while(pT2 != NULL)
				{
					if(nVisit[pT2->nData]==0)
					{
						cout<<"\t"<<pT2->nData;
						Insert(pT2->nData);
						nFlag = 1;
					}
					else
						pT2 = pT2->pNext;
				}
			}
			if(nFlag==1)
				break;
			else
				pT1 = pT1->pDown;
		}
	}
}
/* Main Function Starts Here */
void main()
{
	Vertex p1,*pStart = NULL;
	clrscr();
	pStart = p1.CreateGraph(pStart);
	cout <<"\n Created Graph ... \n";
	p1.Display(pStart);
	cout <<"\n DSF ...\n";
	p1.DSF(pStart);
	cout <<"\n BSF ...\n";
	p1.BSF(pStart);
	getch();
}
/* E n d   o f   P r o g r a m */