MST

** MST(Minimum Spanning Tree)

l  Spanning Tree: acyclic connected subgraph containing all nodes

Ex)

l  MST: a spanning tree with weight less than or equal to the weight of every other spanning tree

l  Kruskal’s algorithm : G(V,E):O(|E|*log|E|)    * Prim’s algorithm

1.     Create a new graph T with the same vertices as G, but no edges (yet)

{1} {2}  {3} {4}  {5}

{1,2}   {3,4}    {5}

{1,2} {3,5} {4}

{1,2,3,5} {4}

{1,2,3,4,5}

1.     Make a list of all the edges in G.

2.     Sort the edges by weight, from lowest to highest

3.     Iterate through the edges in sorted order

For each edge(u,w): If u and w are not connected by a path in T, add (u,w) to T

O(log|E|) using disjointed sets