group c
Contents
Historical Notes
The idea of kruskal's algorithm came from the problem of seven bridge of Königsberg. In the city of Konigsberg, in the east Prussia(now the city is belonged to Russia), 7 bridges connected two island in the river and the mainland of both sides. Leonhard Euler wanted to find out if there is a way to devise a walk through the city that would cross each bridge only once. Euler failed to do that but he came up the way to prove that it is impossible. He developed the theorem to figure out at what circumstance one is able to finish the path without turning back. That is Euler's theorem we learned in class. The contribution of Euler is he laid the foundations of graph theory and prefigured the idea of topology. Now, we can turn all the path problem into points and bridges.This is the foundation of the problem we are talking about, Kriskal's algorithm. Kruskal algorithm is a kind of algorithm to find the minimum spanning tree by Joseph Kruskal published in 1956. There are also Prim algorithm and Boruvka algorithm to solve the same problem. These three algorithms are the application of the greedy algorithm. The different place between Kruskal algorithm and Boruvka algorithm is Kruskal algorithm also has effective when they have the same weight of edge in the diagram. There are four steps: 1.To build a new graph G and G has the same node in the original image, but there is no edge. 2. Take all the edges from smallest to largest in the light of weight. 3.At the beginning of alue minimum weight of edge, if this side connecting two nodes in a graph G is not in the same connected components, then add the edges to the graph G. 4.Repeat 3 until all nodes in the graph G are in the same connected components.
Optimal Rules
Kruskal's algorithm is a solution to the Shortest Spanning Tree Problem. Kruskal's algorithm first selects n-1 edges with total n end point. The optimal rule is picking the remained edge left that will not form a circle and also with the minimize cost to join the selected edge set. (A Tree is a connected graph with no cycle)
Also notes that if the edge picked will form a circle will not be able to form a tree. There always e steps in Kruskal Algorithm (e equal to the edge in the tree). We consider the cost increase in ordered these e edges. When we consider if when select it to our selected edge set we consider if it will cause a circle of the edge set.
KRUSKAL
Kruskal's algorithm(similar to cheapest-link algorithm) is an algorithm used for computing the minimum spanning tree of a undirected edge-weighted graph.
Kruskal's algorithm works by choosing, on each iteration, the cheapest possible edge that does not create a cycle with edges already on the tree. Thus, generally, Kruskal's algorithm builds the MST by creating many disjoint trees that eventually coalesce into one spanning tree. For a visualization, see here (try the large graph to see how Kruskal creates disjoint trees along the way).
PRIM
The main alternative to Kruskal's algorithm for computing a minimum spanning tree is known as Prim's algorithm. Prim's algorithm computes the MST by adding edges to a single connected tree until all vertices have been included in the tree. In other words, start at an arbitrary vertex. Then add the cheapest edge that connects a vertex on the tree to a non-tree vertex. Repeat this procedure until V-1 edges have been added(a tree of a graph has exactly V-1 edges assuming the graph is connected). For a visualization of Prim's algorithm, see here.
For another example of Prim's algorithm:
G-C 3 E-D 8 D-H 6 I-D 1 J-E 15 I-E 11 G-F 16 H-G 13 I-H 12 J-I 9
Represented graphically as:
(A)------14-----(B)------2------(C)------10-----(D)------8------(E)
| /| /| /| /|
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
5 7 17 3 4 6 1 11 15
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
|/ |/ |/ |/ |
(F)------16-----(G)------13-----(H)------12-----(I)------9------(J)
If we start Prim's algorithm from G, the order in which edges are added to the MST (edge specified by weight) is :
3 2 4 6 1 7 5 8 9
Note that it is not necessary that edges are added from cheapest to most expensive, as is the case for Kruskal. Also, note how the edges added form one connected tree at each stage, which is not necessarily true of Kruskal.
CUT PROPERTY
A cut of a graph divides the vertices into two nonempty disjoint sets. A crossing edge of the cut is any edge that connects vertices in different sets.
The cut property states that given any cut in the graph, the cheapest crossing edge must be in the MST.
Proof: Assume distinct edge weights, although it is clear that if two crossing edges are both the cheapest, either can be included. The proof is by contradiction. Define e to the cheapest crossing edge and let T* be the MST. Suppose T* does not contain e. Then T* must contain some other crossing edge f(since the MST is connected). If we add e to T*, we now get a cycle. Since e was defined to be the cheapest crossing edge, we can remove f from T* and we now have an MST of lower weight (removing an edge in a cycle doesn't affect connectedness). But this is a contradiction to the definition of T* meaning e must be in T*.
The reason Kruskal and Prim correctly compute the MST is due to the Cut Property. As outlined in the procedure for Prim above, at each stage Prim looks at the set of edges connecting tree vertices to non-tree vertices(i.e crossing edges). Prim then selects the cheapest crossing edge which, by the Cut Property, must be in the MST. After V-1 iterations, Prim has selected V-1 edges that all belong to the MST. Since there are exactly V-1 edges in the MST, Prim must have computed the MST.
RUNNING TIME
Depending on the implementation, Prim can run in time O(ElogE) or O(ElogV). Both implementations use a minimum priority queue to support the operations of finding the minimum crossing edge. However, the logE version is known as "lazy" Prim since it allows edges no longer eligible to be added to the tree to remain on the priority queue. The logV version is known as "eager" Prim, and stores only eligible edges on the priority queue.
Borůvka
There is another alternative to Kruskal's algorithm is Borůvka's algorithm.Borůvka's algorithm is an algorithm for finding a MST in a graph for which all edge weights are distinct. The way to use this algorithm is first to mark every vertex and finding the cheapest edge for each vertex and no matter the edges already added. And use this way until a tree spaning all vertices is completed. Here is a example to use the Borůvka's algorithm:
First mark each vertex in the graph.
Then, find the minimum edge for every vertice.(Some of them add twice,like AD,CE,it's OK). Now this graph divide to two part:{A,B,D,F} and {C,E,G}
Now add the minimun edge between this two part. It is the same edge,BE/EB. Finally, there is the MST.
Also, there is an animation to show the process of Borůvka's algorithm. click.
CONCLUSION
All three algorithms are greedy algorithms and each of them has the same worst-case running time. Kruskal's algorithm starts with an edge, Prim's algorithm starts with a vertex and Borůvka's algorithm start to find the minimum edge for a vertex. Kruskal's algorithm and Borůvka's algorithm can function on disconnected graphs but in Prim's algorithm, the graph must be connected. Different structure and data cause different approach to application. These three algorithms can be used to find the MST, which could be used in computer networking or laying cable in a wide area in the real world.
Reference
Igor Podsechin,Tampereen lyseon lukio,Tietotekniikka,"Comparing minimum spanning tree algorithms"http://www2.aka.fi/Tiedostot/Tiedostot/Viksu/Viksu%202008/IgorPodsechin.pdf
Pallavi Jayawant and Kerry Glavin(Communicated by Arthur T. Benjamin),"Minimum spanning trees ",2009.http://msp.org/involve/2009/2-4/involve-v2-n4-p06-p.pdf
Borůvka's algorithm themorem ,https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm
Kruskal's algorithm, https://en.wikipedia.org/wiki/Kruskal%27s_algorithm Yvette (I-Ting) Tsai,"A Randomized Algorithm to Find Minimum Spanning Tree",Dec 5, 2013.http://cs-www.bu.edu/faculty/homer/537/talks/Tsai-CS537_Report.pdf
