3. Graph types

Directed graph

In a directed graph, movement between vertices is restricted. We indicate this using arrows as edges. For example you can go from A to C but you cannot go the other way from C to A.

This pattern of movement is called the flow. We use directed graphs to model flow in situations like road traffic or street layout, where one-way streets restrict movement within a city.

Undirected graph

This is the simplest kind where the edges have no particular direction or flow associated with them. Like this:

For example A and C are connected but there is no indication of a direction to the connection.

Consider a graph to model friends on a social network, replace 'A' with 'Annabel' and 'C' with Charlie then the edge is indicating that Annabel and Charlie are friends, but it makes no sense to imply a direction to that friendship.

Labelled or Weighted graph

In weighted graphs, movement from one vertex to another has a 'cost'. This is usually labelled as a number. Different edges will have different costs.

You can apply weightings to both directed and undirected graphs.

This type of graph is used alongside programs written to maximise efficiency. For example, a route calculator in a mapping program will add up the total travel time of each possible path between two locations, and present you with the best one. Routers use weighted graphs to minimise latency.