The Algorithm Visualization Catalog is a comprehensive collection of links to algorithm visualizations, or AVs.

Data Structure Visualization - Minimal Cost Spanning Tree

Link(s)
http://www.cs.usfca.edu/galles/visualization
Topic(s)
Kruskal's algorithm, Minimum spanning tree, Prim's algorithm, Graph Algorithms

Screenshots
Large graph -- Krusal's


Recommendation
  
Lecture Aide Recommended
Self-study Supplement Recommended
Standalone Not Recommended
Debugging Aide Has Potential
Works?
Yes
Delivery Method(s)
Java Application, JavaScript
Project
Data Structure Visualization
Project Relationship
Part of project
Language(s)
English
Author(s)
David Galles
Institution(s)
University of San Francisco
Activity Level(s)
Animation, Random data, Slideshow, Step control
Source Code License
Open source (non-OSI)
First Published
N/A
Last Modified
2011

Description

Visalizations are available for both Prim’s and Kruskal’s algorithms. For each, user can select new randomized graphs to try out. There are views for the logical graph as well as the adjacency list and adjacency matrix representations. Algorithm can be run in animation mode or stepwise mode.

Prim’s AV contains a complete table that describes all the information such as the vertex, cost, path etc that is required to traverse through the graph using Prim’s algorithm (equivalent to Dijkstra’s algorithm for shortest paths).

Kruskal’s AV shows a table indicating the disjoint sets for the vertices, and the list of edges in sort order. There is just (barely) enough explanation text as the algorithm does its processing to see what is going on.

The small graph has six nodes, while the large one has eighteen. The edges are assigned randomly, with random weights from 1 to 10. There was some cluttering of data sometimes with large graphs, depending on which edges were assigned by the application.  

Evaluation

This AV assumes knowledge of the algorithm and its supporting data structures (disjoint sets, adjacency-list and matrix implementation). The slideshow presentation allows you to go step-by-step, though you have to stop the animation to do so. After every iteration nodes are updated. The Adjacency list and matrix views are helpful for seeing these representations, but not for following the algorithm. But the annotations along with the table at each step almost give enough information about this, which is why this AV is "Recommended". It also needs a "back" button to trace back through the steps. One of the view AVs for Kruskal’s algorithm that does a credible job of showing the disjoint set operations, though this could be much better if it showed a logical view of the disjoint sets instead of just the array view.

The application is simple to use. When the "Run Kruskal" button is pressed, the user can see how the edges are sorted. The current  edge considered and the edges added are highlighted with colors, although no difference is made between already-seen edges and edges yet to be processed. The speed of the animation can be selected. User interaction is limited to (i) making the animation run and (ii) clicking through steps if the user decides not to run the tool automatically.  

Usage Notes

The URL above takes you to a page with links on the left side for choice of implementation (Java or JavaScript). Once you pick the implementation, you can choose an algorithm.

 

Field Report(s)
References
N/A
Rating
0
No votes yet
Your rating: None
AV of the Day
No
Score
53