What is wrong in this code for graph?

Question

#include<stdio.h>

struct llist {
int data;
struct llist *next;
};

typedef struct llist list;

struct graph {
    int V;
    list **adj;
};

typedef struct graph graph;

graph* create_graph(int V) {
    list **adj = (list**)malloc(sizeof(list*)*V);
    graph *a = (graph*)malloc(sizeof(graph));
    a->V = V;
    a->adj = adj;
    return a;
}

void insert_list(list **head, int v) {
    list *new_node, *temp_node, *last_node;
    new_node = (list*)malloc(sizeof(list));
    new_node->data = v;
    new_node->next = NULL;
    printf("\n hi %d", head);
    /*
     * head is empty, point the head to temp and return.
     */

    if (*head == NULL) {
        *head = new_node;
        return;
    }

    temp_node = *head;

    do{
        last_node = temp_node;
        temp_node = temp_node->next;
    }while(temp_node);
    last_node->next = new_node;
}

void addedge(graph *g, int u, int v) {

    insert_list(&(g->adj[u]), v);

}


int
main() {
    int V = 10;
    graph *a = create_graph(V);
    printf("\n graph created");
    addedge(a, 1,2);
    addedge(a,1,5);
    addedge(a,2,1);
    addedge(a,2,5);
    addedge(a,2,3);
    addedge(a,2,4);
    addedge(a,3,2);
    addedge(a,3,4);
    addedge(a,4,2);
    addedge(a,4,5);
    addedge(a,4,3);
    addedge(a,5,4);
    addedge(a,5,1);
    addedge(a,5,2);
    return 0;
}

In this code, by printing messages, I have found is create_graph function executes properly and returns a graph. Then addedge is being called, In it, if(*head==NULL) part always returns false (Don't know why, first time it should return true). Then it goes ahead in do while loop and that keep executing till infinity and code terminates.

What I am trying to do is I have a structure called graph, with a integer variable V and array of linked list variable adj (represents adjacency list). And then create graph will initialise a graph variable and return it.

Addedge(V,u,v) will add edge v to u (means v is adjacent to u). so adj[0....V-1] is a array of linked list. so if edge 1 is adjacent to 2 and 3, then list will look like 1->2->3.

Comment If more info needed. I don't know what why *head is not null the first time and why the while loop never terminates.

Thanks a lot in advance.

Initialize all pointers to NULL before using any of them..I think this will solve your problem — Nullpointer, Apr 24 '14 at 13:57
@Nullpointer If that makes the problem go away, it only shows that there are bugs in the code. Get rid of the bugs by actually fixing them, not by hiding them under the carpet... — Lundin, Apr 24 '14 at 14:06
[Please don't cast the return value of `malloc()` in C](http://stackoverflow.com/a/605858/28169). — unwind, Apr 24 '14 at 14:18
@Lundin except that, quite often, the failure to initialize a pointer *is* the bug to begin with... — twalberg, Apr 24 '14 at 15:15

score 0 · Accepted Answer · answered Apr 24 '14 at 14:05

By trail and error, I found the mistake.

In function create graph, after initialising the list, each individual list also must be initialised to NUll, otherwise it will have junk stuff.

Below is correct code :

graph* create_graph(int V) {
    list **adj = (list**)malloc(sizeof(list*)*V);
    int i;
    for (i = 0; i < V; ++i) {
        adj[i] = NULL;
    }
    graph *a = (graph*)malloc(sizeof(graph));
    a->V = V;
    a->adj = adj;
    return a;
}

What is wrong in this code for graph?

1 Answers1