Depth First Search
AIM:
Implement Depth First Search
Description:
In this program, an un-directed graph is created with no weights, and Depth First Search is performed based on starting vertex.
Program:
#include<stdio.h>
#include<stdlib.h>
struct Graph
{
int v;
int e;
int adjMat[20][20];
};
struct Graph* createGraph(int v,int e)
{
int i,j;
struct Graph* g=(struct Graph*)malloc(sizeof(struct Graph));
g->v=v;
g->e=e;
for(i=0;i<v;i++)
{
for(j=0;j<v;j++)
{
g->adjMat[i][j]=0;
}
}
return g;
}
void insertEdges(struct Graph* g)
{
int i,src,dest;
printf("\n Enter Source and Destination Vertices for each edge: ");
i=0;
while(i<g->e)
{
printf("\n Edge %d : ",i+1);
printf("\n Source Vertex : ");
scanf("%d",&src);
printf(" Destination Vertex : ");
scanf("%d",&dest);
if(src>g->v||dest>g->v)
{
printf("\n Vertex does not exists! Enter Again! \n");
}
else if(g->adjMat[src][dest]>0)
{
printf("\n Edge already exists! Enter Again! \n");
}
else
{
g->adjMat[src][dest]=1;
g->adjMat[dest][src]=1;
i++;
}
}
}
void displayGraph(struct Graph* g)
{
int i,j;
printf("\n Adjacency Matrix Representation : \n");
for(i=0;i<g->v;i++)
{
printf("\n");
for(j=0;j<g->v;j++)
{
printf(" %d",g->adjMat[i][j]);
}
}
printf("\n");
}
void DFS(struct Graph* g)
{
int i,j,k,top,ver,flag,stack[g->v],start,Result[g->v];
struct Graph* FG=createGraph(g->v,g->v-1);
printf("\n Enter Starting Vertex : ");
scanf("%d",&start);
if(start>=g->v)
{
printf("\n Vertex Doesn't exist");
}
else
{
j=top=0;
stack[top]=start;
top++;
while(top!=0)
{
ver=stack[top-1];
Result[j]=stack[top-1];
j++;
top--;
for(i=0;i<g->v;i++)
{
flag=0;
if(g->adjMat[ver][i]==1&&ver!=i)
{
k=top-1;
while(k!=-1)
{
if(stack[k]==i)
{
flag=1;
break;
}
else
{
k--;
}
}
k=0;
while(k<j)
{
if(Result[k]==i)
{
flag=1;
break;
}
else
{
k++;
}
}
if(flag==0)
{
stack[top]=i;
FG->adjMat[i][ver]=1;
FG->adjMat[ver][i]=1;
top++;
}
}
}
}
printf("\n Final Graph : ");
displayGraph(FG);
printf("\n Depth First Search : ");
for(i=0;i<j;i++)
{
printf(" %d ",Result[i]);
}
}
}
int main()
{
int v,e;
printf("\n Enter No. of Vertices: ");
scanf("%d",&v);
printf("\n Enter No. of Edges: ");
scanf("%d",&e);
struct Graph* g=createGraph(v,e);
insertEdges(g);
displayGraph(g);
DFS(g);
return 0;
}
OUTPUT
Enter No. of Vertices: 5
Enter No. of Edges: 7
Enter Source and Destination Vertices for each edge:
Edge 1 :
Source Vertex : 0
Destination Vertex : 1
Edge 2 :
Source Vertex : 0
Destination Vertex : 3
Edge 3 :
Source Vertex : 1
Destination Vertex : 2
Edge 4 :
Source Vertex : 1
Destination Vertex : 3
Edge 5 :
Source Vertex : 1
Destination Vertex : 4
Edge 6 :
Source Vertex : 2
Destination Vertex : 4
Edge 7 :
Source Vertex : 3
Destination Vertex : 4
Adjacency Matrix Representation :
0 1 0 1 0
1 0 1 1 1
0 1 0 0 1
1 1 0 0 1
0 1 1 1 0
Enter Starting Vertex : 2
Final Graph :
Adjacency Matrix Representation :
0 0 0 1 0
0 0 1 0 0
0 1 0 0 1
1 0 0 0 1
0 0 1 1 0
Depth First Search : 2 4 3 0 1
--------------------------------
Process exited after 8.999 seconds with return value 0
Press any key to continue . . .
No comments:
Post a Comment