Pages in this set

Page 1

Preview of page 1
Prims Algorithm
Step 1

Choose a start vertex.

Step 2

Connect the start vertex to the nearest new vertex by adding the shortest
edge.

Step 3

From any vertex on the tree so far, add the shortest edge that connects a new
vertex.

Step 4

Repeat step 3 until all…

Page 2

Preview of page 2
Kruskal's Algorithm
Step 1

List the edges in order of weight, smallest first.

Step 2

Choose the edge with the smallest weight

Step 3

From the remaining edges, choose the edge with the smallest weight, as long
as it does not form a cycle with the edges already chosen.

Step…

Page 3

Preview of page 3
Travelling Salesperson
Real world problem: Visit all the towns (vertices) and get back to the start.
The solution must be a complete cycle.


Method

Upper Bound
Nearest Neighbour

# start at a vertex.

# go to the closest vertex you haven't been to yet.

# from the current vertex, go…

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »