Graphs->Linked List Representation

Directed Graph	Linked List Representation

If there would have been an edge from A to B in the graph, in the linked list representation we would have an extra node B after or before D in the down list for A. You can understand from the above representation that there are two types of Lists - one to maintain the adjacency list of every vertex and the other one to maintain the graph. Accordingly, we have two types of List nodes - one which has that red coloured pointer and the other with the black colour pointer. Sorry, to use such a raw language to explain! You will realise the difference after I give you the respective NODE structures.  

Although there is no formal algorithm for the linked list representation, I am giving an informal one so that you understand its C implementation.

Algorithm:-
Step-1: Make the list that holds the graph, having all the vertices in the graph
Step-2: For every vertex in that list do the following - 
            a. find the adjacent vertices, if any
            b. add that vertex in the adjacency list for this current vertex  

Isn't it easy..

C implementation:-

struct adj_node  /*the NODE which forms the part of the adjacency list; look at figure [B]*/
{
char vertex_val;
struct adj_node *adj_next; /*red pointer*/
};

struct node /*the NODE which forms the part of the Graph; look at figure [A]*/
{
char vertex_val;
struct adj_node *down;
struct node *next;  /*black pointer*/
};

struct node *graph; 

LinkListrepresentation()
{
struct node *cur_vertex, *aux_ptr;
struct adj_node *adj_cur, *new;

/*Step-1 of the algorithm is expected from you or refer linked LISTS*/ 
/*Step-1 gives you a list, being pointed by 'graph' */ 

cur_vertex = graph;   /*first node of the graph in consideration*/
/*Step-2 starts here*/
while ( cur_vertex != NULL)
      {
       aux_ptr = graph; /*an auxiliary pointer to the graph*/
       adj_cur = NULL; /*an auxiliary pointer to keep track of the adjacency lists*/
       cur_vertex->down = adj_cur; 
       while (aux_ptr != NULL)
             {
              printf("Is there any edge between %c and %c ",aux_ptr->vertex_val, cur_vertex->vertex_val);
              scanf("%d", &edge);/*step-2: part-A*/
              if( edge == 1) /*step-2: part - B*/
                 if( adj_cur == NULL)
                   {
                    adj_cur = (struct adj_node *)malloc(sizeof(adj_node));
                    adj_cur ->vertex_val = aux_ptr->vertex_val;
                    adj_cur -> adj_next = NULL;
                   } 
                  else
                   {
                     new = (struct adj_node *)malloc(sizeof(adj_node));
                     new -> vertex_val = aux_ptr ->vertex_val;
                     adj_cur ->adj_next = new;
                     adj_cur = new; 
                     adj_cur ->adj_next = NULL;
                   }  
               aux_ptr = aux_ptr ->next;
             }
        cur_vertex = cur_vertex ->next;
     }
}

Note:- If you don't want to use aux_ptr, you can always maintain a Adjacency List for the graph and check it for every vertex, to find the respective adjacent edges.

Related Operations:
Concept --  non-directed, directed and weighted
Adjacency matrix of a Graph
Linked representation of a Graph
Traversals – Depth First & Breadth first Search
Transitive closure/ Warshall’s algorithm
Shortest Path Algorithm
Spanning Tree Algorithm