Minimal Spanning Tree
Task:
Find a connected ayclic subgraph that contains all nodes of the graph and has the smallest sum of costs of its edges.
Example: Given some villages and a list of possible telephony connections between them having different costs. Find the cheapest way to connect these villages in a telephony network.
Solution:
There are two wellknown algorithms for solving this problem: Prim's and Kruskal's.
Prim's algorithm basically runs in O(N^{2}), with some optimizations it runs in O(NlogN) for sparse graphs.
Kruskal's alogrithm basically runs in O(NM), and in O(MlogN) with a good implementation of the algorithm (N is the number of nodes and M is
the number of edges).
Here I wil explain Prim's algorithm because it's easier to implement than a good Kruskal's algorithm (the one that runs in O(MlogN)) and because
it works substantially faster for a big number of edges.
Prim's Algorithm:
 Start with a tree having one node (you can choose anyone). Let this node be i.
Let the distance of a node to a tree represent the cost of the cheapest edge that connects the tree with that node.
Set the distance to i to 0, and the distances to all other nodes to infinity.
 If all node are processed then exit, because the minimal spanning tree has been found.
Otherwise, among all unprocessed nodes find the one that has the minimum distance to the tree. Let this node be i.
Mark it as processed (thus including it into the tree) and go to point 3.
Note: If distances of all unprocessed nodes are equal to Infinity then no minimal spanning tree exists.
 Look at each unprocessed neighbor j (i.e. at those that are not yet included in the tree) of node i. If the distance
from j to the tree is greater than the cost of edge between i and j, then
set the distance to j to the cost of this edge and mark that j has been reached from i.
Go back to point 2.
Complexity:
All N nodes are processed, and for each the neighbors are updated in O(N). Thus the complexity is O(N^{2}).
Restrictions:
Prim's algorithm doesn't work for graphs that have directed edges.
Optimizations:
 For sparse graphs a complexity of O(NlogN) may be obtained. For this purpose a heap is used to store the distances
to nodes, and neighbors of each node are stored in lists. In this way the unprocessed node with the minimum distance is found in logN
and the update of each node is also done in logN.
Providing that the graph is sparse, each node has few neighbors and thus the average complexity is O(NlogN).
Sample Execution:
Applications:
 Consider some communications stations (for telephony, cable television, Internet etc.) and a list of possible connections between them,
having different costs. Find the cheapest way to connect these stations in a network, so that a station is connected to any other (directly,
or through intermediate stations). This may be used for example to connect villages to cable television, or to Internet.
 The same problem, but instead of connecting communications stations  villages are to be connected with roads.
A graph (arranged in grid) similar to a city rectangular
structure 
Minimal Spanning Tree applied to the same graph 
