## Network Algorithms

* Authors: Alex Tee Neng Heng, David G. Green*

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).