4.2 - Graphs

Question 1

What are graphs?

Answer 1

Graphs are an abstract data structure used to represent complex relationships between items within datasets. Graphs can be used to represent networks such as transport networks, IT networks and the Internet.

A graph consists of nodes (also known as vertices) which are joined by edges (sometimes called arcs). A weighted graph is one in which edges are assigned a value, representing a value such as time, distance or cost for example.

Question 2

Unweighted, Undirected Graph vs Weighted, Directed Graph

Answer 2

Unweighted, Undirected Graph has no arrowheads or values on the edges (lines connecting the nodes)

Question 3

How can graphs be represented?

Answer 3

Adjacency Matrices and Adjacency Lists

Question 4

Explain adjacency matrices.

Answer 4

An adjacency matrix is a tabular representation of the graph. Each of the nodes in a graph is assigned both a row and a column in the table.

They always show diagonal symmetry.

Question 5

In an unweighted graph, how are the matrices represented?

Answer 5

1 in the table represents that an EDGE EXISTS between two nodes.

0 indicates that there is NO CONNECTION.

Adjacency Matrices always have a diagonal line of 0s, represented when the row and column represent the same node.

Question 6

In a weighted graph, how are the matrices represented?

Answer 6

Rather than using 1s and 0s, adjacency matrices contain the weight of a contain between two nodes.

If no connection exists, an arbitrarily large value is used (infinity symbol). This presents any shortest path algorithm from using any non existent edges.

Question 7

Explain adjacency lists.

Answer 7

Instead of using a table to represent a graph, a list can be used.

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 8

Adjacency Lists vs Adjacency Matrices

Answer 8

Adjacency Matrix:
ADVANTAGE - Time Efficient: Allows a specific edge to be queried very quickly, as it can be looked up by its row and column.
DISADVANTAGE - Memory Inefficient: Stores every possible edge between nodes, even those that don’t
exist. Almost half the matrix is repeated data.

Adjacency List:
ADVANTAGE - Memory Efficient: Only stores the edges that exist in the graph
DISADVANTAGE: Time Inefficient: Slow to query, as each item in a list must be searched sequentially until the desired edge is found.