Pages in this set

Page 1

Preview of page 1

D1




Algorithms you need to know!




with
Prim
Kruskal
Djikstra
and others




Learn these and the exam will be a doddle!






1

Page 2

Preview of page 2
KRUSKAL'S ALGORITHM
This is an algorithm for finding a minimum spanning tree, or
minimum connector.
This is a spanning tree such that the total length of its edges is
as small as possible.

Step 1 Rank the arcs in ascending order of weight

Step 2 Select the arc of least…

Page 3

Preview of page 3
MATRIX FORM OF PRIM'S ALGORITHM

A network may be described using a DISTANCE MATRIX

Step 1 Choose a starting vertex and delete all
elements in that vertex's row and arrow its
column

Step 2 Neglecting all deleted terms, scan all arrowed
columns for the lowest available element and
circle that…

Page 4

Preview of page 4
DIJKSTRA'S ALGORITHM

This is for finding the shortest path in a network.

Use the following type of box:


Vertex letter Order of Final values
selection
Working values


Step 1 Label the start vertex S with a permanent
label of 0

Step 2 Put a temporary label on each vertex that…

Page 5

Preview of page 5
THE CHINESE POSTMAN PROBLEM

If the graph is Eulerian it is traversable.
If it has some odd vertices then some arcs will have to be
repeated. These repeats will be such that when added to the
graph it will make the odd vertices even! This new graph is now
Eulerian…

Page 6

Preview of page 6
BUBBLE-SORT ALGORITHM

Assuming you are "bubbling" from right to left:

Step 1

Compare the last two numbers on the extreme right. If the
smaller number is on the right, swap the two numbers and
reorder the list, if not, leave them.

Step 2

Move one step back in the list…

Page 7

Preview of page 7
QUICK-SORT ALGORITHM

Step 1

Locate the pivot element (use the element at the mid-point)

Step 2

Split the list into two sub-lists.
Sublist L1 contains those numbers less than or equal to the
pivot and are written to the left of the pivot.
Sublist L2 contains those numbers greater than…

Page 8

Preview of page 8
THE MAXIMUM MATCHING ALGORITHM

This improves an existing matching, if possible, by first
establishing an alternating path between vertices not in the
current matching. The status of the edges are then changed to
produce an improved matching.
(If the current matching is maximal, no alternating path will be
found)

Step…

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all resources »