Adjacency List for Graphs in C

Question

I'm having problems printing vertices when using Adjacency Lists. I want to get only the starting vertices, without the neighbours, but I get their addresses instead. So, I'm having an issue with pointers. Right now I don't get why it's not printing the correct output. My code is:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct ADI{
    int val;
    struct ADI *urm;
}ADI;

ADI *adjancencyList( int vertex )
{
  int neigh,i;
  ADI *head, *elem, *vec;
  head = ( ADI* ) malloc( sizeof( ADI ) );
  head->val = vertex;
  elem = head;
  printf( "Input number of neighbours:" );
  scanf( "%d", &neigh );
  for( i = 0; i < neigh ; i++)
    {   printf( "Neighbour:" );
        vec = ( ADI* ) malloc( sizeof( ADI ) );
        elem->urm = vec;
        scanf( "%d", &elem->val );
    }

  return head;
}
int main()
{   int i, n, v;
    printf("Input number of vertices ");
    scanf( "%d", &n );
    ADI *A = ( ADI* ) malloc( n * sizeof( ADI ) );

    for( i = 0; i < n; i++ )
    {
        printf( "Input vertex name:" );
        scanf( " %d ", &v );
        A = adjancencyList( v );
        A++;
    }

    A = &( A[0] );

    for( i = 0; i < n; i++ )
    {
     printf(" %d ", A->val  );
     printf( " \n " );
     A++;
    }
     return 0;

}

Please provide an example of the input, the expected output, and the actual output. — Scott Hunter, Jul 28 '16 at 14:03
Note that trailing spaces in `scanf()`-family format strings are diabolical if the input ever comes from a user rather than a file. The basic problem is that the `scanf()` function won't return until it comes across something that isn't a white space character after the actual input. — Jonathan Leffler, Jul 28 '16 at 14:11
Note: They say [you shouldn't cast the result of `malloc()` in C](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — MikeCAT, Jul 28 '16 at 14:11
In your `adjacencyList()` function, you are not properly initializing each allocated adjacent node, and you are not linking them into a list properly. In fact, you're leaking all but the last node allocated. This leads to profoundly 'undefined behaviour' and anything is possible after you use undefined behaviour. — Jonathan Leffler, Jul 28 '16 at 14:14

score 1 · Accepted Answer · edited May 23 '17 at 11:44

1

Your program is causing memory leak. You should use an array of ADI*, not an array of ADI, to store what is returned from adjancencyList(). Using subscripting looks better than incrementing in this case. One more tips is that A = &( A[0] ); does virtually nothing.

Also note that they say you shouldn't cast the result of malloc() in C.

Try this:

int main(void)
{
    int i, n, v;
    printf("Input number of vertices ");
    scanf( "%d", &n );
    ADI **A = malloc( n * sizeof( ADI* ) );

    for( i = 0; i < n; i++ )
    {
        printf( "Input vertex name:" );
        scanf( " %d ", &v );
        A[i] = adjancencyList( v );
    }

    for( i = 0; i < n; i++ )
    {
        printf(" %d ", A[i]->val  );
        printf( " \n " );
    }
     return 0;

}

edited May 23 '17 at 11:44

Community

1
1

answered Jul 28 '16 at 14:16

MikeCAT

73,922
11
45
70

Thanks for the answer! From what I read I expected the use of double pointers was needed. Can you please explain why is that the correct form? Am I not pointing to the first address of my vector? Also, I used A= &(A[0]) so I was at that first address again, after the end of the for. – Alex Postolache Jul 29 '16 at 09:18
@AlexPostolache This usage of `A` in `main()` is correct (your `adjancencyList()` is also wrong as pointed out by @JonathanLeffler ) because the type of `A` suits for type of elements (`ADI*`). Your `A` *was* pointinag at what is allocated via `malloc()`, but it is overwritten by the assignment `A = adjancencyList( v );`. `A= &(A[0])` is equivalent to `A= &(*(A+0)`, which is equivalent to `A=&*A`, which is equivalent to `A=A`, which has no effort. – MikeCAT Jul 31 '16 at 08:18

Adjacency List for Graphs in C

1 Answers1