Thursday, October 7, 2010

C Programming - GraphTraversal using BackTracking

ALGORITHM
C Programming - GraphTraversal using BackTracking


#include
#include

int aiQueue[10],iFront=-1,iRear=-1;


void fnDfs(int aiAdj[7][7],int iN,int iI,int aiVisit[7])
{
int iJ;
aiVisit[iI]=1;
printf(" %d ",iI+1);
for(iJ=0;iJ
if(aiAdj[iI][iJ]==1 && aiVisit[iJ]==0)
fnDfs(aiAdj,iN,iJ,aiVisit);
}


int Empty()
{
if(iRear==-1 && iFront==-1)
return 0;
return 1;
}

void fnEnQueue(int aiQueue[7],int iI)
{
if(iFront==-1 && iRear==-1)
iFront++;
iRear++;
aiQueue[iRear]=iI;
}

int fnDeQueue(int aiQueue[7],int iI)
{
iI=aiQueue[iFront];
if(iFront==iRear)
iRear=iFront=-1;
else
iFront++;
return iI;
}


void fnBfs(int aiAdj[7][7],int iN,int iI,int aiVisit[7])
{
int iJ,iX;
aiVisit[iI]=1;
printf(" %d ",iI+1);
for(iJ=0;iJ
{
if(aiAdj[iI][iJ]==1 && aiVisit[iJ]==0)
{
fnEnQueue(aiQueue,iJ);
aiVisit[iJ]=1;
}
}
if(iFront==-1 && iRear==-1)
return;
iX=fnDeQueue(aiQueue,iI);
fnBfs(aiAdj,iN,iX,aiVisit);
}

void main()
{
int iChoice,iI,iJ,aiAdj[7][7],aiVisit[7],iNo;
clrscr();
printf("\n\t\tGRAPH TRAVERSAL");
printf("\n\t1.BIRTH FIRST SEARCH");
printf("\n\t2.DEPTH FIRST SEARCH");
printf("\n\t3.EXIT");
printf("\nEnter the no of vertices : ");
scanf("%d",&iNo);
printf("\nEnter the adjency matrix ");
for(iI=0;iI
for(iJ=0;iJ
scanf("%d",&aiAdj[iI][iJ]);
do
{
printf("\nEnter your choice : ");
scanf("%d",&iChoice);
switch(iChoice)
{
case 1://Depthfirst search
for(iI=0;iI
aiVisit[iI]=0;
fnDfs(aiAdj,iNo,0,aiVisit);
break;
case 2://Birthfirst search
for(iI=0;iI
aiVisit[iI]=0;
fnBfs(aiAdj,iNo,0,aiVisit);
break;
case 3://Exit
break;
}
}while(iChoice!=3);
}

/*

GRAPH TRAVERSAL
1.BIRTH FIRST SEARCH
2.DEPTH FIRST SEARCH
3.EXIT
Enter the no of vertices : 6

Enter the adjency matrix
0 1 0 0 0 1
0 0 1 0 0 1
0 0 0 1 0 1
0 0 0 0 0 0
1 0 0 1 0 0
0 0 0 0 1 0

Enter your choice : 1
1 2 3 4 6 5
Enter your choice : 2
1 2 6 3 5 4
Enter your choice : 3

*/


No comments:

Post a Comment