Graphs (OCR A Level Computer Science)

Graphs

What is a Graph?

• A graph is a set of vertices/nodes that are connected by edges/pointers. Graphs can be placed into the following categories:

• Directed Graph: The edges can only be traversed in one direction

• Undirected Graph: The edges can be traversed in both directions

• Weighted Graph: A value is attached to each edge

Computers are able to process graphs by using either an adjacency matrix or an adjacency list. 

The examples below will be illustrated using an adjacency matrix, more information on programming using both matrices and lists is available in section 8.

Undirected, Unweighted Graph

For unweighted graphs:

• 1 is set when an edge exists between 2 nodes

• 0 is set when there is no edge between 2 nodes

Below is the adjacency matrix for an undirected, unweighted graph:

For this graph, the names are abbreviated to the first letter.

• The data in an adjacency matrix for an unweighted graph is symmetric

• To determine the presence or absence of an edge, you inspect the row (or column) that represents a node. Example: If you wanted to see if there is an edge between Frogmore and Hartlepool you can look at the cross-section of row 3 (for Frogmore) and column 4 (for Hartlepool)

• You need a method (e.g Dictionary) to record which row/column is used for a specific node’s edge data

• The data values for the nodes (in this example names of towns) are not stored in the matrix

Directed, Unweighted Graph

Above is the adjacency matrix for a directed, unweighted graph.
For this graph, the names are abbreviated to the first letter.

• Due to the lack of symmetry in this matrix, you cannot access the data by both row and column, you must know the direction in which the values are stored

• E.g.: In row 0 for Bolton there is only one neighbour (Dunkirk) because there is a single directed edge from Bolton towards Dunkirk. This is because there are 3 edges directed towards Bolton (from Dunkirk, Hartlepool and Frogmore)

• If you are implementing a graph as an adjacency matrix you will need to choose the direction and make sure that the data is stored and accessed correctly

Undirected, Weighted Graph

• For weighted graphs the values of the weights are stored in the adjacency matrix

• If an edge does not exist between two nodes, then a very large number (normally the infinity symbol ∞) is set

Above is the adjacency matrix for an undirected, unweighted graph.
For this graph, the names are abbreviated to the first letter.

Directed, Weighted Graph

Above is the adjacency matrix for a directed weighted graph:
For this graph, the names are abbreviated to the first letter.

The Applications of Graphs

Graphs have many uses in the world of Computer Science, for example:

• Social Networks

• Transport Networks

• Operating Systems