What kind of storage method might save space when used on sparse graph? The edge in the graph consists of each vertex V i and its adjacent vertices. All adjacent vertices to each vertex V i constitute...

What kind of storage method might save space when used on sparse graph?

The edge in the graph consists of each vertex V_i
and its adjacent vertices. All adjacent vertices to each vertex V_i
constitute a linear list. Considering the general case for graphs, for any vertex V_i
, the number of adjacent vertices is uncertain. Therefore, we can choose singly linked list for storage, that is, construct a singly linked list for each vertex (when there are n vertices, then we construct n singly linked lists). The nodes in the ith singly linked list contain all the adjacent nodes of the vertex V_i
.

The remaining problem is how to organize these n linked lists together to facilitate the management.

In our experience, to manage n singly linked lists concurrently is to use “linked list representational method with row vector.” This storage structure also applies to the storage of graph and is called adjacency list.

Besides adjacency list, there are cross-linked list and adjacency multilist. Those two representational methods are relatively complex, and we do not describe them in detail here.