Graphs (data structures)
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.
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.
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.
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.
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.
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: