Thread: Graphs and Pointers on adjacency list Array

I have the following structure for Graphs:

Code:

#define MaxV 100
#define MaxE 50

typedef struct edge {
    int dest;
    int cost;

    struct edge *next;
} Edge, *Graph[MaxV];

This cannot be changed, it must remain exactly like it is above.

After a few hours I came up with the following code:

Code:

Graph *initGraph() {
    Graph *g = (Graph*)malloc(sizeof(Graph));

    for(int i = 0; i < MaxV; i++)
        (*g)[i] = NULL;

    return g;
}

int insertEdge(Graph *g, int o, int d, int c) {
    if(!g) return -1;

    Edge *edge = (Edge*)malloc(sizeof(Edge));

    edge->dest = d;
    edge->cost = c;

    edge->next = (*g)[o];
    (*g)[o] = edge;

    return 0;
}

int main(void) {
    Graph *g1 = initGraph();
    Edge *aux = NULL;

    insertEdge(g1, 0, 1, 2);
    insertEdge(g1, 0, 2, 3);
    insertEdge(g1, 1, 4, 5);
    insertEdge(g1, 2, 4, 1);
    insertEdge(g1, 4, 8, 6);

    for(int i = 0; i < MaxV; i++) {
        printf("[%02d]\n", i);

        for(aux = (*g1)[i]; aux != NULL; aux = aux->next)
            printf(" [%d] » [%d] (%d)\n", i, aux->dest, aux->cost);
    }

    return 0;
}

This seems to be working and Valgrind didn't report any reading/writing memory errors, I'm assuming I did everything alright but I need a second opinion.

Also, I couldn't find a different way other than (*g)[index] to solve that specific graph typedef, which cannot be changed. Is this the only way? Isn't there a way to simplify this?

Originally Posted by Nazgulled

Also, I couldn't find a different way other than (*g)[index] to solve that specific graph typedef, which cannot be changed. Is this the only way? Isn't there a way to simplify this?

Graph is a typedef for an array of MaxV pointers to struct edge objects. Since arrays are converted to pointers to their first elements when passed as an argument, you can avoid passing a pointer to the array, and just pass a pointer to the array's first element, e.g.,

Code:

void initGraph(Graph g) {
    for (int i = 0; i < MaxV; i++)
        g[i] = NULL;
}

int main(void) {
    Graph g1;
    initGraph(g1);
    /* ... */
}

If you do want to use malloc, then remember to use free.