MinimumCostSpanningTree

Works

Yes

Description

Shows Kruskal's minimal cost spanning tree. Along with the graph, there is an array and a list of edges.

Evaluation

It is pretty much a mystery what is going on here. The vertex table and the accompanying list of edges don't really convey the concept of equivalence classes for the connected subgraphs at all. This presentation desperately needs step-by-step explanations. It is a little confusing as to how to get into step-by-step mode.

Animation; Step Control; Random Data

Lecture Aid

Screenshots

Videos

References

First Visited

2006-09-01

Last Visited

2008-07-02

Last Updated

2006-04-05

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.usfca.edu/galles/visualization/download.html

Edit

You may edit this entry if you have an account.

Data Structure Visualization - Prim's Algorithm

Recommendation

Recommended

Link

Delivery Method

Java Application

License

Unlicensed Sourcecode

Language

English

Author

David Galles

Institution

University of San Francisco

Project

Data Structure Visualization

Works

Yes

Description

The Prim's algorithm here has randomized examples to run through the algorithm directly without constructing a graph. It contains various views such as the Logical, Adjacency List view and the Adjacency Matrix view. Bottom of the screen holds the animation and interaction controls. The animation contains a complete table that describes all the information such as the vertex, cost, path etc that is required to traverse through a graph using Prim's algorithm. The animation speed can be controlled easily using the slider bar, or user can go step-by-step. The graph also highlights progress in the array for every iteration.

Evaluation

Generally good visualization. Strengths include the option to go step-by-step and skipping to the last step. The algorithm goes through every possibility through the graph and also using the table that contains all the information of every node. After every iteration nodes are updated. The Adjacency list and matrix views are helpful for seeing these representations, but not for following the algorithm. The main deficiency of this AV is lack of textual feedback for every step and a history window. But the annotations on 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. The tool does not highlight the final path in the graph.

Animation; Step Control; Random Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-09-01

Last Visited

2008-07-02

Last Updated

2006-04-05

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://jhave.org/learner/graphs/prim/prim.php

Edit

You may edit this entry if you have an account.

JHAVÉ - Prim's Algorithm

Recommendation

Has Potential

Link

Delivery Method

Java Web Start

License

CreativeCommons

Language

English

Author

Richard Teviotdale, Tom Naps

Institution

University of Wisconsin - Oshkosh

Project

JHAVÉ

Works

Yes

Description

Visualization of Prim's MCST algorithm. Includes dynamically highlighted pseudo code. Associated HTML page contains an algorithm description, pseudo code, and example trace, and discussion of efficiency analysis.

Evaluation

Step Control; Questions; Canned Data

Self Study; Lab Exercise

Screenshots

Videos

References

Clicking on the link above will take you to a login page for Jhave. If you do not want to create an account at jhave.org, use anonymous@anonymous.com as your user name and anonymous as your password when you are asked to login. You will then be taken to the Jhave page for this AV. Some Jhave AVs include a tutorial on how the AV itself or the underlying algorithm works. At the bottom are links to the AV (you can run it with a built-in quiz system on or off). The first time you try to run any Jhave exercise, you will have to download the Jhave webstart application. This should happen automatically when you click the link. (You might need to install Java WebStart if it is not on your machine.) Once you download the Jhave application, the AV should start automatically. You can then step through the AV by repeatedly clicking the right arrow button. Occasionally, you will be given a multiple-choice or short-answer question to answer.

First Visited

2008-07-08

Last Visited

2008-07-10

Last Updated

2008-07-01

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://jhave.org/learner/graphs/kruskal/kruskal.php

Edit

You may edit this entry if you have an account.

JHAVÉ - Kruskal's Algorithm

Recommendation

Has Potential

Link

Delivery Method

Java Web Start

License

CreativeCommons

Language

English

Author

Richard Teviotdale, Tom Naps

Institution

University of Wisconsin - Oshkosh

Project

JHAVÉ

Works

Yes

Description

Visualization of Kruskal's MCST algorithm. Includes dynamically highlighted pseudo code. Associated HTML page contains an algorithm description, pseudo code, and example trace, and discussion of efficiency analysis.

Evaluation

The AV is set up as a series of "slides" in one pane, and pseudocode in the adjacent pane. As the user steps through the "slides", the associated pseudocode is highlighted. Occasional questions pop up for the user to answer. In addition to the graph being colored to match the steps of the algorithm, there is a small display to suggest the disjoint sets for the nodes, but not much attention is drawn to this information.

Step Control; Questions; Canned Data

Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-08

Last Visited

2008-07-10

Last Updated

2008-07-01

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.animal.ahrgr.de/showAnimationDetails.php3?anim=40

Edit

You may edit this entry if you have an account.

Animal - Minimum Cost Spanning Tree

Recommendation

Not Recommended

Link

Delivery Method

Animal Animation

License

Non-Commercial

Language

English; German

Author

André Flöper; Guido Rössling

Institution

TU Darmstadt, Darmstadt, Germany

Project

Animal

Works

Yes

Description

Presents a slideshow with examples for Prims and Kurskal's algorithms.

Evaluation

Generally clear presentation, but with some serious content flaws. The Kruskal's AV doesn't get across the relationship to disjoint sets, which is a fundamental part of the algorithm. The analysis is basically wrong, stating that Kruskal's is |E| log |E|, Prims is |V|^2, and so Kruskal's is cheaper. In fact, the cost of Prim's depends on how the next vertex is found, and the denseness of the graph. Thus, the AV's analysis is oversimplified and misleading.

Animation; Step Control; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

References

For detailed instructions on how to install Animal and run Animal AVs, see: http://www.algoanim.info/Animal2/?q=node/290. Once you have installed the Animal .jar file and downloaded/unpacked the .zip file of Animal animations, you are now ready to run Animal. Run the .jar file to start Animal. Then go to the "Open" menu item, and browse to where you put the animal animations you got in the .zip file. Pick this AV from the list. You can then step through the animation, or use "kiosk mode" to have the steps fed to you at a constant pace.

First Visited

2007-07-21

Last Visited

2010-02-05

Last Updated

1999-05-10

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/minSpTree/MST.html

Edit

You may edit this entry if you have an account.

Ghosh - Minimum Spanning Tree

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

R. K. Ghosh

Institution

Indian Institute of Technology, Kanpur

Project

Ghosh's Collection

Works

Yes

Description

A panel on top of the applet displays several controls to build a graph and to progress through the algorithm. The visualization allows the user to construct her own input graph by adding nodes and weighted edges in addition to providing a default graph. Next, the user selects the algorithm (Kruskal's or Prim's) to use. The user can step through the algorithm or begin a continuous animation that runs to completion from the current step. The visualization uses a a color scheme to distinguish between the various logical entities in the algorithm.

Evaluation

This visualization does a reasonable job at explaining the construction of the MST. The color scheme used is satisfactory. A good default example is provided. The visualization illustrates the algorithm at the right granularity. The presentation and usability of the applet could be improved. The vertical dimension of the applet is too large and forces the user to constantly scroll to the "display pane" and back to the "control pane". The control pane is crowded with several buttons. A compact way to express these controls is highly desirable. The point at which an edge is added to the MST in the Prim's algorithm is not intuitive. Supporting explanation text would significantly enhance the visualization. The user cannot control the speed of the animation portion at each step. This is a problem because it is too slow, and at the same time, the explanation messages are getting overwritten before the user can process them completely.

Step Control; Animation; User Data; Canned Data

Teaching the Concept

Screenshots

Videos

References

First Visited

2008-06-04

Last Visited

2008-07-15

Last Updated

2001-08-21

Topic

Community

Average rating:	3.0
Your rating:	You must be logged in to Rate.

http://www.cs.hut.fi/Research/TRAKLA2/exercises/Prim.html

Edit

You may edit this entry if you have an account.

Trakla - Prim's Minimum Cost Spanning Tree Algorithm

Recommendation

Has Potential

Link

Delivery Method

Java Application

License

GPL

Language

English

Author

Ville Karavirta; Ari Korhonen; Lauri Malmi; Kimmo Stålnacke

Institution

Helsinki University of Technology

Project

Trakla2

Works

Yes

Description

User clicks on nodes of the graph in order that they are processed.

Evaluation

This is a great idea to have users show proficiency in the algorithm by processing the graph. But the implementation does not quite work out. The big problem is that the edge distances are not shown on the graph. They are shown in an adjacency list, but it is extremely difficult for users to integrate that information to pick the next vertex. The graph layouts are poor, and it would not be a simple thing to label the edges with their distances.

Canned Data; Predictions

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-29

Last Visited

2008-07-29

Last Updated

2006-01-25

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://students.ceid.upatras.gr/~papagel/project/kruskal.htm

Edit

You may edit this entry if you have an account.

UPatrasKruskal

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Papagelis Athanasios

Institution

University of Patras

Project

UPatras Collection

Works

Yes

Description

The web page provides a brief explanation of Kruskal's algorithm followed by an embedded visualization (applet) that demonstrates the algorithm. The visualization comprises two panes placed side by side. The left pane displays the original weighted undirected graph. As the algorithm executes, edges added to the MST and the nodes that these edges connect are highlighted in this graph. The graph in the right pane displays the current state of the partially constructed MST. When the algorithm terminates the right pane contains that completed MST. The visualization allows the user to step through the algorithm or view the completed solution. Several good example graphs are provided.

Evaluation

This visualization does a reasonable job at explaining the Kruskal's algorithm using several good examples. The color scheme chosen is effective. However, the visualization could improve on certain areas. While stepping through the algorithm, the visualization cycles back to the first step without providing any indication that the algorithm has terminated, which could confuse the uninitiated. Supporting explanation text within the visualization that explains what happens at each step could significantly enhance the visualization. The brief explanation at the beginning of the webpage uses non-standard terminology. For example, the minimum spanning tree is called the minimum genetic tree.

Lecture Aid

Screenshots

Videos

References

First Visited

2008-04-06

Last Visited

2008-04-06

Last Updated

1997-10-13

Topic

Community

Average rating:	3.0
Your rating:	You must be logged in to Rate.

http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Prim.shtml

Edit

You may edit this entry if you have an account.

Prim's Algorithm

Recommendation

Unrated

Link

Delivery Method

Java Applet

License

Language

English

Author

Kenji Ikeda

Institution

Tokushima University

Project

Works

Yes

Description

Prim's Minimal Cost Spanning Tree algorithm.

Evaluation

Screenshots

Videos

References

First Visited

2007

Last Visited

Last Updated

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/kruskal/Kruskal.shtml

Edit

You may edit this entry if you have an account.

Kruskal's Algorithm

Recommendation

Unrated

Link

Delivery Method

Java Applet

License

Language

English

Author

Kenji Ikeda

Institution

Tokushima University

Project

Works

Yes

Description

Evaluation

Screenshots

Videos

References

First Visited

2007

Last Visited

Last Updated

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://students.ceid.upatras.gr/~papagel/project/prim.htm

Edit

You may edit this entry if you have an account.

UPatras Prim

Recommendation

Unrated

Link

Delivery Method

Java Applet

License

Language

English

Author

Institution

University of Patras

Project

UPatras Collection

Works

Description

Prim's minimal cost spanning tree algorithm

Evaluation

Screenshots

Videos

References

First Visited

Last Visited

Last Updated

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.auckland.ac.nz/software/AlgAnim/mst.html#mst_anim

Edit

You may edit this entry if you have an account.

Auckland - MST

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Mervyn Ng; John Morris

Institution

University of Auckland

Project

Morris' Collection

Works

Yes

Description

Kruskal's MST algorithm. Animation (or step by step) on given choices of graphs.

Evaluation

Fairly minimal presentation. No concept whatsoever of the union/find process going on.

Step Control; Animation; Canned Data

Lecture Aid

Screenshots

Videos

References

First Visited

2006-11-06

Last Visited

2008-07-17

Last Updated

1998

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.eecs.wsu.edu/~holder/courses/cse2320/lectures/applets/mst/tree.html

Edit

You may edit this entry if you have an account.

Interconnection Trees

Recommendation

Unrated

Link

Delivery Method

Java Applet

License

Language

English

Author

Lawrence Holder (J.L. Ganley?)

Institution

University of Texas, Arlington

Project

Works

Description

Move nodes around to see how it affects the MCST.

Evaluation

Screenshots

Videos

References

First Visited

2008

Last Visited

Last Updated

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

Edit

You may edit this entry if you have an account.

GALGO - Dijkstra's Algorithm

Recommendation

Has Potential

Link

http://www.informatik.fb2.fh-frankfurt.de/~hoebel/graphen/galgo/ (German version); http://www.informatik.fb2.fh-frankfurt.de/~hoebel/graphen/galgo/en/index.html (English version)

Delivery Method

Java Applet

License

Unavailable

Language

German; English

Author

Natascha Hoebel; Martin Burrer

Institution

University of Applied Siences, Frankfurt

Project

GALGO

Works

Yes

Description

User either selects or creates a graph, and then runs user's choice of Prim's or Kruskal's MCST algorithm.

Evaluation

Sophisticated graph editing capabilities. The AV portion is a straight animation.

Exploring the Concept

Screenshots

Videos

References

First Visited

2009-04-21

Last Visited

2009-04-21

Last Updated

2003

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://users.uom.gr/~thanasis/JAVENGA.html

Edit

You may edit this entry if you have an account.

JAVENGA Minimal Cost Spanning Trees

Recommendation

Unrated

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Baloukas Athanasios

Institution

University of Macedonia, Department of Applied Informatics, Thessaloniki, Greece

Project

JAVENGA

Works

Yes

Description

The software features static visualizations for Graph and Network Algorithms. More specifically it illustrates: BFS and DFS traversals; topological sorting; various shortest path algorithms; Minimum Spanning tree algorithms of Prim and Kruskal; and the Primal Network Simplex Algorithm for the balanced Minimum Cost Network Flow Problem.

Evaluation

Teaching the Concept; Exploring the Concept

Screenshots

Videos

References

You can use this as a Java Applet (click on link above) or get the Java .jar file at http://users.uom.gr/~thanasis/JAVENGA.html. When you open the applet, you must first enter a graph using the graphical editor (first 3 buttons at the top). You can view the graph representation (4th button). You can choose an algorithm to run (rightmost button at top). It doesn't appear that you can run an algorithm until you have actually created a graph using the editor.

First Visited

2009-09-02

Last Visited

2009-09-02

Last Updated

2009

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://alvie.algoritmica.org/

Edit

You may edit this entry if you have an account.

ALVIE - Jarnik/Prim

Recommendation

Unrated

Link

Delivery Method

Java Application

License

By Request

Language

English

Author

Pilu Crescenzi

Institution

University of Florence

Project

ALVIE

Works

Yes

Description

Walkthrough showing the Jarnik/Prim algorithm for determining the Minimal Cost Spanning Tree

Evaluation

Simple-to-use user interface for walking through the example. Simply open up the AV (see directions below) and step through the example with pseudo-code. As you go through the example, you are directed to the corresponding line in the pseudocode and given a line or two of explanation in the message window. Attractive layout of the data, including colors.

Step Control; Canned Data

http://sites.google.com/site/alviehomepage/alvie3/downoads/jarnikPrim.swf

Lecture Aid; Self Study

Screenshots

Videos

References

Download and unzip the ALVIE system from the website. Double click on the .jar file. Within the ALVIE pane (not the GRIND pane), click on the "eye" icon (third icon from the left in the toolbar) to get a list of algorithms from which select the AV that you want. Once selected, click OK and step through the AV with the arrow icons.

First Visited

2010-01-29

Last Visited

2010-01-29

Last Updated

2009-12-20

Topic