Linked representation of Graphs in C

There are many in-inadequacies in using the Adjacency Matrix representation of Graphs. Once such inadequacy is the difficulty in adding or deleting nodes while data is to be updated dynamically. Another inadequacy is that even if there exists no arc between two nodes, space must be reserved for the same in the array.

Such inadequacies are solved by using a LINKED Structure which represents a dynamic implementation of Graphs. In such a Linked representation, Graph nodes are represented by HEADER NODES of the format 

and arc nodes are represented by a LIST OF ARCS NODES of the format 

The Header nodes and List nodes are interconnected by pointer so that a particular graph is represented as a Linked Structure. The arc pointer of a Header node points to list of arc nodes emanating from that header node and the next node points to the next header node. The node pointer of the arc node points to that header node which terminates the arc. The next arc points the next arc of the list. For eg., the following graph, 

could be represented as a Linked Structure as shown below –

Dynamic Implementation of Linked Graph

For simplicity of using a single structure for both nodes and arcs, we assume that nodes and arcs have the same format with two pointers and one integer info field. The dynamic implementation is as shown below –

struct nodetype{
                int info;
                struct nodetype * point;
                struct nodetype * next;
               };
         struct nodetype * nodeptr;

/* nodeptr->info points to info field of a particular header node*/
/*nodeptr->point points to an arc node of the same structure as node ptr*/
/*The same structure applies to arc nodes*/

The array implementation of a Linked Graph is as shown below –

struct nodetype{
                 int info;
                 int point;
                 int next;
}
struct nodetyoe nodes[MAX];

In the case of a graph node,
      node[p] represents a graph node (header node)
      node[p].info give info field of header node
      node[p].point points to the list of arc nodes
      node[p].next points to next header node

In the case of an arc node,
      node[p] represents arc node
      node[p].info give info field of an arc node
      node[p].point points to the terminating header node of that arc node
      node[p].next points to next arc node

/*Routine to check for adjacency of two nodes p,q*/
void adjacent(int p, int q){
          int r;
          r = node[p].point;
          while(r >=0 ){
                 if(node[r].point == q){
                      return(TRUE);
                 }
                 else{
                     r = node[r].next;
                 }                 
          }
          return(FALSE);
}/*end adjacent