# Graph data structure using matrices

Published on October 28, 2021 graph implementationRepresenting *graphs*
with *matrices*.
*Graphs*, in their simplest form, are used to show
relationships between data.

We will represent relationships by creating a table that has an
**n** number of columns and rows. Column
**n** corresponds to row **n**, so that
we can get the relationship between two nodes like we would access
a nested array.

```
A(n = 1) -> B(n = 2)
relationship = table[1][2]
```

The number **one** will represent the presence of
an relationship and the number **zero** will represent
the absence. Now let’s create a graph composed of 3 *nodes*:
*A*, *B* and *C*. We will create a table with
three columns and three rows, each one with the name of the
corresponding node. Set the value of all 3^{2} cells to
**zero**, because currently, we have no
relationships.

- | A | B | C |
---|---|---|---|

A | 0 | 0 | 0 |

B | 0 | 0 | 0 |

C | 0 | 0 | 0 |

If we think that a relationship between two nodes is like a
message, we have a sender and a receiver. Making a relationship
between two nodes is done by getting the **n**(index)
of the sender node and the index of the receiver node.

```
matrix = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0]
]
nodes = ['A', 'B', 'C']
sender = nodes.index('A')
receiver = nodes.index('B')
relationship = matrix[sender][receiver]
```

To get all the relationships of a node, we must get the row that corresponds to the node and then remove all zeros.

```
matrix = ...
nodes = ...
row = matrix[nodes.index('A')]
# This is not pseudo code, it's real python
relationships = [nodes[x] for x in row if x != 0]
```

## Big “O” Notation

The space complexity of this way of representing graphs is
*n ^{2}*,

*n*being the number of nodes.

The time complexity of the algorithm used for getting the relationships of a node is

*O(n)*, because it loops through all nodes once.

The time complexity of the algorithm used for making a relationship is

*O(2n)*, because it loops through all nodes twice to get the index of the sender and receiver nodes.

Storing data | Inserting | Finding |
---|---|---|

O(n^{2}) |
O(n) | O(2n) |