#include<graphics.h>
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<dos.h>
#define BLUE 1
#define GRAY 8
#define RED 4
#define WHITE 15
int nvertex,vertexcolor[30],adjmat[30][30],cord[30][30],q[50],i,j;
int top=0,bottom=0;
char alpha[10][2]={{"A"},{"B"},{"C"},{"D"},{"E"},{"F"},{"G"},{"H"},{"I"},{"J"}};
void push(int x)
{
q[top]=x;
top++;
}
int pop()
{
int x=q[bottom];
bottom++;
return x;
}
void drawgraph()
{
cleardevice();
setcolor(GREEN);
setcolor(RED);
for(i=0;i<nvertex;i++)
{
setfillstyle(1,vertexcolor[i]);
fillellipse(cord[i][0],cord[i][0],30,30);
for(j=0;j<nvertex;j++)
if(adjmat[i][j]==1)
line(cord[i][0],cord[i][1],cord[j][0],cord[j][1]);
outtextxy(cord[i][0],cord[i][1],alpha[i]);
}
}
void readcord()
{
printf("Enter coordinate Position of Node");
for(i=0;i<nvertex;i++)
{
printf("%d:",i);
scanf("%d%d",&cord[i][0],&cord[i][1]);
}
}
void initcolor()
{
for(i=0;i<30;i++)
vertexcolor[i]=WHITE;
}
void initadjmat()
{
printf("\nPositions:");
for(i=0;i<nvertex;i++)
printf("%d",i);
for(i=0;i<nvertex;i++)
{
printf("\n\t%d:",i);
for(j=0;j<nvertex;j++)
scanf("%d",&adjmat[i][j]);
}
}
void bfs()
{
int curnode;
drawgraph();
getch();
vertexcolor[0]=GRAY;
push(0);
while(top!=bottom)
{
curnode=pop();
printf("%d\t",curnode);
for(i=0;i<nvertex;i++)
if(adjmat[curnode][i]==1)
if(vertexcolor[i]==WHITE)
{
vertexcolor[i]=GRAY;
push(i);
}
vertexcolor[curnode]=BLUE;
drawgraph();
getch();
}
}
void recdfs(int x)
{
drawgraph();
getch();
vertexcolor[x]=GRAY;
for(i=0;i<nvertex;i++)
if(adjmat[x][i]==1)
if(vertexcolor[i]==WHITE)
recdfs(i);
vertexcolor[x]=BLUE;
}
void dfs()
{
for(i=0;i<nvertex;i++)
if(vertexcolor[i]==WHITE)
recdfs(i);
}
void main()
{
int gd=DETECT,gm=0;
initgraph(&gd,&gm," ");
initcolor();
printf("Enter number of Vetices:");
scanf("%d",&nvertex);
readcord();
initadjmat();
getch();
printf("Showing BFS Procedure");
getch();
bfs();
getch();
initcolor();
printf("Showing DFS Procedure");
getch();
dfs();
drawgraph();
getch();
}
