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

 

 


A C# Oscilloscope Display In Windows Forms

If you need a real time stripchart or oscilloscope style display for a Windows forms project then the good news is that it can be done without having to move outside of C#.



SNTP time class

SNTP is a network protocol for obtaining an accurate time and it is an interesting exercise to build an SNTP client. In this article the language used is C# but it is easy enough to generalise to a la [ ... ]


Other Projects


Microsoft SQL Operations Studio With Smart GUI
27/11/2017

Microsoft has released a preview of a free tool for managing SQL Server, Azure SQL Database, and Azure SQL Data Warehouse. SQL Operations Studio provides wider options than the Windows-only SQL Server [ ... ]



Kotlin 1.2 Released With Cross Platform Support
30/11/2017

JetBrains has just announced the release of Kotlin 1.2 and it is already supported in Android Studio 3. What's new and what's missing?


More News

 
 

 

blog comments powered by Disqus

<ASIN:1584885491>



Last Updated ( Thursday, 25 February 2016 )
 
 

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