Storing graphs in a program using an adjacency matrix
Introduction
Once we have built up a model of a system using a graph, we have to store the data in a program so that it can be used. How do we do this? There are two approaches we could use.
Adjacency matrix
An adjacency matrix records the relationship between one vertex and all of the other vertices, identifying whether there is an edge or not. This is a good method to use when there are more edges than vertices but not so good when there are fewer edges than vertices because it will take up a lot of memory storing the data and take longer to process through it. Consider the following examples:
Undirected - unweighted
We can put a 1 in a matrix (table) if two vertices have an edge and a 0 if they do not.
Directed - unweighted
We put a 1 in a matrix (table) if two vertices have an edge but only in the direction of the arrow, and a 0 if they do not. Note that we are working in rows, so the second row in the first column, for example, starts with Gl therefore we go along that row saying, From Glasgow to Glasgow is 0, From Glasgow to London is 0, From Glasgow to Norwich is 0 and so on. If you work vertically, your table will be different to the answers below.
Undirected - weighted
Use the weighting if there is a link, and use the infinity symbol if there isn't.
Directed - weighted
Use the weighting if there is a link but only in the direction of the arrow, and use the infinity symbol if there isn't. Note that we are working in rows, so the second row in the first column, for example, starts with Gl therefore we go along that row saying, From Glasgow to Glasgow is infinity, From Glasgow to London is infinity, From Glasgow to Norwich is infinity and so on. If you work vertically, your table will be different to the answers below.
