Graphs

Question 1

What is a graph?

Answer 1

An abstract data structure used to represent complex relationships between items within datasets.

Question 2

What can graphs represent?

Answer 2

They can be used to represent networks such as transport networks, IT networks and the Internet.

Question 3

What is a node?

Answer 3

A fundamental unit in a graph which contains data and pointers to other nodes.

Question 4

What is an edge?

Answer 4

A connection between two nodes in a graph.

Question 5

What is a weighted graph?

Answer 5

A graph where the edges are assigned a value. E.g. a map of towns and the distance between them.

Question 6

What is a directed graph?

Answer 6

A graph where the edges have a direction. The edges cannot be bi-directional.

Question 7

What are the two ways in which a graph can be represented?

Answer 7

By using adjacency matrices or adjacency lists.

Question 8

Explain an adjacency matrix for an undirected graph.

Answer 8

A one is used to show that an edge exists between two nodes and a zero indicates that there is no connection.

Adjacency matrices have a characteristic diagonal line of 0s where the row and column represent the same node.

They also display diagonal symmetry.

Question 9

Explain an adjacency list for an undirected graph.

Answer 9

For each node in the graph, a list of adjacent nodes is created. This means that an adjacency list only records existing connections in a graph, unlike an adjacency matrix which stores even those edges that don’t exist.

Question 10

What is the space consideration for a matrix?

Answer 10

Stores every possible edge, even those that don’t exist. Requires more memory (O(n^2)). If undirected, half the matrix is repeated data.

Question 11

What is the space consideration for a list?

Answer 11

Only stores edges that exist.
Requires less memory.

Question 12

What is the time consideration for a matrix?

Answer 12

Specific edges can be accessed instantly (O(1)) by looking up its row and column.

Question 13

What is the time consideration of a list?

Answer 13

Slow to access specific edges as each item in a list must be searched sequentially (O(n)).

Question 14

When do you use a matrix?

Answer 14

Use when graphs have a large number of edges, or when edges need to be frequently changes/checked.

Question 15

When do you use a list?

Answer 15

Use when there are few edges or when edges are not frequently changed/checked.