﻿

# Insertion and deletion of nodes and edges in a graph using adjacency list

﻿

Submitted by Manu Jemini, on January 09, 2018

A graph is a set of nodes or known number of vertices. When these vertices are paired together, we call it edges. An Edge is a line from one node to other. Every edge can have its cost or weight. Graphs are of two types Directed and Undirected. Directed graphs are the graphs in which the vertices are ordered and in undirected graphs the vertices are unordered.

Image source: https://courses.cs.vt.edu/csonline/DataStructures/Lessons/Graphs/graph.gif

Node is a vertex in the graph at a position. The Line between two nodes is an edge. The Edge can have weight or cost associated with it.

Edge is the line connecting two nodes or a pair of nodes. An Adjacency matrix is a square matrix used to represent a finite graph. It contains the information about the edges and its cost. If the value at the Ith row and Jth column is zero, it means an edge do not exist between these two vertices. Else you got the edge and cost of that edge.

C program

```#include <stdio.h>
#include <malloc.h>

struct edge;
struct node
{
struct node *next;
char name;
}*start=NULL;

struct edge
{
char dest;
};
struct node *find(char item);

void insert_node(char node_name)
{
struct node *tmp,*ptr;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->name=node_name;
tmp->next=NULL;

if(start==NULL)
{
start=tmp;
return;
}
ptr=start;
while( ptr->next!=NULL)
ptr=ptr->next;
ptr->next=tmp;
}/*End of insert_node()*/

void delete_node(char u)
{
struct node *tmp,*q;
if(start->name == u)
{
tmp=start;
start=start->next;  /* first element deleted */
free(tmp);
return;
}
q=start;
while(q->next->next != NULL)
{
if(q->next->name==u)     /* element deleted in between */
{
tmp=q->next;
q->next=tmp->next;
free(tmp);
return;
}
q=q->next;
}/*End of while*/
if(q->next->name==u)    /* last element deleted */
{
tmp=q->next;
free(tmp);
q->next=NULL;
}
}/*End of delete_node()*/

void delnode_edge(char u)
{
struct node *ptr;
struct edge *q,*start_edge,*tmp;
ptr=start;
while(ptr!=NULL)
{
{
free(tmp);
continue; /* continue searching in another edge lists */
}
{
if(q->link->dest==u)  /* element deleted in between */
{
free(tmp);
continue;
}
}/*End of while*/
if(q->link->dest==u)    /* last element deleted */
{
free(tmp);
}
ptr=ptr->next;
}/*End of while*/
}/*End of delnode_edge()*/

void insert_edge(char u,char v)
{
struct node *locu,*locv;
struct edge *ptr,*tmp;
locu=find(u);
locv=find(v);

if(locu==NULL )
{
printf("Source node not present ,first insert node %c\n",u);
return;
}
if(locv==NULL )
{
printf("Destination node not present ,first insert node %c\n",v);
return;
}
tmp=(struct edge *)malloc(sizeof(struct edge));
tmp->dest=v;

{
return;
}

}/*End of insert_edge()*/

struct node *find(char item)
{
struct node *ptr,*loc;
ptr=start;
while(ptr!=NULL)
{
if(item==ptr->name)
{
loc=ptr;
return loc;
}
else
ptr=ptr->next;
}
loc=NULL;
return loc;
}/*End of find()*/

void del_edge(char u,char v)
{
struct node *locu,*locv;
struct edge *ptr,*tmp,*q;
locu=find(u);

if(locu==NULL )
{
printf("Source node not present\n");
return;
}

{
free(tmp);
return;
}
{
if(q->link->dest==v)  /* element deleted in between */
{
free(tmp);
return;
}
}/*End of while*/
if(q->link->dest==v)    /* last element deleted */
{
free(tmp);
return;
}
printf("This edge not present in the graph\n");
}/*End of del_edge()*/

void display()
{
struct node *ptr;
struct edge *q;

ptr=start;
while(ptr!=NULL)
{
printf("%c ->",ptr->name);
while(q!=NULL)
{
printf(" %c",q->dest);
}
printf("\n");
ptr=ptr->next;
}
}/*End of display()*/
main()
{
int choice;
char node,origin,destin;
while(1)
{
printf("1.Insert a node\n");
printf("2.Insert an edge\n");
printf("3.Delete a node\n");
printf("4.Delete an edge\n");
printf("5.Display\n");
printf("6.Exit\n");
scanf("%d",&choice);

switch(choice)
{
case 1:
printf("Enter a node to be inserted : ");
fflush(stdin);
scanf("%c",&node);
insert_node(node);
break;
case 2:
printf("Enter an edge to be inserted : ");
fflush(stdin);
scanf("%c %c",&origin,&destin);
insert_edge(origin,destin);
break;
case 3:
printf("Enter a node to be deleted : ");
fflush(stdin);
scanf("%c",&node);
/*This fn deletes the node from header node list*/
delete_node(node);
/* This fn deletes all edges coming to this node */
delnode_edge(node);
break;
case 4:
printf("Enter an edge to be deleted : ");
fflush(stdin);
scanf("%c %c",&origin,&destin);
del_edge(origin,destin);
break;
case 5:
display();
break;
case 6:
break;
default:
printf("Wrong choice\n");
break;
}/*End of switch*/
}/*End of while*/
}/*End of main()*/
```

Output

﻿

﻿

You may also be interested in...

C/C++ Tips and Tricks...

Most viewed pages...

Featured posts...