The Minimum Spanning Tree - Prim's Algorithm
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 WPF

The 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.



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 [ ... ]


Other Projects


Bombe Goes On Display To Celebrate Alan Turing Anniversary
23/06/2018

Today, 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 [ ... ]



Open Source GraphQL Engine Launched
11/07/2018

An open source GraphQL Engine has been launched that can be used with applications based on Postgres without the need for backend GraphQL processing code.


More News

justjsquare

 



 

Comments




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

<ASIN:1584885491>



Last Updated ( Thursday, 25 February 2016 )
 
 

   
Banner
RSS feed of all content
I Programmer - full contents
Copyright © 2018 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.