D1: Algorithms on Graphs

A graph is a collection of points, called vertices or nodes, some of which may be connected together by lines, called arcs or edges.

A famous example of a graph is the London Underground map. The map shows connections between tube stations, the lengths do not need to represent the actual distances.

Most graphs will not just show connections but they will also have numbers on the arcs. These numbers can represent the distance between towns, the cost of a tube ticket between stations, the time taken to get from one station to the next - or many other possible meanings. Because the numbers can represent distance, time, cost, etc. we need a neutral name for this value in general. In general we call the number the weight of the arc.

When a graph has weights on the arcs we call it a weighted graph or network. So a network is just a graph with numbers on it.

Hopefully it is clear that it will be necessary to find routes through networks. And to do so we will use algorithms.

Minimum Spanning Tree

A tree is a connected bit of a graph where there are no circuits. This means that you can't go round in circles in a tree.

A spanning tree is a tree that uses all of the vertices of the graph. This means that there is a route of the spanning tree (called a path) connecting any two points together. It need not be a direct path, but there just must be a route.

A minimum spanning tree is the one that uses the least weight of vertex. If the graph represents towns connected to the electricity supply by expensive and environmentally ugly cables, the minimum spanning tree is the cheapest way of connecting them all together.

Here's a clip where I explain a few Graph Theory terms...

Kruskal's Algorithm

Kruskal's algorithm finds a minimum spanning tree (I say a minimum spanning tree rather than the minimum spanning tree because there might be more than one) by following these steps.

  1. Arrange the arcs in order of weight, smallest first (this can be done using a sorting algorithm)
  2. Choose the arcs in order. Each time make sure that you are not making a circuit
  3. The graph does not need to be connected as you go, but will be at the end when you have joined all of the nodes.

Prim's Algorithm - Graph Method

Prim's Algorithm comes in two types: graphical method and matrix method. They are actually the same thing. Whether you use this or Kruskal's algorithm you will get the same result - the minimum spanning tree.

  1. Choose somewhere to start from. Join this vertex to its nearest neighbour.
  2. Now consider both vertices and join the vertex that is nearest to either of them.
  3. Continue to build up your tree, avoiding circuits, until all vertices are joined by joining the nearest vertex to your tree so far.

Prim's Algorithm - Matrix Method

This is best explained in the video below.

The Shortest Distance From A to B

With modern Sat Nav systems becoming part of our everyday lives, algorithms for finding the shortest distance (or cheapest cost if that's what the weights mean) are becoming more and more important. We will consider only one "shortest distance" algorithm.

Dijkstra's Algorithm

Dijkstra's Algorithm finds the shortest distance from one vertex to another. It works by starting at the beginning node and builds up by adding each vertex as and when we are certain that we have found the shortest route to it. This is another thing that's easier to explain in a clip than by typing. And my hand hurts any way.