PPT On Kruskal’s Algorithm

Download

Kruskal’s Algorithm Presentation Transcript:
1.Minimum Spanning Trees

2.Kruskal’s Algorithm
Kruskal()
{
   T = ?;
   for each v ? V
      MakeSet(v);
   sort E by increasing edge weight w
   for each (u,v) ? E (in sorted order)
      if FindSet(u) ? FindSet(v)
         T = T U {{u,v}};
         Union(FindSet(u), FindSet(v));
}

3.Kruskal()
{
   T = ?;
   for each v ? V
      MakeSet(v);
   sort E by increasing edge weight w
   for each (u,v) ? E (in sorted order)
      if FindSet(u) ? FindSet(v)
         T = T U {{u,v}};
         Union(FindSet(u), FindSet(v));
}

4.Kruskal()
{
   T = ?;
   for each v ? V
      MakeSet(v);
   sort E by increasing edge weight w
   for each (u,v) ? E (in sorted order)
      if FindSet(u) ? FindSet(v)
         T = T U {{u,v}};
         Union(FindSet(u), FindSet(v));
}

5.Kruskal()
{
   T = ?;
   for each v ? V
      MakeSet(v);
   sort E by increasing edge weight w
   for each (u,v) ? E (in sorted order)
      if FindSet(u) ? FindSet(v)
         T = T U {{u,v}};
         Union(FindSet(u), FindSet(v));
}

6.Kruskal()
{
   T = ?;
   for each v ? V
      MakeSet(v);
   sort E by increasing edge weight w
   for each (u,v) ? E (in sorted order)
      if FindSet(u) ? FindSet(v)
         T = T U {{u,v}};
         Union(FindSet(u), FindSet(v));
}

7.Kruskal()
{
   T = ?;
   for each v ? V
      MakeSet(v);
   sort E by increasing edge weight w
   for each (u,v) ? E (in sorted order)
      if FindSet(u) ? FindSet(v)
         T = T U {{u,v}};
         Union(FindSet(u), FindSet(v));
}

8.Kruskal()
{
   T = ?;
   for each v ? V
      MakeSet(v);
   sort E by increasing edge weight w
   for each (u,v) ? E (in sorted order)
      if FindSet(u) ? FindSet(v)
         T = T U {{u,v}};
         Union(FindSet(u), FindSet(v));
}

9.Kruskal()
{
   T = ?;
   for each v ? V
      MakeSet(v);
   sort E by increasing edge weight w
   for each (u,v) ? E (in sorted order)
      if FindSet(u) ? FindSet(v)
         T = T U {{u,v}};
         Union(FindSet(u), FindSet(v));
}

10.Kruskal()
{
   T = ?;
   for each v ? V
      MakeSet(v);
   sort E by increasing edge weight w
   for each (u,v) ? E (in sorted order)
      if FindSet(u) ? FindSet(v)
         T = T U {{u,v}};
         Union(FindSet(u), FindSet(v));
}

11.Kruskal()
{
   T = ?;
   for each v ? V
      MakeSet(v);
   sort E by increasing edge weight w
   for each (u,v) ? E (in sorted order)
      if FindSet(u) ? FindSet(v)
         T = T U {{u,v}};
         Union(FindSet(u), FindSet(v));
}

12.Kruskal()
{
   T = ?;
   for each v ? V
      MakeSet(v);
   sort E by increasing edge weight w
   for each (u,v) ? E (in sorted order)
      if FindSet(u) ? FindSet(v)
         T = T U {{u,v}};
         Union(FindSet(u), FindSet(v));
}

13.Kruskal()
{
   T = ?;
   for each v ? V
      MakeSet(v);
   sort E by increasing edge weight w
   for each (u,v) ? E (in sorted order)
      if FindSet(u) ? FindSet(v)
         T = T U {{u,v}};
         Union(FindSet(u), FindSet(v));
}

14.Kruskal()
{
   T = ?;
   for each v ? V
      MakeSet(v);
   sort E by increasing edge weight w
   for each (u,v) ? E (in sorted order)
      if FindSet(u) ? FindSet(v)
         T = T U {{u,v}};
         Union(FindSet(u), FindSet(v));
}

15.Kruskal()
{
   T = ?;
   for each v ? V
      MakeSet(v);
   sort E by increasing edge weight w
   for each (u,v) ? E (in sorted order)
      if FindSet(u) ? FindSet(v)
         T = T U {{u,v}};
         Union(FindSet(u), FindSet(v));
}