kruskal

#include <iostream>
#include <string>
#include <math.h>
#include <fstream>
#include <time.h>

using namespace std;

struct vert{
  int x, y; // reprezentacja punktu na p³aszczyŸnie
};

struct edge
{
  int a, b; // numery wierzcho³ków, które krawêdŸ ³¹czy
  float len;  // jej d³ugoœæ
  bool chosen; // czy zosta³a wybrana
};


void InsertSort(edge t[], int r)
{
    for(int i=1; i< r; i++)
    {   int idx = i-1;
        edge temp = t[i];
        while(idx >= 0 && t[idx].len> temp.len)
         {
           t[idx+1] = t[idx];
           idx--;
         }
        t[idx+1] = temp;
    }
}


float dist(vert A, vert B)
{
  return sqrt(pow(A.x - B.x,2)+pow(A.y - B.y,2));
}

edge* Kruskal(vert V[], int how_many)
{
  int *color = new int[how_many];
  for(int i=0; i< how_many; i++) color[i] = i;

  int n = 0;

  int num_of_edges = how_many * (how_many-1) *0.5;
  cout<<"num of edges"<<num_of_edges<<endl;

  edge *E = new edge[num_of_edges];
  for(int i=0; i< how_many; i++)
    for(int j=i+1; j< how_many; j++)
    {
      E[n].a = i; E[n].b = j;
      E[n].len = dist(V[i],V[j]);
      E[n].chosen = false;
      n++;
    }




  InsertSort(E, num_of_edges);

  int counter = 0;
  for(int i=0; i< num_of_edges; i++)
  {
    int c1 = color[E[i].a];
    int c2 = color[E[i].b];
    if (c1 != c2)
    {
      E[i].chosen = true;
      for(int j=0; j< how_many; j++)
        if(color[j]==c2) color[j]=c1;
      counter++;
      if (counter==how_many-1)
        break;
    }

  }



  return E;
}



int main()
{
  vert* V = new vert[6];
  V[0].x = 1; V[0].y = 1;
  V[1].x = 2; V[1].y = 2;
  V[2].x = 1; V[2].y = 2;
  V[3].x = 1; V[3].y = 0;

  V[4].x = 17; V[4].y = 1;
  V[5].x = 20; V[5].y = 1;

  edge* res;
  res = Kruskal(V,6);

  for(int i=0; i<15; i++)
    cout<<res[i].a<<"--"<<res[i].b<<" dlugosc "<<res[i].len<<" "<<(res[i].chosen?"*":"")<<endl;


}