This demonstration allows you to run through various well-know graph algorithms step-by step which may be very helpful for understanding how these algorithms work. The demo allows you to study the following algorithms:
- MST (minimum spanning tree): Given a connected, undirected graph G, a spanning tree T of G is a sub-graph of G, such that:
- T which is a tree (i.e. a graph in which any two vertices are connected by exactly one path) and
- T connects all of the G‘s nodes.
A graph can have several spanning trees. A minimum spanning tree Tmin of a connected, undirected and weighted graph G is a spanning tree of G such that the weight-sum on the edges of Tmin is less than or equal to the weight-sum of any other spanning tree of G.
This simulation demonstrates two different algorithms for finding the MST of a graph: Prim’s algorithm and Kruskal’s algorithm.
- Shortest path is the problem of finding a path with minimal weight-sum that connects all nodes (Dijkstra’s algorithm is used here).
- Diameter is the problem of finding the path with the maximum weight-sum that does not visit a node more than once (Dijkstra’s algorithm is used here).
- Circuit is the problem of finding shortest closed loop (depth first search algorithm is used here).
- Breath first search is a standard graph algorithm often used for funding the closest distance between two nodes.
How to use the simulation
- Specifying the network: You can either automatically create one of several types of networks or explicitly specify the configuration of your graph.
- To specify your graph explicitly: edit the connection weights at the bottom of the control panel and then click Apply Weights. Alternatively, you can automatically create of of the 4 graph types:
- Random network: the distribution of nodes is approximately uniform, the only parameter is the connectivity;
- Tree: is a network with branches stemming off a single â€œrootâ€, the main parameter is the number of branches;
- Small world: is a regular network with a degree of random â€œlong rangeâ€ connections;
- Scale free network: is one in which the distribution of links per node follows a power law distribution;
- Set the problem: Select one of the problems described above.
- Start the simulation: Click the Start button. Each algorithm step will be illustrated on the graph depicted in the simulation window and explained in the text field at the bottom.
Links and References
- Wikipedia, Minimum spanning tree,
http://en.wikipedia.org/w/index.php?title=Minimum_spanning_tree&oldid=136046788 (as of June 17, 2007).
- Wikipedia, Prim’s Algorithm,
http://en.wikipedia.org/w/index.php?title=Prim%27s_algorithm&oldid=135413690 (as of June 17, 2007).
- Wikipedia, Kruskal’s Algorithm,
http://en.wikipedia.org/w/index.php?title=Kruskal%27s_algorithm&oldid=138063174 (as of June 17, 2007).
- Wikipedia, Dijkstra’s Algorithm,
http://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algorithm&oldid=136340402 (as of June 17, 2007).
- Wikipedia, Depth-first search,
http://en.wikipedia.org/w/index.php?title=Depth-first_search&oldid=134051467 (as of June 17, 2007).
- Wikipedia, Breadth-first search,
http://en.wikipedia.org/w/index.php?title=Breadth-first_search&oldid=135806308 (as of June 17, 2007).