Tufts Comp160 - Graphing Algorithms Simulations
Developed by RafiLabs
The following application simulates the following algorithms: Breadth First Search (BFS), Depth First Search (DFS), and Prim's Minimum Spanning Tree (MST).
All the graphs in use are undirected and weighted. You can run the application in two modes: instantaneously or step-by-step.
See instructions below. The implementation of these algorithms is based off of
Introduction toAlgorithms, third edition
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
BFS: At the end of the algorithm, each node contains its name, how far away it is from the source vertex, and its parent.
So a node with a label of "B,1,A" is the Node B that is 1 edge away from the source vertex, and its parent is Node A.
The edges highlighted in green show the BFS tree.
DFS: At the end of the algorithm, each node contains its name, its start/finish time, and its parent.
So a node with a label of "B,2/14,A" is Node B with a start time of 2, a finish time of 14, and its parent is Node A.
Prim's: At the end of the algorithm, each node contains its name, its key (i.e. the cheapest edge connect it to the MST), and its parent.
So a node with a label of "B, 2, A" is Node B with a key of 2, and its parent is Node A.
The edges highlighted in green show the MST.
Please use edge weights less than 1000. I initially used Number.MAX_INT for these simulations, but the node labels
become absurdly large and unreadable. If you use weights greater than 1000, then Prim's algorithm will not run correctly.
I had to modify the MinHeap.js slightly and include an exists() function. This is necessary for Prim's algorithm as it tests for
set membership within the min heap for every node it looks at. This is to ensure the MST doesn't form cycles. The exists()
function is not efficient - it does a linear search for the particular node.