0
votes

I don't understand why I need double pointers inside 'struct graph'. Is it because it allows me to access one of the nodes that I made inside the function makeGraph()?

If I use one pointer (struct node *adjList) then I can't set the nodes to NULL that I made inside makeGraph().

I got the code frome programiz.com and in the article that explains this code it says: Don't let the struct node** adjList overwhelm you. All we are saying is we want to store a pointer to struct node*. This is because we don't know how many vertices the graph will have and so we cannot create an array of Linked Lists at compile time.

If I do: graph->adjList[1] does it go to the address of the second node or goes it inside the node? (I'm talking about the nodes that I create inside makeGraph())

I understand the rest of the code. If anyone can help me it would be appreciated.

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

struct node
{
    int vertex;
    struct node *next;
};

struct graph
{
    int numVertices;
    struct node **adjList; // <--- THIS ONE
};

struct graph *makeGraph(int vertices) // Creating a Graph
{
    struct graph *graph = malloc(sizeof(struct graph));
    graph->numVertices = vertices;
    graph->adjList = malloc(sizeof(struct node) * vertices); // creating the nodes

    for (int i = 0; i < vertices; i++)
        graph->adjList[i] = NULL; // Setting all nodes to NULL

    return graph;
}

void addEdge(struct graph *graph, int src, int dest) // Add Edge
{
        struct node *newNode = makeNode(dest);
        newNode->next = graph->adjList[src];
        graph->adjList[src] = newNode;

        struct node *newNode2 = makeNode(src);
        newNode2->next = graph->adjList[dest];
        graph->adjList[dest] = newNode2;
        return;

int main()
{
    struct graph *graph1 = makeGraph(4);
    addEdge(graph1, 0, 1);
    addEdge(graph1, 0, 2);
    addEdge(graph1, 0, 3);
}
It's a dynamically allocated array of pointers. - 500 - Internal Server Error
If you don't understand why, then you probably don't need them. I see no obvious need for them here, looks like obfuscation. They could seemingly as well have allocated an array of structs with struct node * and a single malloc call. Perhaps they did it this way to enable faster swapping between edges? Swapping pointers is faster than hard copy of structs. Though on the other hand, malloc overhead and fragmentation is slow too. - Lundin
struct node ** adjList is an array of pointers of struct node, just like int *arr represents an array of integers. g->adjList[1] represents the second element of the array and it is a pointer to a struct node that is adjacent to the current node in the graph according to the general definition. - susanth29
You are allocating the wrong size memory block for the adjacency list. It should be graph->adjList = malloc(sizeof(struct node *) * vertices); or equivalently (and better style) graph->adjList = malloc(sizeof(*graph->adjList) * vertices);. - Ian Abbott
You already quoted the explanation given by the site where you got the code. What about that don't you understand? - John Bollinger