Se citeste un graf neorientat prin matricea de adiacenta. Se cere sa se verifice daca graful reprezinta un arbore.
Daca daca graful are n-1 muchii şi este conex atunci este arbore.
Solutie
using namespace std;
int viz[30],n,i,j,k,u,v,p,a[20][20],c[30],m=0;
int main()
{
cout<<"Dati numarul de varfuri n = ";
cin>>n;
for(i=1; i<=n-1; i++)
for(j=i+1; j<=n; j++)
{
cout<<"a["<<i<<","<<j<<"]= ";
cin>>a[i][j];
a[j][i] = a[i][j];
m+=a[i][j]; // m = nr. de muchii
}
cout<<"Dati varful de plecare ";
cin>>i;
for(j=1; j<=n; j++) viz[j]=0;
// parcurgem in latime graful neorientat
c[1]=i;
p=1; //prima pozitie
u=1; //ultima pozitie
viz[i]=1;
while(p<=u)
{
v=c[p];
for(k=1; k<=n; k++)
{
if( (a[v][k]==1) && (viz[k]==0) )
//daca primul nod din coada(v) are vecini k nevizitati atunci ii punem in coada
{
u++;
c[u]=k;
viz[k]=1;
}
}
p++;
}
int arbore=1; //presupunem ca este arbore
for(i=1; i<=n; i++)
if(!viz[1]) arbore=0;
//daca au ramas noduri nevizitate atunci nu este conex si deci nu este arbore
if(m==n-1 && arbore)
cout<<"este arbore";
else
cout<<"nu este arbore";
return 0;
}