Welcome to Marks algorithm animation software package
Minimum Spanning Trees
Given a connected, undirected graph
G=<N,E>
where each edge has an associted weight.
For example :
An Example Of An Undirected Graph
We want a subset T of edges E such that the graph remains connected if only
the edges in T are used, and sum of the lengths of edges in T is as small as possible.
Such a subgraph must be tree and is called a Minimum Spanning Tree.
An Example Of A Minimum Spanning Tree (cost 16)
Kruskal's Algorithm
Greedy algorithm to find minimum spanning tree.
We want to find a set of edges T
- Keep track of connected components of graph with edges T
- Initially (when T=0), components are single nodes
- At each stage, add the cheapest edge that connects two nodes not already connected.
Example
- Initialise T=0 {A},{B},{C},{D},{E},{F},{G}
- Add AD {A,D},{B},{C},{E},{F},{G}
- Add FG {A,D},{B},{C},{E},{F,G}
- Add CD {A,D,C},{B},{E},{F,G}
- Add AB {A,B,D,C},{E},{F,G}
- Add EG Add DG {A,B,D,C,F,G,E}
User Manual for Mark's Algorithm Animation System
Before you can run an Algorithm Animation you must first draw the graph
that you would like to be animated.
This is done by either:
- clicking on the Default button
- drawing one manually.
To draw one manually:
- Click anywhere on the canvas to add a node. (not too close to another node/edge, max 10 nodes).
- Click on a node, drag and release on a different node to create an edge.
(A node will be highlighted to show it has been selected.)
- To move an node, hold shift down and click on desired node and drag to desired position.
- To change the weight of an edge click on its current weight, and enter new weight.
Once you are happy with your graph click Play to play the animation,
or Step to step through the animation.
To pause the animation whilst it is running click on the Pause button.
Click on Resume to resume the animation.
To stop the animation at any time it is running click on the Stop button.
To clear the current graph click on the Clear button.
Colour code
Cyan nodes represent nodes not yet connected, magenta edges represent rejected edges.
Yellow nodes represent connected nodes, green edges represent used edges.