Computing - Graphs
AQA Computer Science 2022
What a graph is
In summary, what is a graph?
An abstract data type representing complex relationships.
What is an undirected graph?
A graph where the edges don’t specify a direction.
What does an edge weight commonly represent on a graph representing a map?
The distances between two places.
What is a directed graph?
A graph where relationships can point one way only.
What is the technical definition of a graph?
A set of nodes connected by edges.
Terminology
Representing graphs
What are the two ways of representing a graph?
- Adjacency matrix
- Adjacency list
How does an adjacency matrix represent a graph?
A two-dimensional array where a value at $[\text{row}, \text{column}]$ represents a connection.
In the adjacency matrix \
\[ \begin{table}[]\begin{tabular}{llll} & A & B & C \\ A & & 1 & \\ B & & & \\ C & & 1 & \end{tabular}\end{table}\\]
, what does the second cell represent?
A connection from $B$ to $A$.
What is special about the adjacency matrix for an undirected graph?
The matrix will be symmetric.
What is the disadvantage of an adjacency matrix?
A sparse graph will have a lot of empty cells which wastes memory space.
How does an adjacency list represent a graph?
A dictionary containing the nodes and list of the other nodes it points to.
What is the advantage of an adjacency list?
It only stores the connections that exist so it’s more space-efficient.
What’s the best way to represent a large, sparse graph?
Using an adjacency list.
Connectivity
What does connected mean in the context of graphs?
Each node is linked to another node.
Choosing a representation
When might you want to use an adjacency list instead of adjacency matrix?
When the adjacency matrix is sparse.
Apart from an adjacency matrix wasting space because it’s sparse, what’s another situation where you might want to use an adjacency list?
When edges are rarely changed.