Operations on Graph Data Structure
AIM:
Implement operations on Graphs:-
i. Vertex insertion
ii. Vertex deletion
iii. Finding vertex
iv. Edge addition and deletion
Description:
In this program, a un-directed graph is implemented and the graph is represented in Adjacency Matrix form.
Program:
#include<stdio.h>
#include<stdlib.h>
#include<stdlib.h>
struct Graph
{
int v;
int adjMat[10][10]; //Maximum 10 vertices
};
void insertVertex(struct Graph* g)
{
int i;
for(i=0;i<=g->v;i++)
{
g->adjMat[i][g->v]=0;
g->adjMat[g->v][i]=0;
}
}
void deleteVertex(struct Graph* g, int x)
{
int i;
while(x<g->v)
{
for(i=0;i<=g->v;++i)
{
g->adjMat[i][x]=g->adjMat[i][x+1];
}
for(i=0;i<=g->v;++i)
{
g->adjMat[x][i]=g->adjMat[x+1][i];
}
x++;
}
}
void searchVertex(struct Graph* g, int x)
{
int i;
printf("\n Adjacency List of vertex %d : ",x);
printf("\n %d <- ",x);
for(i=0;i<g->v;i++)
{
if(g->adjMat[x][i]==1&&x!=i)
{
printf("%d <- ",i);
}
}
printf("NULL\n");
}
void addEdge(struct Graph* g,int src, int dest)
{
g->adjMat[src][dest]=1;
g->adjMat[dest][src]=1;
}
void removeEdge(struct Graph* g,int src,int dest)
{
g->adjMat[src][dest]=0;
g->adjMat[dest][src]=0;
}
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");
}
int main()
{
int x,src,dest,cho;
struct Graph* g=(struct Graph*)malloc(sizeof(struct Graph));
g->v=-1; //graph has no vertices
do
{
printf("\n Choose Graph Operation : \n");
printf("\n 1. Insert a Vertex");
printf("\t 2. Delete a Vertex");
printf("\t 3. Find a Vertex ");
printf("\n 4. Add an Edge ");
printf("\t 5. Remove an Edge ");
printf("\t 6. Display Graph ");
printf("\t 7. Exit");
printf("\n\n Enter Your Choice : ");
scanf("%d",&cho);
switch(cho)
{
case 1:
g->v++;
printf("\n Vertex %d Inserted \n",g->v);
insertVertex(g);
break;
case 2:
printf("\n Enter Vertex to be deleted : ");
scanf("%d",&x);
if(x>g->v)
{
printf("\n Vertex not Present \n");
}
else
{
deleteVertex(g,x);
printf("\n Vertex Removed! \n");
g->v--;
}
break;
case 3:
printf("\n Enter Vertex to be searched : ");
scanf("%d",&x);
if(x>g->v)
{
printf("\n Vertex not Present \n");
}
else
{
searchVertex(g,x);
}
break;
case 4:
printf("\n Enter Source Vertex : ");
scanf("%d",&src);
printf("\n Enter Destination Vertex : ");
scanf("%d",&dest);
if((src>g->v)||(dest>g->v))
{
printf("\n Vertex does not exists! \n");
}
else
{
addEdge(g,src,dest);
printf("\n Edge Added! \n");
}
break;
case 5:
printf("\n Enter Source Vertex : ");
scanf("%d",&src);
printf("\n Enter Destination Vertex : ");
scanf("%d",&dest);
if((src>g->v)||(dest>g->v))
{
printf("\n Vertex does not exists! \n");
}
else
{
removeEdge(g,src,dest);
printf("\n Edge Removed! \n");
}
break;
case 6:
if(g->v==-1)
{
printf("\n Graph has no vertices \n");
}
else
{
displayGraph(g);
}
break;
case 7:
printf("\n Done!");
break;
default:
printf("\n Invalid Choice! \n");
}
}while(cho!=7);
return 0;
}
Output:
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 1
Vertex 0 Inserted
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 1
Vertex 1 Inserted
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 1
Vertex 2 Inserted
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 1
Vertex 3 Inserted
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 4
Enter Source Vertex : 0
Enter Destination Vertex : 1
Edge Added!
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 4
Enter Source Vertex : 0
Enter Destination Vertex : 2
Edge Added!
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 4
Enter Source Vertex : 1
Enter Destination Vertex : 2
Edge Added!
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 4
Enter Source Vertex : 2
Enter Destination Vertex : 3
Edge Added!
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 6
Adjacency Matrix Representation :
0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 1
Vertex 4 Inserted
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 4
Enter Source Vertex : 4
Enter Destination Vertex : 1
Edge Added!
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 4
Enter Source Vertex : 4
Enter Destination Vertex : 3
Edge Added!
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 6
Adjacency Matrix Representation :
0 1 1 0 0
1 0 1 0 1
1 1 0 1 0
0 0 1 0 1
0 1 0 1 0
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 3
Enter Vertex to be searched : 2
Adjacency List of vertex 2 :
2 <- 0 <- 1 <- 3 <- NULL
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 5
Enter Source Vertex : 2
Enter Destination Vertex : 1
Edge Removed!
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 2
Enter Vertex to be deleted : 1
Vertex Removed!
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 6
Adjacency Matrix Representation :
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
Choose Graph Operation :
1. Insert a Vertex 2. Delete a Vertex 3. Find a Vertex
4. Add an Edge 5. Remove an Edge 6. Display Graph 7. Exit
Enter Your Choice : 7
Done!
--------------------------------
Process exited after 197.5 seconds with return value 0
Press any key to continue . . .
No comments:
Post a Comment