Ingineria programării - arbori și grafuri

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;

}