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;
     }
    }
   }
  }
 }

 

 


AWS Low Cost Mailing List Using phpList And SES

Running a mailing list is not easy or cheap, but if you use AWS it can be. Find out how to create a low-cost and highly effective mailing list server.



QuickSort Exposed

QuickSort was published in July 1961 and so is celebrating its 60th birthday.  QuickSort is the most elegant of algorithms and every programmer should study it. It is also subtle and this often m [ ... ]


Other Projects


Apache Updates Geronimo Arthur
28/03/2024

Apache Geronimo Arthur has been updated with support for Common-compress, XBean, and ensures the default options are compatible with last GraalVM release.



Supersimple - Deep Insights From Data
02/04/2024

Announcing $2.2 Million in pre-seed funding, the Estonian startup Supersimple has launched an AI-native data analytics platform which combines a semantic data modeling layer with the ability to answer [ ... ]


More News

raspberry pi books

 

Comments




or email your comment to: comments@i-programmer.info

<ASIN:1584885491>



Last Updated ( Thursday, 25 February 2016 )