Prim ------------------

#include<conio.h>
#include<stdio.h>
#include<math.h>
#define vocuc 22222


typedef struct
{
int x;
int y;
}Point;

typedef struct
{
   int v1;
   int v2;
   double trongso;
}EGDE;

typedef struct
{
int nVer;
double **a;
Point *p;
EGDE *T;
double tongtrongsoT;
}Graph;

void DocToaDoDinh(Graph &g);
double KhoangCach2Point(Point a, Point b);
void MaTranKeTrongSo(Graph &g);
int Prim(Graph &g);
int TimCanhNhoNhat(Graph g, EGDE  &canh, int labels[]);
void xuatT(Graph g);
void main()
{
   Graph gp;
   DocToaDoDinh(gp);
   MaTranKeTrongSo(gp);
   xuatT(gp);
}

void xuatT(Graph g)
{
   FILE *f;
   f=fopen("primOutput.txt","wt");

   if(Prim(g)==0)
   {
      fprintf(f,"Do thi khong co cay khung");
   }
   else
   {
      fprintf(f,"Tong chieu dai tuyen duong: %lf",g.tongtrongsoT);
      fprintf(f,"\n");
      for(int i=0;i<g.nVer-1;i++)
      {
         fprintf(f,"%2d      %2d      %2lf",g.T[i].v1,g.T[i].v2,g.T[i].trongso);
         fprintf(f,"\n");
      }
   }
   fclose(f);
   
}


int TimCanhNhoNhat(Graph g, EGDE  &canh, int *labels)
{
canh.v1=-1;
for(int i=0;i<g.nVer;i++)
{
   if(labels[i]==1)
   {
      for(int j=0;j<g.nVer;j++)
      {
         if(labels[j]==0&&g.a[i][j] != vocuc)
            if(canh.v1==-1 || canh.trongso>g.a[i][j])
            {
               canh.v1=i;
               canh.v2=j;
               canh.trongso=g.a[i][j];
            }
      }
   }      
}
if(canh.v1==-1) return 0;
return 1;
}

int Prim(Graph &g)
{
   int dinh=0;
   EGDE canh;
   int *labels=new int [g.nVer];

   g.T=new EGDE [g.nVer];

   for(int i=0;i<g.nVer;i++)
      labels[i]=0;
   g.tongtrongsoT=0;
   //Xet dinh 0
   labels[0]=1;
   while(dinh<g.nVer-1)
   {
      if(TimCanhNhoNhat(g,canh,labels)==0)  return 0;
      g.T[dinh]=canh;
      labels[canh.v2]=1;
      g.tongtrongsoT=g.tongtrongsoT+canh.trongso;
      dinh++;
   }
   return 1;
}

double KhoangCach2Point(Point a, Point b)
{
   return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}

void MaTranKeTrongSo(Graph &g)
{
   //Khai bao ma tran ke
   g.a=new double *[g.nVer];
   for(int i=0;i<g.nVer;i++)
      g.a[i]=new double[g.nVer];

   for(int i=0;i<g.nVer;i++)
   {
      g.a[i][i]=vocuc;
      for(int j=i+1;j<g.nVer;j++)
         g.a[i][j]=g.a[j][i]=KhoangCach2Point(g.p[i],g.p[j]);
   }
}

void DocToaDoDinh(Graph &g)
{
   FILE *f;
   f=fopen("cities.txt","rt");
   fscanf(f,"%d",&g.nVer);
   //Khai bao ma tran Point
   g.p=new Point [g.nVer];

   for(int i=0; i<g.nVer; i++)
   {
      fscanf(f,"%d");
      fscanf(f,"%d",&g.p[i].x);
      fscanf(f,"%d",&g.p[i].y);
      fscanf(f,"\n");
   }
   fclose(f);
}