Graphs revision notes

What is a graph?

A graph is a data structure used to represent relationships between objects. The objects are represented by vertices, also called nodes, and the relationships are represented by edges, also called arcs. For example, a graph could represent locations connected by roads, people connected by relationships, or computers connected in a network.

A vertex represents an individual object. An edge represents a connection between two vertices. The exact meaning of a connection depends on the problem being modelled.

Types of graph

An undirected graph has edges with no direction. If vertex A is connected to vertex B, the connection can be considered to work in both directions. A road graph could be undirected if travel between two locations is possible in either direction.

A directed graph has edges with a direction. An edge from A to B represents a connection from A to B, but it does not automatically represent a connection from B to A. A graph representing one-way links is an example of a directed graph.

A weighted graph has a value associated with an edge. The value may represent something such as distance, time or cost in the situation being modelled. The weight belongs to the connection, not to the vertex itself. A graph can be both directed and weighted.

Adjacency matrix

An adjacency matrix represents a graph using a two-dimensional table. Each row and each column corresponds to a vertex. The entry at the intersection of a row and a column indicates whether an edge exists between the corresponding vertices. In a weighted graph, the entry can hold the edge's weight rather than only indicating connection or no connection.

For an undirected graph, the connection from A to B corresponds to the connection from B to A, so the relevant entries reflect the same relationship. For a directed graph, the two entries can represent different directed edges and therefore need not be the same.

Adjacency list

An adjacency list stores a list of the vertices directly connected to each vertex. Each vertex has an associated list of adjacent vertices. For a weighted graph, an entry in the list can also include the weight of the edge. In a directed graph, the list records the vertices reached by outgoing edges, so the reverse connection is not assumed.

Comparing the representations

An adjacency matrix provides a position for every possible pair of vertices. This makes the representation systematic and allows the presence or value of a particular connection to be inspected by using its row and column. However, it includes positions for pairs that may not have an edge.

An adjacency list records connections alongside the vertices that have them. It directly shows the neighbours of each vertex and does not need a separate connection entry for every possible pair. However, checking whether a particular pair is connected may require examining the relevant list.

The suitable representation depends on the graph and the operation required. Consider whether the graph is directed or undirected, whether edges have weights, and whether the task focuses on inspecting a particular pair or examining the connections from a vertex.

Common errors

• Treating a vertex as the connection rather than the object being connected.
• Assuming every graph is directed or every graph is undirected.
• Confusing a weighted graph with a graph in which vertices have values; weights belong to edges.
• Assuming an edge from A to B in a directed graph automatically gives an edge from B to A.
• Forgetting that an adjacency matrix uses both rows and columns to identify vertices.
• Describing an adjacency list as a list of all possible pairs rather than a list of connections for each vertex.