# include<iostream>
using namespace std;

int dinh[50][50],queue[50],daxet[50],truoc[50],n,dau,cuoi;

void docfile()
{
   FILE *f;
   f=fopen("D:\\DTH1.txt","r");
   if(f==NULL)
   {
      cout<<"\n LOI DOC FILE!!:";
      return;
   }
   fscanf(f,"%d",&n);
   for(int i=1;i<=n;i++)   
   {
      cout<<"\n ";
      daxet[i]=0;
      for(int j=1;j<=n;j++)
      {
         fscanf(f,"%d",&dinh[i][j]);
         cout<<dinh[i][j]<<" ";
      }
   }
}

void xuat()
{
   int i=cuoi;
   cout<<cuoi<<"<-";
   while(truoc[i]!=dau)
   {
      cout<<truoc[i]<<"<-";
      i=truoc[i];
   }
   cout<<dau<<"\n";
}

void BFS(int s)
{
   int dauQ=1;
   int cuoiQ=1;
   int u;
   queue[cuoiQ]=s;                                                                                                                                                                                                                                                                                                                                                                                                   
   daxet[s]=1;
   while(dauQ<=cuoiQ)
   {
      u=queue[dauQ];
      dauQ++;
      for(int i=1;i<=n;i++)
      {
         if(queue[cuoiQ]==cuoi)
            xuat();
         else if(dinh[u][i]==1&&daxet[i]==0)
         {
            cuoiQ++;
            queue[cuoiQ]=i;
            daxet[i]=1;
            truoc[i]=u;   
         }
      }
   }
}
void main()
{
   docfile();
   cout<<"\n NHAP DINH DAU: ";
   cin>>dau;
   cout<<"\n NHAP DINH CUOI:";
   cin>>cuoi;
   cout<<"\n KET QUA SAU KHI DUYET BFS:\n";
   BFS(dau);
}

#include<iostream>
using namespace std;

int dinh[50][50],truoc[50],n,dau,cuoi,daxet[50];

void docfile()
{
   FILE *f;
   f=fopen("D:\\DTH1.txt","r");
   if(f==NULL)
   {
      cout<<"\n Loi mo file!!!";
      return;
   }
   fscanf(f,"%d",&n);
   for(int i=1;i<=n;i++)
   {
      cout<<"\n";
      for(int j=1;j<=n;j++)
      {
         fscanf(f,"%d",&dinh[i][j]);
         cout<<dinh[i][j]<<" ";
      }
   }
}

void xuat()
{
   int i=cuoi;
   cout<<cuoi<<"<-";
   while(truoc[i]!=dau)
   {
      cout<<truoc[i]<<"<-";
      i=truoc[i];
   }
   cout<<dau<<"\n";
}
void DFS(int s)
{
   daxet[s]=1;
   for(int i=1;i<=n;i++)
   {      
      if(dinh[s][i]&&daxet[i]==0)
      {   truoc[i]=s;
         if(i==cuoi)
            xuat();
         else
         {
            DFS(i);
         }
         daxet[i]=0;//dong nay la de cho DFS co the chay het tat ca cac truong hop   
      }
   }   
}
void main()
{
   docfile();
   for(int i=1;i<=n;i++)
   {
      daxet[i]=0;
   }
   cout<<"\n DUYET DFS:";
   cout<<"\n NHAP DINH DAU: ";
   cin>>dau;
   cout<<"\n NHAP DINH CUOI:";
   cin>>cuoi;
   cout<<"\n KET QUA SAU KHI DUYET DFS:\n";
   DFS(dau);
}

#include<iostream>
using namespace std;
#define max 50
int n,t,s,truoc[max],dinh[max][max],d[max];
bool final[max];

void docfile()
{
   FILE *f;
   f=fopen("D:\\Dijikstra.txt","r");
   if(f==NULL)
   {
      cout<<"\n LOI DOC FILE";
      return;
   }
   fscanf(f,"%d",&n);
   for(int i=1;i<=n;i++)
   {
      for(int j=1;j<=n;j++)
      {
         fscanf(f,"%d",&dinh[i][j]);
      }
   }
   fclose(f);
}

void insolieu()
{
   cout<<"\n SO DINH CUA DO THI:"<<n;
   cout<<"\n MA TRAN KHOANG CACH:";
   for(int i=1;i<=n;i++)
   {
      cout<<"\n";
      for(int j=1;j<=n;j++)
      {         
         cout<<dinh[i][j]<<" ";
      }
   }
}

void inketqua()
{
   cout<<"\n DUONG DI NGAN NHAT TU"<<s<<" DEN "<<t<<": ";
   int i=t;
   cout<<t<<"<-";
   while(truoc[i]!=s)
   {
      cout<<truoc[i]<<"<-";
      i=truoc[i];
   }
   cout<<s;
   cout<<"\n DO DAI CUA DUONG DI LA:"<<d[t];
}

void Dijikstra()
{
   int v,u,minp;
   cout<<"\n TIM DUONG DI TU:";
   cin>>s;
   cout<<"\n DEN:";
   cin>>t;   
   for(v=1;v<=n;v++)
   {      
      d[v]=dinh[s][v];
      truoc[v]=s;
      final[v]=false;         
   }
   truoc[s]=0;
   d[s]=0;
   final[s]=true;
   while(!final[t])
   {
      // tim u la dinh co nhan tam thoi nho nhat
      minp=max;
      for(v=1;v<=n;v++)
         if(!final[v]&&minp>d[v])
         {
            u=v;
            minp=d[v];
         }
         final[u]=true;
         if(!final[t])
            for(v=1;v<=n;v++)
               if(!final[v]&&(d[u]+dinh[u][v])<d[v])
               {
                  d[v]=d[u]+dinh[u][v];
                  truoc[v]=u;
               }
      }   
}

void main()
{
   docfile();
   insolieu();
   Dijikstra();
   inketqua();
   system("pause");
}

#include<iostream>
using namespace std;
#include<stdio.h>
#include<conio.h>
//int arn[50];
//int arm[5000];
int n,m,MinL;
int Dau[5000],Cuoi[5000],W[5000];
int DauT[50],CuoiT[50],Father[50];
bool Connect;
void Nhapdl()
{
   FILE *f;
   f=fopen("D:\\Cay Khung.txt","r");
   if(f==NULL)
      cout<<"\n LOI DOC FILE";
   fscanf(f,"%d",&n);
    fscanf(f,"%d",&m);
   for(int i=0; i<m;i++)
   {
            fscanf(f, "%d",&Dau[i]);
            fscanf(f,"%d",&Cuoi[i]);
            fscanf(f,"%d",&W[i]);
            //cout<<a.dt[i][j]<<" ";
         
   }
   fclose(f);
}

void Indulieu()
{
   cout<<"\n So dinh:"<<n<<"\n So canh:"<<m;
   cout<<"\n Dinh dau Dinh cuoi Do dai";
   for(int i=0;i<m;i++)
   {
      cout<<"\n"<<Dau[i]<<" "<<Cuoi[i]<<" "<<W[i];
   }
}

void Heap(int First,int Last)
{
   int j,k,t1,t2,t3;
   j=First;
   while(j<=Last/2)
   {
      if(2*j<Last&&W[2*j+1]<W[2*j])
   
         k=2*j+1;
      else
         k=2*j;
      if(W[k]<W[j])
      {
         t1=Dau[j];
         t2=Cuoi[j];
         t3=W[j];
         Dau[j]=Dau[k];
         Cuoi[j]=Cuoi[k];
         W[j]=W[k];
         Dau[k]=t1;
         Cuoi[k]=t2;
         W[k]=t3;
         j=k;
      }
      else
         j=Last;
   }
}

int Find(int i)
{
   int Tro;
   Tro=i;
   while(Father[Tro]>0)
      Tro=Father[Tro];
   return Tro;
}

void Union(int i,int j)
{
   int x;
   x=Father[i]+Father[j];
   if(Father[i]>Father[j])
   {
      Father[i]=j;
      Father[j]=x;
   }
   else
   {
      Father[j]=i;
      Father[i]=x;
   }
}

void Kruskal()
{
   int i,Last,u,v,r1,r2,Ncanh,Ndinh;
   // khoi tao mang Father danh dau cay con va khoi tao Heap
   for(i=1;i<n;i++)
   {
      Father[i]=-1;
   }
   for(i=m/2;i>1;i--)
   {
      Heap(i,m);
   }
   Last=m;
   Ncanh=0;
   Ndinh=0;
   MinL=0;
   Connect=true;
   while(Ndinh<n-1&&Ncanh<m)
   {
      Ncanh=Ncanh+1;
      u=Dau[1];
      v=Cuoi[1];
      //kiem tra u va v co thuoc cung 1 cay con khong
      r1=Find(u);
      r2=Find(v);
      if(r1!=r2)
      {
         //ket nap canh (u,v) vao cay khung
         Ndinh=Ndinh+1;
         Union(r1,r2);
         DauT[Ndinh]=u;
         CuoiT[Ndinh]=v;
         MinL=MinL+W[1];
      }
      //to chuc lai Heap
      Dau[1]=Dau[Last];
      Cuoi[1]=Cuoi[Last];
      W[1]=W[Last];
      Last=Last-1;
      Heap(1,Last);
   }
   if(Ndinh!=n-1)
      Connect=false;
}

void Inketqua()
{
   int i;
   cout<<"\n ******************************************** \n";
   cout<<"\n **            Ket Qua tinh toan          ** \n";
   cout<<"\n ******************************************** \n";
   cout<<"\n Do dai cua cay khung nho nhat:"<<MinL;
   cout<<"\n Cac canh cua cay khung nho nhat";
   for(i=1;i<n-1;i++)
      cout<<"\n ("<<DauT[i]<<","<<CuoiT[i]<<")";
   cout<<"\n ******************************************** \n";
}

int main()
{
    clrscr();
   Nhapdl();
   Indulieu();
   Kruskal();
   if(Connect)
      Inketqua();
   else
      cout<<"\n Do thi khong lien thong";
   getch();
}