# Graphs (data structures)

**Level: A Level Computing**

In computing, a **graph** is a set of **vertices** (points) connected by **edges**. For example:

Here, the circles labelled A to E are the vertices, the red lines joining them together are the edges. Vertices are sometimes called **nodes**. Edges are sometimes called **arcs**.

Graphs are also used in graph theory in maths.

## Contents

## Graph types and typical uses

The basic graph shown above is used to store connections between vertices. A typical use of this might be to represent a wired computer network, where the vertices represent computers and the edges represent the wires between them.

There are other types of graph, shown below.

## Weighted graphs

A **weighted graph** has a value associated with each edge. The can represent the "cost" of moving from one vertex to another. For example in this graph, the vertices are cities, the edges represent roads joining the cities, and the weight is the distance between the cities in km.

Weighted graphs can be used for solving optimisation problems. For example, suppose you had to visit all four towns - using the distances you could find the shortest route that visits all 4 towns.

## Directed graphs

A **directed graph** (sometimes called a **digraph**) each edge has a direction. You can only move from one vertex to another if the arrow is pointing in the that direction.

In this case, the graph might indicate some tasks that have to be performed in a particular order:

- A - decide what you want for dinner
- B - set the table
- C - prepare the ingredients
- D - cook the food
- E - eat dinner

The graphs shows that A must be done first. C and D must be done in order (first prepare the ingredients, then cook them), but task B can be done at the same time (you can set the table while the food is being made). Finally E, eating dinner, cannot be done until all the other tasks are complete.

A directed graph can also be weighted. For example we could weight the edges according to how long each task will take. This will allow us to calculate how long it will take until dinner is ready.

## Connected graphs

Two vertices are said to be **connected** if there is a path between them (either directly or via another vertex). In this graph, **A** is connected to **B** directly. **A** is also connected to **D**, for example connecting path goes from **A** to **C** to **D**.

A **graph** is said to be **connected** if every vertex is connected to every other. The graph above is connected. Here is a graph that is not connected:

Vertices **A** and **B** are not connected, for example. Even though some of the vertices are connected, the graph as a whole is classed as not connected.

## Cycles

A **cycle** is a closed path that includes 3 or more vertices. This graph contains several cycles:

For example **DBE** is a cycle - you can go from **D** to **B** to **E** and back to **D**. **ABEDC** is another cycle.

This graph contains no cycles:

## Implementations

There are several different ways to implement graphs. Commonly used ones are adjacency matrices and adjacency lists.