spanning tree

MST is used to connect a bunch of points to each other as cheaply as possible. Applications clustering networking Blazingly fast greedy algorithms There are many greedy algorithm, but we will talk about 2: Prim’s algo [1957, also djikstra’ 1959] or Jarnic found it in 25 years earlier. Kruskal’s algo[1956]. Will be using union find data-structure. They are blazingly fast as they are almost close to linear time of number of edges: [Read More]