Implementation of a graph with adjacency list in C

Question

I read a code implementing a graph with adjacency list. But I am so
confused about the addEdge function.

In the function of the following code, when the newNode->next is assigned
with array[src].head. That means the next node of newNode is
array[src].head. But after the statement"graph->array[src].head = newNode;", the order is the other way around as we test the result. Can someone explain to me? Thanks!

#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; 
}

MFisherKDX MFisherKDX · Accepted Answer · 2019-04-18T15:28:55

In the function of the following code, when the newNode->next is assigned with array[src].head. That means the next node of newNode is array[src].head. But after the statement graph->array[src].head = newNode;, the order is the other way around as we test the result. Can someone explain to me? Thanks!

This is correct. The function addEdge is inserting the new node at the beginning of the list, as you have confirmed from your test output.

This line:

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

makes the new node's next pointer point to the beginning of the current list (before the list is updated).

Then this line:

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

updates the beginning of the list to point to the new node you just added.

Now the list looks like:

[head == new-node] -> [... state of list before addEdge was called ...]

Implementation of a graph with adjacency list in C

1 Answers