Algorithms.

HideShow resource information

Kruskal's algorithm:

1)LIST arcs in order of weights (smallest -> largest).

2)SELECT the first arc that is of smallest weight and add this to start the tree.

3)CHOOSE the next smallest arc, adding it to the tree, UNLESS it forms a cycle. (If forms a cycle -> reject).

4)STOP when all nodes are connected.

5)FINISH, by listing all arcs, and then adding the weights together to find the total weight of the network.

Prim's algorithm:

1)CHOOSE a staring vertex.

2)ADD the nearest vertex, with the smallest weight.

3)CONTINUE to repeat step 2 until all nodes are connected. (look at all the arcs that link vertices in the tree with those not in the tree).

4)STOP when all nodes are connected.

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all Networks, algorithms and problem solving resources »