Graphs (data structures)

From Schoolcoders wiki
Jump to: navigation, search
Level: A Level Computing


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

Graph-data-structure.png

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.


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.

Graph-data-structure-weighted.png

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.

Graph-data-structure-directed.png

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.

Graph-data-structure.png

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:

Graph-data-structure-not-connected.png

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:

Graph-data-structure.png

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:

Graph-data-structure-no-cycles.png


Implementations

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


See also