Representing 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² cells to zero, because currently, we have no relationships.

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², 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.