Graph as adjacency List

Adjacency list of a graph ( here undirected graph) is another way to represent other than matrix representation.

Graph Adjacency List Representation in C

  • From above figure it clear that adjacency list representation of undirected graph require linked list data structure.  Hence let us first finalized  our data structure.

In the figure there are 5 nodes or vertices. according to graph vertex 1 will have the list of (2,3,4) , vertex 2 will have list     (1,5),vertex 3 will have list (4,1), vertex 4 will have list (1,3) and vertex 5 will have list(2,4). this implies same for all vertices. This also shows that one node points two more than one nodes.

#include <stdio.h>
#include <stdlib.h>

#define maxNode 6 //0 : dummy

typedef struct Node {
       int vertexNum;
       struct Node *next;
} Node;

typedef struct List{
           Node *head;
} List;

List *adjlist[maxNode] = { 0 };
void printList(void);
void addNode(int source, int destination);
void freemem(void);

int main(void){
        int i;
        for (i = 1; i <= maxNode; i++){
           adjlist[i] = (List *)malloc(sizeof(List));
           adjlist[i]->head = NULL;
         }
    addNode (1, 2);
    addNode (1, 3);
    addNode (1, 4);
addNode (2, 1);
addNode (2, 5);
addNode (3, 4);
               addNode (3, 1);
               addNode (4, 1);
               addNode (4, 3);
addNode (5, 2);
addNode (5, 4);

printList();
//deallocate
freemem();
return 0;
}

void addNode(int s, int d)
{
     if(adjlist[s]->head == NULL){
        Node *src = (Node *)malloc(sizeof(Node));
        src->vertexNum = s;
        src->next = NULL;
        adjlist[s]->head = src;
     }

     Node *dest = (Node *)malloc(sizeof(Node));
     dest->vertexNum = d;
     dest->next = NULL;
     Node *tmp = adjlist[s]->head;

     while (tmp->next != NULL)
     tmp = tmp->next;

     tmp->next = dest;
}

void printList(void){
   int i;
   for (i = 1; i < maxNode; ++i){
     Node *p = adjlist[i]->head;
     printf ("Adjacency list for vetex %d\n", i);//adjlist[i]->n ?
     while (p){
        printf ("%d ", p->vertexNum);
         p = p->next;
     }
      printf ("\n");
    }
}
void freemem(void){
   int i;
   for (i = 1; i <= maxNode; ++i){
   Node *p = adjlist[i]->head;
   while (p){
   p = p->next;
   free(p);
}
free(p);
}
}



Related Contents to follow