I'm trying to create a directed random graph and using the code in Robert Sedgewick's Algorithms book. Whilst the code is working I am having trouble understanding how to use adjacency lists in particular the GraphinsertE function below. I have an idea in my head as to how it is working but when I try to follow the code I get confused with the pointer to pointers. I am trying to understand what happens with just 3 nodes A,B and C and what happens when I insert an edge between A and B, and then A and C. If anyone could talk me through this it would really help. Here is the code. I'm new to the board so hope I have done this right.
Code:
typedef struct { int v; int w; } Edge;
typedef struct graph *Graph;
typedef struct node *link;
struct node { int v; link next; };
struct graph { int V; int E; link *adj; };
link NEW(int v, link next)
{
link x = malloc(sizeof *x);
assert(x != NULL);
x->v = v; x->next = next;
return x;
}
Graph GRAPHinit(int V)
{
int v;
Graph G = malloc(sizeof *G);
G->V = V; G->E = 0;
G->adj = malloc(V*sizeof(link));
for (v = 0; v < V; v++) G->adj[v] = NULL;
return G;
}
void GRAPHinsertE(Graph G, Edge e)
{
int v = e.v, w = e.w;
G->adj[v] = NEW(w, G->adj[v]);
G->E++;
}
Edge EDGE(int a1, int a2)
{
Edge r;
r.v = a1;
r.w = a2;
return r;
}
The bit I then need to understand is how
Code:
GRAPHinsertE(G,EDGE(i,j));
would be working.