Adjacency Matrix,
Breadth First and Depth First Search.
An
adjacency matrix is a means of representing which vertices (or nodes) of a
graph are adjacent to which other
vertices. Another matrix representation for a graph is the incidence matrix.
All
child nodes obtained by expanding a node are Pushed to a Queue (FIFO - First In
First Out), and then POP the value in
same order to print the sequence.
Using a
stack instead of a queue would turn this algorithm into a depth-first search.
// Program for adjacency matrix
#include <stdio.h>
#include <conio.h>
#define MAX 20
int adm[MAX][MAX]; //Declaring
Adjacency matrix
int n; // to store n umbers of
nodes in the graph
void
Adjm()
{
int
edges,i,j,x,y;
char
type;
printf("\n\tNumber
of nodes : "); //assume 4
scanf("%d",&n);
edges=n*(n-1);
for(i=1;i<=edges;i++)
{
//enter
1 2 , 1 3, 2 4, 3 4
printf("\n\tEnter
edge (x,y) of %d ( 0 0 to quit ) :
",i);
scanf("%d%d",&x,&y);
if( (x==0) && (y==0)
)
{
break;
}
if( x > n || y >
n || x<=0 || y<=0)
{
printf("Invalid edges,
Enter again\n");
i--;
}
else
{
adm[x][y]=1;
}
}
}
void disp()
{
int i,j;
printf("\n\tAdjacency
matrix :\n");
for(i=1;i<=n;i++)
{
printf("\t");
for(j=1;j<=n;j++)
{
printf("%d ",adm[i][j]);
}
printf("\n");
}
printf("\n\n\tPress
Any Key to Cont..");
getch();
clrscr();
}
void bfs()
{
int
qu[MAX],rear=0,front=0,i,j,start=1;
int
visited[MAX]={0},visit[MAX];
start=1;
printf("\n\tVisitied : ");
printf("%d",start);
visited[start]=1;
i=1;
while(i<
n)
{
for(j=1;j<=n;j++)
{
if(adm[start][j]!=0
&& visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
qu[rear++]=j;
}
}
start=qu[front++];
printf("
%d ", start );
i++;
visit[start]=0;
visited[start]=1;
}
printf("\n\n\tPress Any Key to
Cont..");
getch();
clrscr();
}
void
dfs()
{
int
stack[MAX],top=-1,i,j,start=n;
int
visited[MAX]={0},visit[MAX];
printf("\n\tVisitied : ");
printf("%d",start);
visited[start]=1;
i=1;
while(i<
n)
{
for(j=n-1;j>=1;j--)
{
if(adm[start][j]!=0
&& visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
stack[top++]=j;
}
}
start=stack[--top];
printf("
%d ", start );
i++;
visit[start]=0;
visited[start]=1;
}
printf("\n\n\tPress
Any Key to Cont..");
getch();
clrscr();
}
void
main()
{
int
c=0;
clrscr();
do
{
printf("\n\n\t1.
Adjancy Matrix ");
printf("\n\t2. Display");
printf("\n\t3.
Breadth First Search");
printf("\n\t4.
Depth First Search");
printf("\n\t5.
Exit");
printf("\n\tEnter
a Choice : ");
scanf("%d",&c);
switch(c)
{
case
1:
Adjm();break;
case
2:
disp();break;
case 3:
bfs();break;
case
4:
dfs();break;
case
5:
printf("\n\n\t\tQuit.......");
getch();
exit(0);
}
}while(c<5);
}
No comments:
Post a Comment