Preferred when graphs are not dense, where we keep track of all vertices connected to each vertex on a linked list that is associated with that vertex. We maintain a vector of lists so that, given a vertex, we can immediately access its list; we use linked lists so that we can add new edges in constant time.
Graph ADT implementation (adjacency lists)
class SparseMultiGRAPH
{
int Vcnt, Ecnt; bool digraph;
struct node
{
int v; node* next;
node(int x, node* t){ v = x; next = t; }
};
typedef node* link;
vector<link> adj;
public:
SparseMultiGRAPH(int V, bool digraph = false):
adj(V), Vcnt(V), Ecnt(0), digraph(digraph)
{ adj.assign(V,0);}
int V() const { return Vcnt; }
int E() const { return Ecnt; }
bool directed() const { return digraph; }
void insert(Edge e)
{
int v = e.v , w = e.w;
adj[v] = new node(w, adj[v]);
if(!digraph) adj[w] = new node(v,adj[w]);
}
void remove(Edge e);
bool edge(int v,int w) const;
class adjIterator;
friend class adjIterator;
};
Iterator for adjacency-lists representation
class SparseMultiGRAPH::adjIterator
{
const SparseMultiGRAPH &G;
int v;
link t;
public:
adjIterator(const SparseMultiGRAPH &G, int v):
G(G), v(v) { t= 0; }
int begin()
{ t= G.adj[v]; return t? t->v : -1;}
int nxt()
{if(t) t = t->next; return t ? t->v : -1;}
bool end()
{ return t == 0; }
};
It builds multigraph. Checking duplicate edges in the adjacency-lists structure would necessitate searching through the lists and could take time proportional to $V$ same can be said about remove edge function.
This graph is undesirable if there is heavy use of remove edge or of existence tests.
Isomorphism problem still persists. Adjacency-list structure determines how our various algorithms see the graph. Although a algorithm should produce correct answers no matter how the edges are ordered on adjacency list.
Primary advantage is space-efficient structure while disadvantage is time proportional to $V$ for removing a specific edges.