Saturday, September 3, 2011

Multi list representation of a graph


/*Multi list representation of a graph */
#include <stdio.h>
typedef struct edge
 {
char u,v;
int next;
 }edge;

 int main()
   {
edge list[10];
int edgecount=0,nodecount,i,j,k;
char heads[10][2];
printf("\nEnter No of vertices : ");
scanf("%d",&nodecount);
printf("\nEnter the name of each node(A,B....) : ");
for(i=0;i<nodecount;i++)
  {    fflush(stdin);
scanf("%c",&heads[i][0]);
      // heads[i][0]=getchar();
fflush(stdin);
heads[i][1]=-1;
  }
printf("\nEnter No. of edges  : ");
scanf("%d",&edgecount);

printf("\nEnter edges as (u,v) pair : ");
for(i=0;i<edgecount;i++)
 {     fflush(stdin);
scanf("%c%c",&list[i].u,&list[i].v);
list[i].next=-1;
 }
   //creation of multilist
for(i=0;i<nodecount;i++)
 {
j=0;
while( j < edgecount && heads[i][0] != list[j].u)
    j++;
if(j<edgecount)
 {
heads[i][1]=j;
for(k=j+1;k<edgecount;k++)
 {
if(list[k].u==list[j].u)
    {
list[j].next=k;
j=k;
    }
 }
  }
  }

//display the headers
printf("\nHeaders\n" );
for(i=0;i<nodecount;i++)
       printf("\n%c  %d",heads[i][0],heads[i][1]);
printf("\nAdjacency list(u,v,next): \n");
for(i=0;i<edgecount;i++)
       printf("\n%c  %c  %d ",list[i].u,list[i].v,list[i].next);
return(0);
}


No comments:

Post a Comment