can't undertand double pointer to structure

general
, , , ,
1

Hello so I’m trying to implement graph data structure in c++ with adjacency list. I am using structures for that.

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

struct Graph{
int vertex;
node**adj;  //for storing head pointers of adjacency list
};

Now here how do I allocate memory dynamically for storing V(vertex) no. of head pointers of adjacency lists in adj(of graph structure). I tried something like

graph*g=new graph();
*(g->adj)=new node*[v]; //v is no of vertices

But I think its wrong.
And also how to access this adj(of graph)?
I tried like this for adding an edge between two vertex.

temp->next=*(g->adj[src]) //here temp is newly created node pointer and g is a graph pointer.
*(g->adj[src])=temp;      //src is the source vertex

I think the syntax is incorrect.
Please help.

2

Look if you want to implement adjacency list you can use array of pointers instead of **adj. This is because when you implement a graph by adjacency list you have to make head nodes and then pointer in the strucutre of nodes should point to its adjacent elements. Agree?
In that case there will be two structures one for nodes made overall and another for those nodes which are adjacent. For eg:

1 -4-3
2 -1-3
3 -4-2
4 -2-1

This is a random representation. So for first column, you need a different structure and for rest you need different. So instead of having all this why not make an array of pointers for first column. In this way you have to make only one structure.
There are different methods for implementing it. It might be possible that you didn’t get this one but atleast you can try.This might help you—> Graph and its representations - GeeksforGeeks
Hope it Helps :slight_smile:

EDIT: In case you think why i said that there will be two structures because since you have taken **adj so you have to manually link nodes 1 2 3 4 in this example and also these nodes are pointing to adjacent nodes so for this structure there are two pointers and for those adjacent nodes there is a single pointer as you can see 4-3,1-3,4-2…

3

This one is the correct approach:

graph* g = new graph();
g->adj = new node*[v];
for (int src = 0; src < v; ++src) {
    node *head = g->adj[src] = new node(); // allocate the head
    head->src = src;
}

since new node*[v] is of type node**, which is also the type of g->adj. But that syntax merely allocates an array of pointers, so you have to properly allocate each head as well. Pointers are unallocated by default, after all. Hope that is clear.

3 Likes
4

I was about to say the same thing. Here is a small working demo: link.
Although, @amartya_k, usually working with library containers is the better choice compared to implementing your own linked list.

2 Likes
5

Thanks everyone. This really helped me alot. I also asked this question on stack overflow but none of the guys could understand it. I was really surprised to see that and they flagged my question.
@meooow I know the vector implementation but I just wanted to try the native way first because I believe that’s good for understanding when you are a beginner. :slight_smile:

6

@amartya_k, agreed :slight_smile: