Difficulty in understanding the implementation of graphs using Linked Lists

Question

I am reading a book on Algorithms which has following code. I am having difficulty in understanding some lines here.

I have shown my doubt lines in the following code as DOUBT LINE 1 and DOUBT LINE 2. I have also commented a line as REFERENCE where I am having difficulty to comprehend. Please elaborate about the DOUBT LINE 1 and DOUBT LINE 2.

#define MAXV        100     /* maximum number of vertices */
#define NULL        0       /* null pointer */

/*  DFS edge types      */

#define TREE        0       /* tree edge */
#define BACK        1       /* back edge */
#define CROSS       2       /* cross edge */
#define FORWARD     3       /* forward edge */

typedef struct edgenode {
    int y;              /* adjancency info */
    int weight;         /* edge weight, if any */
    struct edgenode *next;      /* next edge in list */
} edgenode;

typedef struct {
    edgenode *edges[MAXV+1];    /* adjacency info */       //REFERENCE 
    int degree[MAXV+1];     /* outdegree of each vertex */
    int nvertices;          /* number of vertices in the graph */
    int nedges;         /* number of edges in the graph */
    int directed;           /* is the graph directed? */
} graph;

it is graph.h header and there it is also read and insert functions.

read_graph(graph *g, bool directed)
{
    int i;              /* counter */
    int m;              /* number of edges */
    int x, y;           /* vertices in edge (x,y) */

    initialize_graph(g, directed);

    scanf("%d %d",&(g->nvertices),&m);

    for (i=1; i<=m; i++) {
        scanf("%d %d",&x,&y);
        insert_edge(g,x,y,directed);
    }
}

insert_edge(graph *g, int x, int y, bool directed)
{
    edgenode *p;            /* temporary pointer */

    p = malloc(sizeof(edgenode));   /* allocate storage for edgenode */

    p->weight = NULL;
    p->y = y;
    p->next = g->edges[x]; //DOUBT LINE1

    g->edges[x] = p;        /* insert at head of list */ //DOUBT LINE 2

    g->degree[x] ++;        

    if (directed == FALSE)
        insert_edge(g,y,x,TRUE);
    else
        g->nedges ++;
}

Answer 1

Each vertex holds a set of edges. We can regard the set as unordered. At all times outside of the mutator functions, the pointer g->edges[i] points to the first edgenode incident on the ith vertex, or NULL otherwise. Then, the next links in the edgenode point to other edges in the set, transitively.

So, to add an edge, you first create a new edge, then assign it's next pointer the currently "first" node (DOUBT LINE 1), then assign the g->edges[i] pointer the newly created value (DOUBT LINE 2).

Notice that the conditions I said need to exist above are both still satisfied, although the order of the nodes has changed - what was "previously" first is now second, and the new node is first. That's OK, because we're just storing a set - the order does not matter.

Before (=> traverses a 'next' link):

   // edges[i] == <previous> => <other stuff>...

After:

   //         *             *    These asterisks are above what we set...
   //edges[i] == <new node> => <previous> => <other stuff>

Answer 2

Linked list means that next is a pointer to the following node. Example:
a {some_data,pointer_to_b}
b {some_data,pointer_to_c}
When you want to insert node, you must change next pointer of previous node to new node and set new node's next pointer to address of following node. Example:
a {some_data,pointer_to_d/*what is done at doubt line 1*/}
d {some_data,pointer_to_b} //inserted node what is done at doubt line 2
b {some_data,pointer_to_c}

Answer 3

Let's dissect so that you understand everything clearly.

The structure of the graph

1o-->2o-->#
2o-->3o-->#
3o-->#
4o-->#
5o--.#

Here

 `1o`: The node 1

 `-->`: It denotes a directed edge.

 `#`: denotes `NULL`

Now let's add 2-->4 edge having weight = 5

Step-1: p = malloc(sizeof(edgenode));

p-------->[ ]   ( This is the allocated node)

Step-2: p->weight = NULL; // it should be the weight of the edge p->y = y;

| wieght = 5 |
| y = 4      |
| next       |

step-3: p->next = g->edges[x]; g->edges[2] is a pointer to 3o

| wieght = w |
| y = 4      |
| next =------------>3o

Now the picture is

1o-->2o--->#

p[]--+
     |
     V
2o-->3o--->#
3o-->#
4o-->#
5o--.#

step-4: g->edges[2]=p g->edges[2] is basically 2o

1o-->2o--->#
2o-->[] --> 3o--->#
3o-->#
4o-->#
5o-->#

Simply

1o-->2o--->#
2o-->4o--->3o--->#
3o-->#
4o-->#
5o-->#

Explanation:

Basically here we are maintaining a list where for each node x we put y , z, if there is an edge x->y and x->z.

If we look into the implementation we will see the nodes are added in front.

For example..if we add x->y then the edge list will look like

x---->y

Now add z.

x---->z---->y

That's all...a friendly tips when you don't get a code get a pencil and paper try to dry run or it or sometimes simply run a debugger.