Sa se verifice daca un graful reprezinta un arbore.

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;
}
%d bloggers like this: