Implementing a graph with adjacency list in C

Question

I am now learning graph, when I read about implementing graph with adjacency list from online teaching source, I was confused about the addEdge function.

When addEdge(graph, 0, 1) is executed, the node with 1 value is created, and then newNode->next is assigned with graph->array[0].head which is NULL. After that, graph->array[0].head is assigned with the newNode. Then node 0 and 1 are connected, in the next half of the function, it goes the other way around. I don't know how this approach connects the the two nodes.

Can someone explain to me?

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

// A structure to represent an adjacency list node 
struct AdjListNode 
{ 
    int dest; 
    struct AdjListNode* next; 
}; 

// A structure to represent an adjacency list 
struct AdjList 
{ 
    struct AdjListNode *head;  
}; 

// A structure to represent a graph. A graph 
// is an array of adjacency lists. 
// Size of array will be V (number of vertices  
// in graph) 
struct Graph 
{ 
    int V; 
    struct AdjList* array; 
}; 

// A utility function to create a new adjacency list node 
struct AdjListNode* newAdjListNode(int dest) 
{ 
    struct AdjListNode* newNode = 
     (struct AdjListNode*) malloc(sizeof(struct AdjListNode)); 
    newNode->dest = dest; 
    newNode->next = NULL; 
    return newNode; 
} 

// A utility function that creates a graph of V vertices 
struct Graph* createGraph(int V) 
{ 
    struct Graph* graph =  
        (struct Graph*) malloc(sizeof(struct Graph)); 
    graph->V = V; 

    // Create an array of adjacency lists.  Size of  
    // array will be V 
    graph->array =  
      (struct AdjList*) malloc(V * sizeof(struct AdjList)); 

    // Initialize each adjacency list as empty by  
    // making head as NULL 
    int i; 
    for (i = 0; i < V; ++i) 
        graph->array[i].head = NULL; 

    return graph; 
} 

// Adds an edge to an undirected graph 
void addEdge(struct Graph* graph, int src, int dest) 
{ 
    // Add an edge from src to dest.  A new node is  
    // added to the adjacency list of src.  The node 
    // is added at the begining 
    struct AdjListNode* newNode = newAdjListNode(dest); 
    newNode->next = graph->array[src].head; 
    graph->array[src].head = newNode; 

    // Since graph is undirected, add an edge from 
    // dest to src also 
    newNode = newAdjListNode(src); 
    newNode->next = graph->array[dest].head; 
    graph->array[dest].head = newNode; 
} 

// A utility function to print the adjacency list  
// representation of graph 
void printGraph(struct Graph* graph) 
{ 
    int v; 
    for (v = 0; v < graph->V; ++v) 
    { 
        struct AdjListNode* pCrawl = graph->array[v].head; 
        printf("\n Adjacency list of vertex %d\n head ", v); 
        while (pCrawl) 
        { 
            printf("-> %d", pCrawl->dest); 
            pCrawl = pCrawl->next; 
        } 
        printf("\n"); 
    } 
} 

// Driver program to test above functions 
int main() 
{ 
    // create the graph given in above fugure 
    int V = 5; 
    struct Graph* graph = createGraph(V); 
    addEdge(graph, 0, 1); 
    addEdge(graph, 0, 4); 
    addEdge(graph, 1, 2); 
    addEdge(graph, 1, 3); 
    addEdge(graph, 1, 4); 
    addEdge(graph, 2, 3); 
    addEdge(graph, 3, 4); 

    // print the adjacency list representation of the above graph 
    printGraph(graph); 

    return 0; 
}

Answer 1

Look its Very simple You're Not Actually Linking One Node To Other Node You're Just Creating a List Which is Containing That this Element is Connected to That Element

More explanation :--

Calling

addEdge(graph, 0,1);

then This Function is Creating a Simple Node of Name (dest)

struct AdjListNode* newNode = newAdjListNode(dest);

and as the node Created You First Assigned next ptr of newNode to the Source('src') Node

newNode->next = graph->array[src].head; 

And after that You assigned SrcNode to newNode(Very Same Way We use to swap Elements)

graph->array[src].head = newNode; 

Until Now You have already Linked Both Src And Dest Nodes ( But Only One Way).

Now Repeat The Above Process from Dest to Src For Making it A Two Way Path.

Explanation2 :--

addEdge(graph, 0, 1); 

After This One Lines Comment everything and Add

printf(" %d \n",graph->array[0].head->dest);
printf(" %d \n",graph->array[1].head->dest);

First Will Output 1 Second Will Output 0

Even While Traversing In BFS Or DFS or another Way we will be needing the list we don't actually need to Connect Them..'

Hope You Understood!!!! Please Correct Me If am Wrong..🤗🤗🤗🤗

Answer 2

You may like to refer this other approach too :

//WAP to represent an un-directed graph using Adjacency List.
#include<stdio.h>
#include<stdlib.h>
struct ListNode
{
  int vertexNo;
  struct ListNode* next;
};
struct Graph
{
 int V;
 int E;
 struct ListNode** Adj;
};

struct ListNode* createNode(int v) 
{
  struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
  newNode->vertexNo = v;
  newNode->next = NULL;
  return newNode;
}

void insertNode_atEnd(struct ListNode **start, int val)   //Insert a node with vertexNo=val at end of SLL
{
 struct ListNode *temp,*t;
 temp=createNode(val);
 if(*start == NULL)
  *start = temp;
 else
 {
  t=*start;
  
  while(t->next!=NULL)
   t=t->next;
   
  t->next=temp;
 }
}

void viewList(struct ListNode **start)
{
 struct ListNode *t;
 if(*start ==NULL)
  printf("Isolated Vertex");
 else
 {
  t=*start;
  while(t!=NULL) 
  {
   printf("%d\t",t->vertexNo);
   t=t->next;    
  }
 }
}

struct Graph *createGraph(int V,int E)
{
 struct Graph *G = (struct Graph*)malloc(sizeof(struct Graph));
 if(!G)
 {
  printf("Memory Error");
  return NULL;
 }
 G->V = V;
 G->E = E;
 G->Adj = (struct ListNode**)malloc((G->V)*sizeof(struct ListNode));
 
 for(int i=0;i<G->V;i++)
  {
    G->Adj[i] = NULL;
  }
  return G;
}

void adjMatrixOfGraph(struct Graph *G)
{
  int u,v;
     printf("Enter node no. in a pair that connects an edge");
     for(int i=0;i<G->E;i++)
     {
      scanf("%d %d" , &u,&v); 
      insertNode_atEnd(&(G->Adj[u]),v); 
      insertNode_atEnd(&(G->Adj[v]),u); //for undirected graph only
     }
     
     printf("ADJACENCY LIST :\n");
     printf("VERTEX NO.\t CONNECTED NODES\n");
     for(int i=0;i<G->V;i++)
     {
       printf("%d\t\t",i);
       viewList( &(G->Adj[i]) );
       printf("\n");
     }
     
}

int main()
{
 int V,E;  
 printf("Enter no. of nodes & no. of edges");
 scanf("%d%d",&V,&E);
 struct Graph *G = createGraph(V,E);
 adjMatrixOfGraph(G);
 return 0;
}