Extras din referat
Problema 1
Fie G un graf conex cu n varfuri.
Fiecarui arc (i,j) i se pune in corespondenta un cost c[i][j].
Sa se listeze toti arborii acestui graf si costurile lor.
Rezolvare:
#include <stdio.h>
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#define N 10
int c[N][N];
int valid(int *a,int k)
{if(k>0) if( c[a[k-1]][a[k]] ==0 ) return 0;
for(int j=0;j<k-1;j++)
if(a[j]==a[k])return 0;
return 1;
}
void afis(int a[],int n)
{cout<<"n";
for(int i=0;i<n;i++)
cout<<a[i]+1;
}
void arb(int n)
{int a[N],vb,cost,k;
cost=0;
k=0;a[k]=-1;
while(k>=0)
{ vb=0;
while(a[k]<n-1)
{ a[k]++;
vb=valid(a,k);
if(vb) { if(k>0) cost+=c[a[k-1]][a[k]];
break; }
}
if(vb)
if(k==n-1) { afis(a,n);
cout<<"nCostul arborelui:"<<cost;
cost-=c[a[k-1]][a[k]]; }
else{k++;a[k]=-1;}
else{
k--;
if(k>0)cost-=c[a[k-1]][a[k]];
}
}
}
void main()
{int n;
cout<<"Nr. de varfuri:(maxim"<<N<<")";
cin >>n;
cout<<"nMatricea costurilor este";
for(int i=0;i<n;i++)
{printf("n");
for(int j=0;j<n;j++)
{ if(i==j) { c[i][j]=0; continue; }
cout<<"tc["<<i+1<<"]["<<j+1<<"]=";
cin >>c[i][j];
}}
arb(n);
//getch();
}
Problema 2
Sa se determine daca intre doua noduri oarecare ale unui graf orientat exista sau nu drum.
Rezolvare
#include <stdio.h>
#include <iostream.h>
#define NMAX 20
void exista_drum(char n,char g[NMAX][NMAX],char dr[NMAX][NMAX])
{
char i,j,k,l;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
dr[i][j]=g[i][j];
for(l=2;l<n;l++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i!=j)
for(k=0;k<n;k++)
if(dr[i][k] && dr[k][j])
dr[i][j]=1;
}
void main()
{
char i,j,n,a[NMAX][NMAX],dr[NMAX][NMAX];
do
{
printf("nIntroduceti numarul de noduri (maxim %d): ",NMAX);
scanf("%d",&n);
}
while(n<1 && n>NMAX);
cout <<" Introduceti pentru fiecare arc:"<<endl;
cout <<"a[i,j]=1 - daca exista arc de la i catre j"<<endl;
cout <<"a[i,j]=0 - daca nu exista arc de la i catre jn"<<endl;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i!=j)
{
cout <<"a["<<i+1<<","<<j+1<<"]=";
cin>>a[i][j];
}
else
a[i][j]=1;
exista_drum(n,a,dr);
cout<<"Exista drumuri intre urmatoarele noduri ale grafului:"<<endl;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i!=j && dr[i][j]==1)
cout<<"de la "<<i+1<<" la "<<j+1<<endl;
}
Problema 3
Sa se determine drumul minim intr-un graf.
Rezolvare
#include<stdio.h>
#include <iostream.h>
void main()
{
int c[10][10],a[10][10],n,i,j,k;
cout<<"Introduceti numarul de virfuri ale grafului : "<<endl;
cin>>n;
cout<<"Introduceti matricea costurilor : "<<endl;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
cout <<"c["<<i+1<<","<<j+1<<"]=";
cin>>c[i][j];
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=c[i][j];
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if (a[i][j]>a[i][k]+a[k][j])
a[i][j]=a[i][k]+a[k][j];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cout<<"Drumul minim de la "<<i+1<<" la "<<j+1<<" este "<<a[i][j]<<endl;
}
Preview document
Conținut arhivă zip
- Arbori si Grafuri.doc