Algoritmul LEE

#include<iostream>

#include<fstream>

using namespace std;

int a[20][20],c[20],v[20],ns,n;

int prim;

int ultim;

void citire(int a[20][20],int &n)

{

ifstream f("graf.in");

int x,y;

f>>n;

while(f>>x>>y)

a[x][y]=a[y][x]=1;

f.close();

}

void afisare(int a[20][20],int n)

{

cout<<"Matricea de adiacenta este : "<<endl;

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

{

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

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

cout<<endl;

}

}

int exista_nod_nevizitat(int v[20],int n)

{

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

if(v[i]==-1)

return i;

return 0;

}

int main()

{ citire(a,n);

afisare(a,n);

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

v[i]=-1;

cout<<"Dati nodul de start : "; cin>>ns;

v[ns]=0;

cout<<"Parcurgerea in latime este : ";

cout<<ns<<" ";

prim=ultim=1;

c[ultim]=ns;

while(exista_nod_nevizitat(v,n)!=0)

{

if(prim<=ultim)

{//adaug la coada toate nodurile adiacente si nevizitate

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

if(a[c[prim]][i]==1)

if(v[i]==-1)

{

ultim++;

c[ultim]=i;

cout<<i<<" ";

v[i]=v[c[prim]]+1;

}

prim++;

}

else

{

ns=exista_nod_nevizitat(v,n);

v[ns]=0;

prim=ultim=1;

c[prim]=ns;

cout<<ns<<" ";

}

}

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

cout<<"Distanta minima dintre nodul "<<i<<" si "<<ns<<" este "<<v[i]<<endl;

return 0;

}