1.2.3 Adjacency lists

Next: 1.2.4 Node-arc matrix Up: 1.2 Various representations of Previous: 1.2.2 Tail head

1.2.3 Adjacency lists

Another interesting representation often used by algorithms is the adjacency lists representation. It uses three row vectors, lp, ls and la. If n is the number of nodes and m is the number of arcs of the graph:
lp is the pointer array (size = n+1)
ls is the node array (size = m)
la is the arc array (size = m).
If the graph is undirected, each edge corresponds to two arcs.

With this type of representation, it is easy to know the successors of a node. Node number i has lp(i+1)-lp(i) successors nodes with numbers from ls(lp(i)) to ls(lp(i+1)-1), the corresponding arcs are have numbers from la(lp(i)) to la(lp(i+1)-1).

The adjacency lists representation of the graph of figure 1 is given below:

$\begin{picture}(0,0)% \epsfig{file=foo_adj.pstex} % \end{picture}$
#1#2#3#4#5 @font#1#2pt #3#4#5
$\begin{picture}(1770,1725)(953,-1883) \put(953,-1764){\makebox(0,0)[lb]{\smash{\... ...\SetFigFont{12}{14.4}{\familydefault}{\mddefault}{\updefault}lp}}} \end{picture}$

The function used to compute the adjacency list representation of a graph is adj_lists.

Next: 1.2.4 Node-arc matrix Up: 1.2 Various representations of Previous: 1.2.2 Tail head

Scilab Group