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



WPF The Easy 3D Way

WPF provides a full 3D graphics experience without the need to master DirectX. It really is the easy 3D approach.


Other Projects


New WinDbg Available In Preview
18/09/2017

Microsoft has announced a preview version of a new WinDbg. The new version has been updated to have more modern visuals, faster windows, and built-on support for scripting.



Alexa Gadgets SDK For Voice-Enabled Play
02/10/2017

At the same time as launching new Echo products, Amazon has announced Alexa Gadgets and unveiled Echo Buttons, which can be controlled using the Alexa Gadgets SDK and the Gadgets S [ ... ]


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.