constructie vectorul TATA

Se citeste un arbore cu n varfuri dat prin vectorul muchiilor si apoi se citeste varful radacina. Sa se construiasca si sa se afiseze vectorul TATA.

vector_tata2noduri1

Vectorul de tati de declara astfel: T[i]=parintele(tata) nodului i.

Pentru arborele din figura vectorul TATA este 0,1,2,1 si radacina este 1.Muchiile care se citesc sunt 1-2,2-1,1-4

#include<iostream.h>
int n, r, T[20], a[20][20], p[20];void citire()
{ int i,x,y;
  cout<<“nr de noduri: “;cin>>n;
  cout<<“cititi muchiile de forma x-y : “<<endl;
  for(i=1;i<=n-1;i++)
    { cin>>x>>y;
      a[x][y]=a[y][x]=1;;
    }
  cout<<“dati radacina : “<<endl;
  cin>>r;
}void BF(int r)
{  int s,d,i,x[100];
   d=s=1;
   x[1]=r; p[r]=1;
   while (s<=d)
   { for(i=1;i<=n;i++)
      if(a[x[s]][i] &&!p[i])
    { d++; x[d]=i;
      p[i]=1; T[i]=x[s];
    }
     s++;
   }
}void main()
{ int i;
  citire();
  BF(r);
  cout<<“vectorul TATA este :”<<endl;
  for(i=1;i<=n;i++) cout<<T[i]<<” “;
}

arbori binari vector TATA

Se citeste un arbore cu n varfuri dat prin vectorul TATA.
1) Sa se afiseze muchiile arborelui
2) Sa se construiasca si sa se afiseze matricea de adiacenta a arborelui.

noduri1vector_tata1

Observatie: vectorul TATA  precizeaza pentru fiecare varf i, nodul TATA[i] care reprezinta parintele sau

Pentru arborele din imagine vectorul TATA este: 0,1,2,1.

#include<iostream.h>
int n, t[20], a[20][20];void afis()
{ int i,j;
  for(i=1;i<=n;i++)
    { for(j=1;j<=n;j++)
     cout<<a[i][j]<<” “;
     cout<<endl;
    }
}void main()
{ int i;
  cout<<“nr de noduri: “;cin>>n;
  cout<<“dati vectorul tata “<<endl;
  for(i=1;i<=n;i++)
  {
  cout<<“t[“<<i<<“]=”;
  cin>>t[i];
  }
  cout<<“muchiile sunt: “<<endl;
  for(i=1;i<=n;i++)
    if(t[i]!=0)
      { cout<<“[“<<t[i]<<“,”<<i<<“] “;
    a[i][t[i]]=a[t[i]][i]=1;
      }
  cout<<endl;
  cout<<“matricea de adiacenta este: “<<endl;
  afis();
}

arbore partial de cost minim algoritmul lui Kruskal

Sa se determine un arbore partial de cost minim folosind algoritmul Kruskal

Pentru memorarea muchiilor grafului si a costurilor acestora se defineste o structura de date cu trei campuri (nodurile muchiei si costul ei) pe care o numim muchie

#include<iostream.h>
#include<fstream.h>
typedef struct{int u,v,c;} muchie;
int l[30],n,m;
muchie e[30];
void citire()
{int i;
fstream f(“apm.txt”, ios::in);
f>>n;
f>>m;
for(i=1;i<=m;i++)
f>>e[i].u>>e[i].v>>e[i].c;
f.close();}

void main()
{int k,ultim,i,u,v,ct,ind,ms,lu,lv;
muchie aux;
citire();
for(i=1;i<=n;i++)
l[i]=i;
ultim=m;
while(ultim>1)
{k=0;
for(i=1;i<=ultim-1;i++)
if(e[i].c>e[i+1].c)
{aux=e[i];
e[i]=e[i+1];
e[i+1]=aux;
k=1;
}
ultim=k;}
cout<<“APM contine muchiile:”<<endl;
ct=0;ms=0;ind=0;
while(ms<n-1)
{
do
ind++;
while(l[e[ind].u]==l[e[ind].v]);
u=e[ind].u;
lu=l[u];
v=e[ind].v;
lv=l[v];
cout<<u<<”  “<<v<<endl;
ct=ct+e[ind].c;
ms++;
for(i=1;i<=n;i++)
if(l[i]==lu)
l[i]=lv;}
cout<<“costul APM este:”<<ct;}

numarul de nivele ale unui arbore

Numarul  de nivele ale unui arbore

 

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
struct nod
{int nr;
nod* st,*dr;
};
nod *c;
int coada[20],s[20],i,sf;
nod *r[20];

nod *arb()
{int n;
nod *c;
cout<<“n=”;cin>>n;
if(n)
{
c=new nod;
c->nr=n;
c->st=arb();
c->dr=arb();
return c;
}
else return 0;
}

int max(int x,int y)
{if (x>y) return x;
else return y;
}

int h(nod *r)
{
if (r==0) return 0;
else return 1+max(h(r->st),h(r->dr));
}

int h1(nod *r)
{if(r==0) return 0;
else return 1+h1(r->st);
}

int h2(nod *r)
{if(r==0) return 0;
else return 1+h2(r->dr);
}

void main()
{int a,b;
//clrscr();
c=arb();
cout<<h(c)<<endl;
cout<<h1(c)<<endl;
cout<<h2(c)<<endl;
getch();
}

codul pruffer

Codul pruffer

#include<iostream.h>
#include<conio.h>
int t[50],pt[50],i,j,k,n,gasit;

void main()
{ cout<<“n=”;cin>>n;
for(i=1;i<=n-2;i++)
{cout<<“pt[“<<i<<“]=”;
cin>>pt[i];
}
pt[n-1]=n;
for(i=1;i<=n-1;i++)
{k=1;
do
{gasit=0;
for(j=1;j<=i-1;j++)
if(t[j]==k) gasit=1;
if(!gasit)
for(j=i;j<=n-1;j++)
if(pt[j]==k) gasit=1;
if(gasit) k++;
} while(gasit);
t[i]=k;
}
for(i=1;i<=n-1;i++) cout<<t[i]<<” “;
cout<<endl;
getch();
}

arborescenta

Arborescenta

#include<fstream.h>
#include<conio.h>
int a[20][20],b[20][20],s[20],gasit,ok,radacina,n,i,j,suma,r;

void citire(char nume[10],int a[20][20],int& n)
{
fstream f(nume,ios::in);
int i,j;
f>>n;
while (f>>i>>j) a[i][j]=1;
f.close();
}

void df(int nod)
{
int k;s[nod]=1;
for(k=1;k<=n;k++)
if(a[nod][k]==1 || a[k][nod]==1)
{a[k][nod]=a[nod][k]=0;
if (s[k]==0) df(k);
else gasit=1;
}
}

void df1(int nod)
{
int k;s[nod]=1;
for(k=1;k<=n;k++)
if (a[nod][k]==1 && s[k]==0) df1(k);
}

void main()
{
citire(“graf.txt”,a,n);cout<<“n->”<<n<<endl;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) b[i][j]=a[i][j];
df(1);
for(i=1;i<=n;i++) suma+=s[i];
if(suma!=n) cout<<“nu este conex”<<endl;
else cout<<“este conex”<<endl;
if(gasit) cout<<“are cel putin un ciclu”<<endl;
else cout<<“nu are cicluri”;
if (suma==n && !gasit)
{cout<<“este arbore”<<endl;
ok=1;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) a[i][j]=b[i][j];
if (ok)
{r=1;
do
{suma=0;for(i=1;i<=n;i++)s[i]=0;
df1(r);
for(i=1;i<=n;i++) suma+=s[i];
if (suma==n)
{cout<<“radacina este “<<r<<endl<<“este arborescenta”<<endl;
radacina=1;
}
else r++;
}while (!radacina && r<=n);
if(!radacina) cout<<“nu are radacina”;
}
getch();
}

arbore partial de cost minim

Arbore partial de cost minim

 

#include<fstream.h>
#include<iostream.h>
float a[20][20],min,cost;
int s[20],t[20],n,i,j,k,v;

void citire(char nume[20],float a[20][20],int &n)
{
int i,j;
float c;
fstream f(nume,ios::in);
f>>n;
for(i=1;i<=n;i++) a[i][i]=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) a[i][j]=100;
while(f>>i>>j>>c) a[i][j]=a[j][i]=c;
f.close();
}

void main()
{
cost=0;
citire(“graf2”,a,n);
cout<<n<<endl;
cout<<“nodul de pornire:”;cin>>v;
for(i=1;i<=n;i++)
if(i==v) s[i]=0;
else s[i]=v;

for(k=1;k<=n-1;k++)
{
min=100;
for(i=1;i<=n;i++)
if(s[i])
if(a[s[i]][i]<min)
{min=a[s[i]][i];
j=i;
}
t[j]=s[j];
cost+=a[s[j]][j];s[j]=0;
for(i=1;i<=n;i++)
if(s[i] && a[i][s[i]]>a[j][i]) s[i]=j;
}
cout<<“cost=”<<cost<<endl;
for(i=1;i<=n;i++) cout<<t[i]<<” “<<endl;
}

arbori de cautare

Arbori de cautare

#include<iostream.h>
#include<conio.h>
struct nod
{int nr;
nod *as,*ad;
};
nod *v,*man;
int k;

void inserare(nod*& c,int k)
{
if(c)
if(c->nr==k)
cout<<“nr inserat”<<endl;
else
if(c->nr<k) inserare(c->ad,k);
else inserare(c->as,k);
else
{c=new nod;c->as=c->ad=0;
c->nr=k;}
}

void parcurg(nod* c)
{if(c)
{parcurg(c->as);
cout<<c->nr<<endl;
parcurg(c->ad);
}
}

void main()
{v=0;
do{
cout<<“k=”;cin>>k;

inserare(v,k);}

while(k!=0);
parcurg(v);
getch();
}

parcurgere arbore binar

Sa se parcurga un arbore binar

 

#include<iostream.h>
#include<conio.h>
struct nod
{int nr;
nod* st,*dr;
};
nod *c;
int nrst,nrdr;

void svd(nod *c)
{
if(c)
{svd(c->st);
cout<<c->nr;
svd(c->dr);
}
}

void vsd(nod *c)
{
if(c)
{cout<<c->nr;
vsd(c->st);
vsd(c->dr);
}}

void sdv(nod *c)
{
if(c)
{
sdv(c->st);
sdv(c->dr);
cout<<c->nr;
}
}

nod *arb()
{int n;
nod *c;
cout<<“n=”;cin>>n;
if(n)
{
c=new nod;
c->nr=n;
c->st=arb();
c->dr=arb();
return c;
}
else return 0;
}

void main()
{
clrscr();
c=arb();
svd(c);
cout<<endl;
vsd(c);
cout<<endl;
sdv(c);
cout<<endl;
getch();
}