The logic inside your insert_node()
function is completely wrong.
Assuming, you are building an undirected graph, if the user enters the pair i, j
, you have to push node i
to the adjacency list of j
and also node j
to that of node i
.
Another major mistake is, you are always appending the newly created node, which you denote by temp
to the first element of the adjacency list of the other node, which is true only in case the other node’s neighbors’ list was empty. You first have to check if(node_p[i] == NULL)
. If that is true, you can directly append the temp
to that node_p[i]
, otherwise you have to follow link
s to get to the last element of the adjacency list and append temp
there.
The modified code looks like this
void insert_node(graph **node_p,int i,int j)
{
/* Add j to adj list of i */
graph *temp;
temp=(graph *)malloc(sizeof(graph));
temp->data=j;
temp->link=NULL;
if(node_p[i] == NULL) /* First Node */
node_p[i]=temp;
else
{
graph *loc;
loc = node_p[i];
while(loc->link != NULL)
loc = loc->link;
loc->link = temp;
}
/*** COMMENT THIS PORTION IF THE GRAPH IS DIRECTED ***/
/* Add i to adj list of j */
graph *temp1;
temp1 = (graph *)malloc(sizeof(graph));
temp1->data = i;
temp1->link = NULL;
if(node_p[j] == NULL) /* First Node */
node_p[j]=temp1;
else
{
graph *loc;
loc = node_p[j];
while(loc->link != NULL)
loc = loc->link;
loc->link = temp1;
}
}
In case you are building a directed graph i.e, i -> j
and not j -> i
, comment out the second half of the code that says /* Add i to adj list of j */
.
Using this. I got this output on the following graph of 5 nodes whose edges are = {1-2, 1-5, 1-3, 2-4}
enter number of number of nodes in the graph5
enter option 1.create graph 2.display 3.exit 1
enter source and destination nodes 1 2
enter source and destination nodes 1 5
enter source and destination nodes 1 3
enter source and destination nodes 2 4
enter source and destination nodes 0 0
enter option 1.create graph 2.display 3.exit 2
the nodes adjacent to node 1 are= 2 5 3
the nodes adjacent to node 2 are= 1 4
the nodes adjacent to node 3 are= 1
the nodes adjacent to node 4 are= 2
the nodes adjacent to node 5 are= 1
enter option 1.create graph 2.display 3.exit3
CLICK HERE to find out more related problems solutions.