Suppose we have 7 nodes 1,2,...,7 and the list of neighbours are given by {(1,2),(1,3),(2,3),(3,4),(5,6),(7,6),(5,7}. If we draw this as a picture, we have the following.
2 / \ / \ 1 --------- 3 -------- 4 5 --------- 6 \ / \ / 7
We can represent the structure of a graph as an "adjacency matrix" A with 7 rows and columns (in general, n rows and n columns, where the number of nodes in the graph is n). The entry A[i,j] = 1 if nodes i and j are neighbours, and is 0 otherwise.
For the example above, the adjacency matrix is
0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0
For a weighted graph, we set A[i,j] to be the weight of the edge (i,j) rather than just 1 or 0.
If we want to visit all the neighbours of node i, we scan row i from left to right and select all non-zero entries. In general, to check the neighbours of a node, we have to scan n entries, independent of the degree of the node.
If the graph has relatively few edges, we can use a different representation.
In this representation, for each node we explicitly maintain a list of all its neighbouras. For example, the graph with edges {(1,2),(1,3),(2,3),(3,4),(5,6),(7,6),(5,7}, is represented as:
Which representation to use depends on the requirement.
Storing adjacency lists
A node can have at most N-1 neighbours. For simplicity, we could represent an adjacency list as a two dimensional array E of size [1..N]×[0..N-1]. Row i lists the neighbours of node i. E[i][0] is the number of neighbours of i. The entries E[i][1],...,E[i][E[i][0]] list out the actual neighbours.
0 1 2 3 4 5 6 1) 2 2 3 x x x x 2) 2 1 3 x x x x 3) 3 1 2 4 x x x 4) 1 3 x x x x x 5) 2 6 7 x x x x 6) 2 5 7 x x x x 7) 7 5 6 x x x x
For instance, E[6][0] is 2, saying that node 6 has two neighbours. The actual neighbours are stored in E[6][[1] and E[6][2].
This is not a desirable implementation of adjacency lists for two reasons:
A more efficient option is to maintain two linear arrays.
Offset Neighbours 1 1 --------------> 2 2 3 ------------ 3 3 5 ---------- |-> 1 4 9 -------- | 3 5 10 ------ | |---> 1 6 12 ---- | | 2 7 14 -- | | | 4 | | | | 6 | | | -----> 3 | | -------> 6 | | 7 | ---------> 5 | 7 -----------> 5 6
Offset[i] stores the position in Neighbours where the neighbours of vertex i begin. To examine all neighbours of vertex i, scan Neighbours[Offset[i]], Neighbours[Offset[i]]+1, … Neighbours[Offset[i+1]]-1.
Note, however, that adding edges in this representation is complicated.
Another way is to represent the list of neighbours using two arrays as follows. Here, each neighbour points (via "Next") to the next neighbour, until the last neighbour which has Next = -1.
Offset Node Next 1 1 --------------> 2 2 2 3 ------------ 3 -1 3 5 ---------- |-> 1 4 4 9 -------- | 3 -1 5 10 ------ | |---> 1 6 6 12 ---- | | 2 7 7 14 -- | | | 4 8 | | | | 6 9 | | | -----> 3 -1 | | -------> 6 11 | | 7 -1 | ---------> 5 13 | 7 -1 -----------> 5 15 6 -1
Suppose we now add a new neighbour to 2, say 7. We append (7,-1) to the arrays (Node,Next) and modify the -1 entry in Next[4] to point to the new position, 17.
Offset Node Next 1 1 --------------> 2 2 2 3 ------------ 3 -1 3 5 ---------- |-> 1 4 4 9 -------- | 3 17 <--- Points to new nbr of 2 5 10 ------ | |---> 1 6 6 12 ---- | | 2 7 7 14 -- | | | 4 8 | | | | 6 9 | | | -----> 3 -1 | | -------> 6 11 | | 7 -1 | ---------> 5 13 | 7 -1 -----------> 5 15 6 -1 7 -1
You can also use more complicated data structures to represent adjacency lists, if you are comfortable with them:
Video lecture on Representation of graphs, NPTEL online course on Design and Analysis of Algorithms (Lecture slides)
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky