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);
}
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. - Lundingraph->adjList = malloc(sizeof(struct node *) * vertices);or equivalently (and better style)graph->adjList = malloc(sizeof(*graph->adjList) * vertices);. - Ian Abbott