Algoritmul lui Lee

 

Fiind dat un graf orientat, se cere determinarea  lungimea lanturilor (minime) de la un varf  la toate celelalte

 

 #include<fstream.h>

int a[20][20],n,m,viz[100],c[100],ic,sc,prim;

int t[20]; 

void drum(int i)

{if(t[i]!=0)

       drum(t[i]);

 cout<<i<<" ";

void lanturi()

{

 if(ic<=sc)

     {prim=c[ic];

     for(int k=1;k<=n;k++)

             if(a[prim][k]==1&&viz[k]==0)

                 {sc++;

                  c[sc]=k;

                  viz[k]=viz[prim]+1;

                  t[k]=prim;

                  }

      ic++;

      lanturi();

     }

 }

 void main()

{int x,y,j;

fstream f;

 f.open("lee.in",ios::in);

 if(f)

   cout<<"ok!"<<endl;

 else

   cout<<"eroare";

 f>>n>>m;

 for(int i=1;i<=m;i++)

    {f>>x>>y;

     a[x][y]=1;}

cout<<endl<<"matricea de adiacente"<<endl;

for(i=1;i<=n;i++)

   {for(j=1;j<=n;j++)

       cout<<a[i][j]<<" ";

   cout<<endl;}

cout<<endl<<"lungime lanturi incepand de la "<<endl;

cin>>x;

cout<<"pana la ";

cin>>y;

ic=sc=1;

c[ic]=x;

viz[x]=1;

lanturi();

cout<<"lantul minim are lungimea "<<viz[y]<<" ";

cout<<endl;

cout<<"vectorul viz "<<endl;

for(i=1;i<=n;i++)

   cout<<viz[i]<<" ";

cout<<endl<<"vectorul t "<<endl;

for(i=1;i<=n;i++)

   cout<<t[i]<<" ";

cout<<endl<<"drumul este "<<endl;

drum(y);

}

{joscommentenable}