malloc gets memory corruption, when I increase the number of nodes from 4 to anything greater than 5 in a graph

Question

I've written a simple code for printing a graph given the edges, and I am using structs to store the data in graphs, it works well when the number of nodes is less than 5 but anything greater than 5 brings a malloc error, I do not know why as to this is happening, can someone point out what I am doing wrong.

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

// Define maximum number of vertices in the graph

#define N 5
//#define N 4 //use this when the nodes are less than 5 

// Data structure to store graph
struct Graph {
    // An array of pointers to Node to represent adjacency list
    struct Node *head[N];
};

// A data structure to store adjacency list nodes of the graph
struct Node {
    int dest;
    struct Node *next;
};

// data structure to store graph edges
struct Edge {
    int src, dest;
};

// Function to create an adjacency list from specified edges
struct Graph *createGraph(struct Edge edges[], int n) {
    unsigned i;

    // allocate memory for graph data structure
    struct Graph *graph = (struct Graph *)malloc(sizeof(struct Graph));

    // initialize head pointer for all vertices
    for (i = 0; i < n; i++)
        graph->head[i] = NULL;

    // add edges to the directed graph one by one
    for (i = 0; i < n; i++) {
        // get source and destination vertex
        int src = edges[i].src;
        int dest = edges[i].dest;

        // allocate new node of Adjacency List from src to dest
        // error occurs over here and does not move forward when the number of nodes are greater than 5
        struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
        newNode->dest = src;

        // point new node to current head
        newNode->next = graph->head[dest];

        // point head pointer to new node
        graph->head[dest] = newNode;
    }
    return graph;
}

// Function to print adjacency list representation of graph
void printGraph(struct Graph *graph) {
    int i;
    for (i = 0; i < N; i++) {
        // print current vertex and all ts neighbors
        printf("for node %d\n", i);
        struct Node *ptr = graph->head[i];
        while (ptr != NULL) {
            printf("(%d -> %d)\t", i, ptr->dest);
            ptr = ptr->next;
        }
        printf("\n");
    }
}

// Directed Graph Implementation in C
int main(void) {
    // input array containing edges of the graph (as per above diagram)
    // (x, y) pair in the array represents an edge from x to y
    // when the nodes are 5 or more use this 
    struct Edge edges[] = {
        { 3, 0 }, { 3, 1 }, { 3, 2 }, { 1, 0 },
        { 1, 2 }, { 4, 1 }, { 4, 3 }
    };

    //when the nodes are 4 use this below
    // struct Edge edges[] = {
    //     { 3, 0 }, { 3, 1 }, { 3, 2 }, { 1, 0 },
    //     { 1, 2 }
    // };

    // calculate number of edges
    int n = sizeof(edges) / sizeof(edges[0]);
    printf("%d\n",n );
    // construct graph from given edges
    struct Graph *graph = createGraph(edges, n);

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

    return 0;
} 

the error that I get when using nodes greater than 4 at:

struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));

is as follows:

malloc(): memory corruption aborted (core dumped)

Answer 1

In your code, you allocate in Graph an array of 4 Node pointers called head.

// Data structure to store graph
struct Graph {
    // An array of pointers to Node to represent adjacency list
    struct Node* head[N];
};

later on you are touching memory which is not yours by initializing out of bounds:

   // initialize head pointer for all vertices
for (i = 0; i < n; i++)
    graph->head[i] = NULL;

Using valgrind:

=16498== Invalid write of size 8
==16498==    at 0x400653: createGraph (a.c:37)
==16498==    by 0x400815: main (a.c:103)
==16498==  Address 0x52044a0 is 0 bytes after a block of size 32 alloc'd
==16498==    at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==16498==    by 0x40063E: createGraph (a.c:33)
==16498==    by 0x400815: main (a.c:103)