Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionvi [2012/03/01 03:48] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionvi [2012/03/01 03:54] (current) – [Implementing Kruskal's Algorithm] mugabej
@@ Line 65: / Line 65: @@
 >>>>>>>>>>>>>>>>> Find(u) takes O(logn) time \\
+==== Implementing Kruskal's Algorithm ====
+>>>>>>>>>>>>>>>>> T = {}
+>>>>>>>>>>>>>>>>> foreach (u ∈ V) make a set containing singleton u
+>>>>>>>>>>>>>>>>> for i = 1 to m
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> (u,v) = ei
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> if (u and v are in different sets)
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> T = T ∪ {ei}
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> merge the sets containing u and v
+>>>>>>>>>>>>>>>>> return T
+( The above algorithm, is from the class discussion)
+\\
+\\
+Kruskal's algorithm implemented as above runs in O(mlogn) time.
+\\
+\\
+This section was also interesting, although it contained some long proofs. I give it an 8/10