4.2.4.1 Graphs

Question 1

What is a graph data structure?

Answer 1

Diagrams modelling relationships between objects of a certain collection, consisting of edges (lines) and vertices. and

Question 2

What is a weighted / directed graph?

Answer 2

Weighted - graphs have values stored in their edges

Directed - graphs where the edges point one way

Question 3

What are graphs used for?

Answer 3

Graphs are used to record relationships between things, e.g maps.

Question 4

What is a vertex / node?

Answer 4

The vertices (nodes) are where the data is stored. The degree of a vertex is how many other vertices it is connected to (or how many neighbours it has).

Question 5

What is an edge / arc / connection?

Answer 5

The edges connect the nodes. When there are two vertices connected by an edge, the two vertices are called neighbours.

Question 6

What is an adjacency matrix?

Answer 6

Records the relationship between every vertex to all other vertices. It records both when there is an edge between two vertices and when there isn’t an edge. 0 represents that the two nodes are not connected, 1 for if they are. The data in the edges can be stored instead of 1 and 0, and a dash for no edge.
Used for stuff like satnavs

Question 7

What is an adjacency list?

Answer 7

An adjacency list records the relationship between every vertex to all relevant vertices. It records only when there is an edge between two vertices. To search it would be harder because you don’t know where the data is in the list.

Question 8

When should you use an adjacency list / matrix?

Answer 8

An adjacency matrix uses O(n*n) memory. It has fast lookups to check for presence or absence of a specific edge, but slow to iterate over all edges.
Adjacency lists use memory in proportion to the number edges, which might save a lot of memory if the adjacency matrix is sparse. It is fast to iterate over all edges, but finding the presence or absence of a specific edge is slightly slower
Adjacency matrix appropriate when there are many edges between vertices // when edges may be frequently changed // when presence/absence of specific edges needs to be tested frequently

Question 9

How could you store a binary tree?

Answer 9

Using three arrays:
One array stores data items;, One array for left child pointers;, One array for right child pointers;
Pointers stored at same location in arrays as corresponding data item;

With one array:
Record created to store data item and pointers;
One pointer to left child;
One pointer to right child;

Root node stored at first location/start of array(s)