[prev] 39 [next]

Adjacency List Representation (cont)

Implementation of edge insertion/removal (assuming VList ADT):

void insertE(Graph g, Edge e)
{
   assert(validG(g) && validE(g,e));
   int orig = length(g->edges[e.v]);
   g->edges[e.v] = insert(g->edges[e.v], e.w);
   g->edges[e.w] = insert(g->edges[e.w], e.v);
   if (length(g->edges[e.v]) > orig) g->nE++;
}
void removeE(Graph g, Edge e)
{
   assert(validG(g) && validE(g,e));
   int orig = length(g->edges[e.v]);
   g->edges[e.v] = delete(g->edges[e.v], e.w);
   g->edges[e.w] = delete(g->edges[e.w], e.v);
   if (length(g->edges[e.v]) < orig) g->nE--;
}