Coding adjacency list representing graph

Question

I want to write some basic code on graph like DFS, BFS but before that I am coding graph representation in adjacency list, and some basic functions like readgraphfrommatrix. (This will initialize graph from adjacency matrix which is easier to supply as input to test the program.)

A vertex can have some info like name (say name of town), an edge can have some info like weight.

Does below code look decent enough or there are more standard recognized code snippets for adjacency list representation of graphs?

struct edge
{
    char *data;
}

struct vertex 
{
    char *data;
};

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

struct graph
{
    int nvertex,nedges; //
    struct vertex **V; // in main, I will malloc depending on input to have sth like struct vertex V[nvertex];
    struct edge **E //to have like struct edge E[nedges];
    struct node **list ; // to have like struct node* list[nvertex];
}

Answer 1

Code style: Use typedef struct instead of struct for cleanliness.

This looks generally OK, but is not strictly speaking an adjacency list representation. In an adjacency list representation you store a list of verticies, and each of those verticies store a list of its neighbours. This structure implicitly encodes the edges of the graph.

A more compact adjacency representation might look something more like this:

typedef struct{
    char *data;
    struct vertex **neighbours;
    char **weight; // edge to neighbours[i] stored in weight[i] 
} vertex;

typedef struct{
    int num_verticies;
    struct vertex **V;
} graph;

The edges can be recovered by traversing the graph. To improve performance we may choose a structure other than a linked list to store the neighbours of a vertex.

Which further annotations you keep in the graph struct will depend on the final use case. For certain algorithm having an explicit edge list will be vital, whereas for others it will be wasteful.