Descompunerea in componente tare conexe a unui graf orientat

Descompunerea in componente tare conexe a unui graf orientat, dat prin matricea de adiacenta

Matricea de adiacenta se citeste dintr-un fisier text

#include <fstream.h>
int s[20],p[20],a[20][20],n,nr,i,j;
void df1(int nod)
{
int k;
s[nod]=nr;
for(k=1;k<=n;k++)
if ((a[nod][k]==1) && (s[k]==0))
df1(k);
}
void df2(int nod)
{
int k;
p[nod]=nr;
for(k=1;k<=n;k++)
if((a[k][nod]==1) && (p[k]==0))
df2(k);
}
void main()
{
fstream f(“grafo.txt”,ios::in);
f>>n;
while(f>>i>>j) a[i][j]=1;
f.close();
nr=1;
for (i=1;i<=n;i++)
if (s[i]==0)
{
s[i]=nr;
df1(i);df2(i);
for(j=1;j<=n;j++)
if (s[j]!=p[j]) s[j]=p[j]=0;
nr++;
}
for(i=1;i<=n;i++)
{
cout<<“componenta “<<i<<endl;
for(j=1;j<=nr;j++)
if(s[j]==1) cout<<j<<” “;
cout<<endl;
}
}

{joscommentenable}

graf orientat tare conex

 

Graf orientat tare conex

 

#include<fstream.h>
#include<conio.h>
int s[50],a[50][50],n,suc[50],pred[50],i,j;
void citire(char fis[20],int a[50][50],int&n)
{
fstream f(fis,ios::in);
int i,j;
f>>n;
while(f>>i>>j) a[i][j]=1;
f.close();
}

void df1 (int nod)
{
int k;
suc[nod]=i;

for (k=1;k<=n;k++)
if ((a[nod][k]==1) && (suc[k]==0))
df1(k);
}
void df2(int nod)
{
int k;
pred[nod]=i;
for (k=1;k<=n;k++)
if((a[k][nod]==1)&&(pred[k]==0))
df2(k);
}
void main()
{
citire(“fis.txt”,a,n);
cout<<“nodul de pornire:”;cin>>i;
suc[i]=pred[i]=i;
df1(i);df2(i);
for(j=1;j<=n;j++)
if((suc[j]==pred[j])&&(suc[j]==i))
cout<<j<<” “;
getch();
}

{joscommentenable}

roy floyd-grafuri orientate

#include<fstream.h>
#include<conio.h>
const float pinf=1.e20;
float a[50][50];
int n;

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

void drum(int i,int j)
{
int k=1,gasit=0;
while ((k<=n) && !gasit)
{
if ((i!=k) && (j!=k) && (a[i][j]==a[i][k]+a[k][j]))
{
drum(i,k);drum(k,j);
gasit=1;
}
k++;
}
if (!gasit) cout<<j<<” “;
}

void tipar(int nodi,int nodf)
{
if (a[nodi][nodf]<pinf)
{
cout<<“drumul de la “<<nodi<<” la “<<nodf<<” are lungimea “
<<a[nodi][nodf]<<endl;
cout<<nodi<<” “;
drum(nodi,nodf);
}
else
cout<<“nu exista drum”;
}

void lungime()
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (a[i][j]>a[i][k]+a[k][j])
a[i][j]=a[i][k]+a[k][j];
}

void main()
{
citire(“ponderi.txt”,a,n);
lungime();
tipar(4,2);
getch();
}

{joscommentenable}