C C++ Java Data Structure Python JavaScript CSS Ajax PL/SQL PHP Puzzles C programs C++ programs Java programs



Home » Data Structure

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



In this article, we will learn about Graph, Adjacency Matrix with linked list, Nodes and Edges.
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.

Graph in DS using C

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.

Graph in DS using C

Image source: http://2.bp.blogspot.com/-KS2IS_wQ99k/Ux5EYJg2SZI/AAAAAAAACL8/xn2mJDQto8o/s1600/Adjacency+Matrix+Representation+of+Weighted+Graph.JPG

C program

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

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

struct edge
{
	char dest;
	struct edge *link;
};
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;
	tmp->adj=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)
	{
		/* ptr->adj points to first node of edge linked list */
		if(ptr->adj->dest == u)
		{
			tmp=ptr->adj;
			ptr->adj=ptr->adj->link;  /* first element deleted */
			free(tmp);
			continue; /* continue searching in another edge lists */
		}
		q=ptr->adj;
		while(q->link->link != NULL)
		{
			if(q->link->dest==u)  /* element deleted in between */
			{
				tmp=q->link;
				q->link=tmp->link;
				free(tmp);
				continue;
			}
			q=q->link;
		}/*End of while*/
		if(q->link->dest==u)    /* last element deleted */
		{
			tmp=q->link;
			free(tmp);
			q->link=NULL;
		}
		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;
	tmp->link=NULL;


	if(locu->adj==NULL)   /* item added at the begining */
	{
		 locu->adj=tmp;
		  return;
	}
	ptr=locu->adj;
	while(ptr->link!=NULL)
		ptr=ptr->link;
	ptr->link=tmp;

}/*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;
	}

	if(locu->adj->dest == v)
	{
		tmp=locu->adj;
		locu->adj=locu->adj->link;  /* first element deleted */
		free(tmp);
		return;
	}
	q=locu->adj;
	while(q->link->link != NULL)
	{
		if(q->link->dest==v)  /* element deleted in between */
		{
			tmp=q->link;
			q->link=tmp->link;
			free(tmp);
			return;
		}
		q=q->link;
	}/*End of while*/
	if(q->link->dest==v)    /* last element deleted */
	{
		tmp=q->link;
		free(tmp);
		q->link=NULL;
		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);
		q=ptr->adj;
		while(q!=NULL)
		{
			printf(" %c",q->dest);
			q=q->link;
		}
		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");
		printf("Enter your choice : ");
		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

Graph in DS using C






You may also be interested in...

C/C++ Tips and Tricks...

Was this page helpful? YES NO

Are you a blogger? Join our Blogging forum.


Comments and Discussions