Spanning Trees¶
A spanning tree of a graph consists of all nodes of the graph and some of the edges of the graph so that there is a path between any two nodes.
Like trees in general, spanning trees are connected and acyclic.
Usually there are several ways to construct a spanning tree.
Note that a graph may have several minimum and maximum spanning trees, so the trees ar not unique.
It turns out that several greedy methods can be used to construct minimum and maximum spanning trees.
terminologies¶
 Weight of spanning tree: sum of its edge weights.
 Minimum spanning tree: a spanning tree whose weight is as small as possible
Kruskal's Algorithms¶
The initial spanning tree only contains the nodes of the graph and does not contain any edges. Then the algorithm goes through edges ordered by their weights, and always adds an edge to the tree if it does not create a cycle. The algorithm maintains the components of the tree. Initially each node of the graph belongs to a separate component. Always when an edge is added to the tree, two components are joined. Finally, all nodes belong to the same component and a minimum spanning tree has been found
Implementation¶
It's convinient to use the edge list representation
1 2 3 4 5 6 

efficiency
The problem is how to efficiently implement the function same
and unite
. One possibility is to implement function same
as a graph traversal and check if we can get from node a
to node b
. However, the time complexity of such a function would be $\Omicron(n+m)$ and resulting algorithm would be slow, because the function same
will be called for each edge in graph.
Union find structure¶
Using a Union find structure implements both $same$ and $unite$ functions in $\Omicron(lg(n))$ time. thus the time complexity of Kruskal's algorithm will be $\Omicron(mlg(n))$
Structure¶
In a unionfind structure, one element in each set is the representative of the set, and there is a chain from any other element of the set to the representative.
The efficiency of the unionfind structure depends on how the sets are joined.
It turns out that we can follow a simple strategy:always connect the representative the smaller set to the representative of larger set. Using this strategy, the length of any chain will be $\Omicron(lg(n))$
Implementation¶
The unionfind structure can be implemented using arrays.
link
contains for each element the next element in the chain or the element it self if it is representative.and the array
size
indicates for each representative the size of thecorresponding set.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 

Prim's algorithm¶
The algorithm first adds an arbitrary node to the tree. After this, the algorithm always choose a minimumweight edge that adds a new node to the tree. Finally all nodes have been added to the tree and a minimum tree has been found
Prim's algorithm resembles Dijkstra's algorithm. But, Prim's algorithm simply selects the minimum weight edge that adds a new node to the tree.
Implementation¶
Like Dijkstra's algorithm, Prim's algorithm can be efficiently implemented using a priority queue.
The priority queue should contain all nodes that can be conneted to the current component using a single edge, in increasing order of the weights of the corresponding edges.
The time complexity of Prim's algorithm is $\Omicron(n+ mlg(m))$ that equals the time complexity of Dijkstra's algorithm.
most competitive programmers use Kruskal's algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 
