Training Material

## Basic Graph Algorithms

### Representing graphs

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:

• 1 → [2,3]
• 2 → [1,3]
• 3 → [1,2,4]
• 4 → 
• 5 → [6,7]
• 6 → [5,7]
• 7 → [5,6]

Which representation to use depends on the requirement.

• To visit all neighbours of a node, adjacency lists are more efficient since we don't have to skip over 0's as we do in the adjacency matrix.
• To answer a question of the form "Is (i,j) an edge in the graph", we have to scan the list of neighbours of i, which could be very large. In an adjacency matrix, we just have to check the value of A[i,j].

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] is the number of neighbours of i. The entries E[i],...,E[i][E[i]] 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 is 2, saying that node 6 has two neighbours. The actual neighbours are stored in E[ and E.

This is not a desirable implementation of adjacency lists for two reasons:

• It uses N2 space even when M is small.
• If we have to initialize this matrix, it takes N2 time.

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 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:

• An array of pointers, each pointing into a linked list. Entry i in the array points to the list of neighbours of i.
• C++ vectors.

Video lecture on Representation of graphs, NPTEL online course on Design and Analysis of Algorithms (Lecture slides)