Graphs
Implementation of Adjacency List Representation for Graphs
/*Implementation of Adjacency List Representation for graphs*/
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 4
struct edge;
typedef struct node
{
int id;
char city[25];
struct edge *next;
}VERTEX;
typedef struct edge
{
int adj;
int distance;
struct edge *next;
}EDGE;
VERTEX *nodes[MAX]={NULL};
VERTEX *makevertex(char str[],int pos)
{VERTEX *temp = (VERTEX *)malloc(sizeof(VERTEX));
temp->id = pos;
strcpy(temp->city,str);
temp->next=NULL;
return temp;
}
void getnode_info()
{
int i;
char city[25];
VERTEX *temp;
for(i=0;i<MAX;i++)
{printf(“Enter city name?”);
scanf(“%s”,city);
temp=makevertex(city,i);
nodes[i]=temp;
}
}
int return_subscript(char nm[])
{int i;
for(i=0;i<MAX;i++)
if(strcmp(nm,nodes[i]->city)==0)
return i;
return -1;
}
EDGE *makenode(int num,int j)
{
EDGE *temp = (EDGE *)malloc(sizeof(EDGE));
temp->adj=j;
temp->distance=num;
temp->next=NULL;
return temp;
}
VERTEX *join(VERTEX *node,EDGE *arc)
{VERTEX *temp=node;
EDGE *edg=temp->next;
if(node->next==NULL)
{node->next=arc;
return node;
}
while(edg->next!=NULL)
edg=edg->next;
temp->next=arc;
return node;
}
void display()
{int i;
EDGE *temp;
for(i=0;i<MAX;i++)
{printf(“%dt%st”,nodes[i]->id,nodes[i]->city);
temp=nodes[i]->next;
while(temp!=NULL)
{printf(“%d/%dt”,temp->adj,temp->distance);
temp=temp->next;
}
printf(“n”);
}
}
void main()
{
int ans,i,j;
EDGE *temp;
char city1[25],city2[25];
int distance;
getnode_info();
do
{
do
{printf(“nDoes route exists?”);
printf(“nFrom City?”);
scanf(“%s”,city1);
printf(“nTo City?”);
scanf(“%s”,city2);
i=return_subscript(city1);
j=return_subscript(city2);
}while(i==-1 || j==-1);
/*Now making node*/
printf(“nEnter distance?”);
scanf(“%d”,&distance);
temp=makenode(distance,j);
nodes[i]=join(nodes[i],temp);
printf(“nContinue(1/0)?”);
scanf(“%d”,&ans);
}while(ans==1);
display();
getch();
}