The Minimum Spanning Tree - Prim's Algorithm

### New Book Reviews!

 The Minimum Spanning Tree - Prim's Algorithm
Written by Mike James
Thursday, 25 February 2016
Article Index
The Minimum Spanning Tree - Prim's Algorithm
Prim's Algorithm In C#
Implementing Prim's algorithm
Listing

## Listing

The complete listing is:

`using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;using System.Windows;using System.Windows.Controls;using System.Windows.Data;using System.Windows.Documents;using System.Windows.Input;using System.Windows.Media;using System.Windows.Media.Imaging;using System.Windows.Navigation;using System.Windows.Shapes;``namespace Prim{`` public partial class MainWindow : Window {  const int size = 10;  private Point[] Positions = new Point[size];  private Single[,] Network =                        new Single[size, size];  private Random R = new Random();``  public MainWindow()  {   InitializeComponent();  }``   private void setnet(Single[,] Net, Point[] Pos)  {   int maxlength = (int)(Math.Min(canvas1.Width,                           canvas1.Height) * 0.9);   int minlength = maxlength / size;   for (int i = 0; i < size; i++)   {    Pos[i].X = R.Next(minlength, maxlength);    Pos[i].Y = R.Next(minlength, maxlength);    for (int j = 0; j <= i; j++)    {     Net[i, j] = distance(Pos[i], Pos[j]);     Net[j, i] = Net[i, j];     if (i == j) Net[i, j] = 0;    }   }  }``  private Single distance(Point a, Point b)  {   return (Single)Math.Sqrt((a.X - b.X) *                                (a.X - b.X) +                                (a.Y - b.Y) *                                 (a.Y - b.Y));  }``  private void shownet(Single[,] Net)  {   canvas1.Children.Clear();   Line myLine;   for (int i = 0; i < size; i++)   {    for (int j = 0; j < i; j++)    {     if (Net[i, j] != 0)     {      myLine = new Line();      myLine.Stroke = Brushes.Black;      myLine.X1 = Positions[i].X;      myLine.X2 = Positions[j].X;      myLine.Y1 = Positions[i].Y;      myLine.Y2 = Positions[j].Y;      myLine.StrokeThickness = 1;      canvas1.Children.Add(myLine);     }    }   }   Rectangle myMarker;   for (int i = 0; i < size; i++)    {    myMarker = new Rectangle();    myMarker.Stroke = Brushes.Black;    myMarker.Fill = Brushes.Red;    myMarker.Height = 10;    myMarker.Width = 10;    myMarker.SetValue(Canvas.TopProperty,          Positions[i].Y - myMarker.Height / 2);    myMarker.SetValue(Canvas.LeftProperty,          Positions[i].X - myMarker.Width / 2);    canvas1.Children.Add(myMarker);   }  }``  private void button_Click(object sender,                              RoutedEventArgs e)  {   canvas1.Width = 600;   canvas1.Height = 600;   setnet(Network, Positions);   shownet(Network);  }``  private void Find_MST_Click(object sender,                              RoutedEventArgs e)  {   prims();  }``  void prims()  {   int[] included = new int[size];    int[] excluded = new int[size];``   Single[,] finished = new Single[size, size];``   int start = 0;   ``int finish = 0;``   for (int i = 0; i < size; i++)`

`   {    excluded[i] = i;    included[i] = -1;   }``   included[0] = excluded[R.Next(size)];   excluded[included[0]] = -1;``   for (int n = 1; n < size; n++)   {    closest(n, ref start, ref finish,                          included, excluded);``    included[n] = excluded[finish];    excluded[finish] = -1;``    finished[included[n], included[start]] =          Network[included[n], included[start]];    finished[included[start], included[n]] =          Network[included[start], included[n]];   }   shownet(finished);  }``   private void closest(int n, ref int start,     ref int finish,int[] included, int[] excluded)  {   Single smallest = -1;   for (int i = 0; i < n; i++)   {    for (int j = 0; j < size; j++)    {     if (excluded[j] == -1) continue;     if (smallest == -1) smallest =          Network[included[i], excluded[j]];     if (Network[included[i], excluded[j]] >                            smallest) continue;     smallest = Network[included[i], excluded[j]];      start = i;      finish = j;     }    }   }  } }`

 Mandelbrot Zoomer in WPFThe Mandelbrot set is fun, but implementing a simple viewer in WPF can be a challenge.Here's a project to plot the Mandelbrot set and allow the user to zoom in on any area of interest. + Full Project Useful Windows Screensavers - Including Windows 10 The screensaver is an example of a vestigial technology - it no longer serves its original purpose. However, this doesn't mean it isn't useful in other ways and it is supported on all versions of Wind [ ... ] + Full Project Other Projects

 Bombe Goes On Display To Celebrate Alan Turing Anniversary23/06/2018Today, on the 106th anniversary of the birth of Alan Turing, the UK National Museum of Computing is opening a gallery dedicated to the Bombe. Designed by Turing, this electro-mechanical machine was us [ ... ] + Full Story Open Source GraphQL Engine Launched11/07/2018An open source GraphQL Engine has been launched that can be used with applications based on Postgres without the need for backend GraphQL processing code. + Full Story More News