Se citeste nr de noduri, nr de muchii si muciile. Sa se verifice daca doua noduri x,y fac parte din aceeasi componenta conexa. Sa se verifice daca graful este conex. Sa se afiseze componentele conexe ale grafului. Sa se afiseze componenta conexa de lungime maxima. Afisati muchiile care trebuie adaugate pentru ca graful sa devina conex.

#include<iostream>
#include<fstream>
using namespace std;
int a[20][20],n,m,v[20],xx,yy,u[10][10];
void citire()
{ifstream f("date");
f>>n>>m;
int x,y;
for(int i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=a[y][x]=1;}
f>>xx>>yy;
}

void DF(int x)
{//cout<<x<<" ";
v[x]=1;
for(int i=1;i<=n;i++)
    if(a[x][i]==1 && v[i]==0)
        DF(i);
}

void DDF(int x)
{//cout<<x<<" ";
v[x]=1;
for(int i=1;i<=n;i++)
    if(a[x][i]==1 && v[i]==0)
        {cout<<x<<" "<<i<<endl;
                        DDF(i);
        }
}

void DFF(int x,int &j,int &k)
{cout<<x<<" ";
u[j][k]=x;
k++;
v[x]=1;
for(int i=1;i<=n;i++)
    if(a[x][i]==1 && v[i]==0)
        DFF(i,j,k);
}

int main()
{citire();
int ok=1,k=0,maxi=0,j=0,p;
DF(xx);
if(v[yy]==1)
    cout<<xx<<" si "<<yy<<" fac parte din aceeasi componenta conexa";
else cout<<xx<<" si "<<yy<<" NU! fac parte din aceeasi componenta conexa";
for(int i=1;i<=n;i++)
    v[i]=0;
DF(1);
for(int i=1;i<=n;i++)
    if(v[i]==0)
        ok=0;
if(ok)
    cout<<endl<<"Graful este conex"<<endl;
else cout<<endl<<"Graful nu este conex"<<endl;

for(int i=1;i<=n;i++)
    v[i]=0;
cout<<"Componentele conexe "<<endl;
for(int i=1;i<=n;i++)
    if(v[i]==0)
    {DFF(i,j,k);
    j++;
    if(k>maxi)
        maxi=k;
    k=0;
    cout<<endl;
    }
cout<<"Cea mai lunga componenta conexa ("<<maxi<<") "<<endl;
for(int i=0;i<j;i++)
    if(u[i][maxi-1]!=0)
        p=i;
for(int i=0;i<maxi;i++)
    cout<<u[p][i]<<" ";
cout<<endl<<"Pentru ca graful sa devina conex trebuie adaugate muchiile"<<endl;
for(int i=1;i<j;i++)
    cout<<u[0][0]<<" "<<u[i][0]<<endl;
for(int i=1;i<=n;i++)
    v[i]=0;
cout<<"Muchiile de avansare"<<endl;
for(int i=1;i<=n;i++)
    if(v[i]==0)
        DDF(i);

}

Fisier

10 7
1 2
1 3
2 3
1 10
6 8
4 5
5 7
2 8

Graf bipartit - !!UNCOMPLITID!!

#include<iostream>
#include<fstream>
using namespace std;
int u[100][100],a[10],b[10],n,m,v[10];
void citire()
{ifstream f("date");
f>>n>>m;
int x,y;
for(int i=1;i<=m;i++)
{f>>x>>y;
u[x][y]=u[y][x]=1;}

}

void DF(int x,int &i, int &j)
{
v[x]=1;
for(int ii=1;ii<=n;ii++)
    if(u[x][ii]==1 && v[ii]==0)
        {if(a[i-1]==x)
            {b[j]=ii;j++;}
        if(b[j-1]==x)
            {a[i]=ii;i++;}
            DF(ii,i,j);
        }
}

int main()
{    citire();
    a[0]=1;  
    int i=1,j=0;
    DF(1,i,j);
    for(int ii=0;ii<i;ii++)
        cout<<a[ii]<<" ";
    cout<<endl;
    for(int ii=0;ii<j;ii++)
        cout<<b[ii]<<" ";
 
}

Fisier

6 5
1 5
2 3
3 4
5 6
3 6

#include<iostream>
#include<fstream>
using namespace std;
int a[20][20],n,m,v[20];
void citire()
{ifstream f("date");
f>>n>>m;
int x,y;
for(int i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=a[y][x]=1;}
}

void DF(int x)
{cout<<x<<" ";
v[x]=1;
for(int i=1;i<=n;i++)
    if(a[x][i]==1 && v[i]==0)
        DF(i);
}

int main()
{citire();
for(int i=1;i<=n;i++)
    {DF(i);
    for(int j=1;j<=n;j++)
        v[j]=0;
    cout<<endl;}
}

Fisier

8 13
1 2
1 3
1 6
1 8
3 6
3 4
3 5
4 5
5 6
5 7
6 8
6 7
7 8

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int n,m,i,j,k,l,p,u[10][10],a,b,maxi=0,s,x,y,ii,t;
int main()
{ifstream f("graf.in");
f>>n>>m;
for(i=1;i<=m;i++)
{f>>a>>b;
u[a][b]=u[b][a]=1;}
for(i=1;i<=n;i++)
    {for(j=1;j<=n;j++)
        cout<<setw(3)<<u[i][j];
    cout<<endl;}
    f>>t;
cout<<endl<<"Noduri adiacente cu nodul "<<t<<" : ";
for(i=1;i<=n;i++)
    if(u[t][i]==1)
        cout<<i<<" ";
for(i=1;i<=n;i++)
{s=0;
    for(j=1;j<=n;j++)
        if(u[i][j]==1)
            s++;
        if(s>maxi)
            maxi=s;
}
cout<<endl<<endl<<"Nodurile de grad maxim ("<<maxi<<") : ";
for(i=1;i<=n;i++)
    {s=0;
    for(j=1;j<=n;j++)
        if(u[i][j]==1)
            s++;
        if(s==maxi)
            cout<<i<<" ";}
   
f>>x>>y;

cout<<endl<<endl<<"Lanturi elementare de L=3 care contin nodurile "<<x<<" si "<<y<<endl;
for(ii=1;ii<=n;ii++)
{
for(i=1;i<=n;i++)
    if(u[ii][i]==1)
        for(j=1;j<=n;j++)
            if(u[i][j]==1 && j!=ii)
                for(k=1;k<=n;k++)
                    if(u[j][k]==1  && k!=ii && k!=i &&
                        (k==y || i==y || j==y || ii==y) &&
                        (k==x || i==x || j==x || ii==x))
                        cout<<"("<<ii<<" "<<i<<" "<<j<<" "<<k<<")"<<endl;
}
                   
for(i=1;i<=n;i++)
    {u[5][i]=0;
    u[i][5]=0;}
    cout<<endl<<"Graful partial obtinut prin eliminarea muchiilor incidente cu nodul "<<t<<endl;
    for(i=1;i<=n;i++)
    {for(j=1;j<=n;j++)
        cout<<setw(3)<<u[i][j];
    cout<<endl;}
}

Se dă un graf. Să se scrie o funcţie care citeşte datele şi construieşte matricea, o funcţie cu parametru matrice care verifică dacă este simetrică şi are diag. principală 0 (returnează 1 sau 0), o funcţie cu parametru nr nat i care returnează gradul nodului i, o funcţie care afişează nodurile izolate, terminale, de grad n-1, o funcţie care primeşte i şi afişează nodurile adiacente lui i, o funcţie care returnează 1 dacă graful e complet şi 0 în caz contrar.

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int u[10][10],n,m,i,j,k,a,b,c;

void citire()
{ifstream f("graf");
int j;
f>>n>>m;
for(j=1;j<=m;j++)
{f>>a>>b;
u[a][b]=u[b][a]=1;}
f>>i;
}

int simetrica(int u[10][10])
{int ok=1,i,j,ko=1;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        {if(u[i][j]!=u[j][i])
            ok=0;
        if(i==j && u[i][j]==1)
            ko=0;
        }
if(ok==1 && ko==1)
    return 1;
else return 0;
}

int grad(int i)
{int j,s=0;
for(j=1;j<=n;j++)
    if(u[i][j]==1)
        s++;
return s;
}

void noduri()
{int i,j,s=0,a[10],b[10],c[10],aa=1,bb=1,cc=1;
for(i=1;i<=n;i++)
    {s=0;
        for(j=1;j<=n;j++)
            if(u[i][j]==1)
                s++;
        if(s==0)
            {a[aa]=i;aa++;}
        if(s==1)
        {b[bb]=i;bb++;}
        if(s==n-1)
        {c[cc]=i;cc++;}
    }
cout<<"Noduri izolate ";
for(i=1;i<aa;i++)
    cout<<a[i]<<" ";
if(aa==1)
    cout<<"nu sunt";
cout<<endl<<"Noduri terminale ";
for(i=1;i<bb;i++)
    cout<<b[bb]<<" ";
if(bb==1)
    cout<<"nu sunt";
cout<<endl<<"Noduri de grad "<<n-1<<" ";
for(i=1;i<cc;i++)
    cout<<c[cc]<<" ";
if(cc==1)
    cout<<"nu sunt";
}

void adiacente(int i)
{int j;
cout<<endl<<"Nodurile adiacente lui "<<i<<": ";
for(j=1;j<=n;j++)
    if(u[i][j]==1)
        cout<<j<<" ";
    cout<<endl;
}

int complet()
{
    if(m==n*(n-1)/2)
        return 1;
    else return 0;
}

int main()
{citire();
//cout<<i;
if(simetrica(u)==1)
    cout<<"Matrice simetrica"<<endl;
else cout<<"Matrice nesimetrica"<<endl;
cout<<"Gradul nodului "<<i<<" este "<<grad(i)<<endl;
noduri();
cout<<endl;
adiacente(i);
if(complet()==1)
    cout<<"Graf complet";
else cout<<"Graful nu e complet";
}

Fisier

6 5
1 5
1 4
2 4
2 3
3 5
2

1. Se dau două grafuri. Să se verifice dacă al doilea este graf parţial/subgraf al primului. Pentru subgraf se citesc, în ordine: nb, mb, vârfurile şi apoi muchiile.

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int n,m,i,ua[10][10],ub[10][10],na,nb,ma,mb,ok=1,ok1=1,v[10];
int a,b,c,j,k;
int main()
{ifstream fa("a");
ifstream fb("b");
fa>>na>>ma;
fb>>nb>>mb;
if(na!=nb)
 {cout<<"nu este graf partial"<<endl;
 ok=0;}

if(nb>=na)
 {cout<<"nu este subgraf"<<endl;}
for(i=1;i<=ma;i++)
{fa>>a>>b;
ua[a][b]=ua[b][a]=1;}
for(i=1;i<=nb;i++)
 {fb>>a;
 v[a]=1;}
for(i=1;i<=mb;i++)
{fb>>a>>b;
ub[a][b]=ub[b][a]=1;}
for(i=1;i<=na;i++)
 {for(j=1;j<=na;j++)
  cout<<setw(3)<<ua[i][j]<<ub[i][j];
 cout<<endl;}
if(ok==1)
{
for(i=1;i<=na;i++)
 for(j=1;j<=na;j++)
  if(ub[i][j]==1 && ua[i][j]==0)
  {cout<<"nu este graf partial"<<endl;
  ok=0;}
}
if(ok==1)cout<<"este graf partial";
for(i=1;i<=na;i++)
 for(j=1;j<=na;j++)
  if(v[i]==1 && v[j]==1)
  if(ub[i][j]!=ua[i][j])
  {cout<<"nu este subgraf"<<endl;
  ok1=0;
  return 0;}
if(ok1==1)cout<<"este subgraf";
}

Fişiere

7 6
1 2
1 5
1 6
2 3
2 6
6 7

7 5
1 2
1 5
2 3
2 6
6 4

2. Se citeşte dintr-un fişier numărul de noduri, muchii şi muchiile unui graf. Să se afişeze: a) nodurile de grad maxim; b) lanţurile elementare L=2 ce pornesc din k; c) lanţurile elementare L=3 ce pornesc din x şi se termină în y; d) ciclurile elementare L=3 ce conţin nodul u; e) verificaţi dacă graful e complet; f) toate lanţurile elementare care pornesc din x şi se termină în y; câte sunt si care e lungimea maximă?

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int n,m,i,u[100][100],ok=1,ok1=1,v[100],nr,xx[100],ii=2,mm[100],ms=0;
int a,b,c,j,k,maxi=0,x,y,uu;

void afisare(int i)
{int j;
nr++;
for(j=1;j<=i;j++)
    cout<<xx[j]<<" ";
cout<<endl;
}

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(xx[j]==xx[i])
        return 0;
return 1;
}

void back(int i)
{int j;
for(j=1;j<=n;j++)
{if(u[xx[i-1]][j]==1)
    {xx[i]=j;
if(verif(i))
    if(xx[i]==y)
        {afisare(i);
    if(i>ms)ms=i;
    for(int o=1;o<=i;o++)
        mm[o]=xx[o];
        }
    else back(i+1);
    }
}
}

int main()
{ifstream f("graf");
f>>n>>m;
for(i=1;i<=m;i++)
{f>>a>>b;
u[a][b]=u[b][a]=1;}
f>>k>>x>>y>>uu;
for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
  v[i]+=u[i][j];
for(i=1;i<=n;i++)
 if(v[i]>maxi)
  maxi=v[i];
cout<<"Nodurile de grad maxim"<<endl;
for(i=1;i<=n;i++)
 if(v[i]==maxi)
  cout<<i<<" ";
 cout<<endl<<endl;
cout<<"Lanturi de L=2 care pornesc din "<<k<<endl;
for(i=1;i<=n;i++)
 if(u[k][i]==1)
  for(j=1;j<=n;j++)
   if(u[i][j]==1 && j!=k)
    cout<<k<<" "<<i<<" "<<j<<endl;
   cout<<endl;
cout<<"Lanturi de L=3 care pornesc din "<<x<<" si se termina in "<<y<<endl;
for(i=1;i<=n;i++)
 if(u[x][i]==1)
  for(j=1;j<=n;j++)
   if(u[i][j]==1)
    for(int ii=1;ii<=n;ii++)
     if(u[j][ii]==1 && ii==y)
      cout<<x<<" "<<i<<" "<<j<<" "<<ii<<endl;
cout<<endl<<"Cicluri elementare de L=3 ce contin nodul "<<uu<<endl;
for(i=1;i<=n;i++)
 if(u[uu][i]==1)
  for(j=1;j<=n;j++)
   if(u[i][j]==1)
    for(int ii=1;ii<=n;ii++)
     if(u[j][ii]==1 && ii==uu)
      cout<<uu<<" "<<i<<" "<<j<<" "<<ii<<endl;
cout<<endl;
if(m==n*(n-1)/2)
    cout<<"Graful e complet"<<endl<<endl;
else cout<<"Graful nu e complet"<<endl<<endl;
cout<<"Lanturile elementare ce pornesc din "<<x<<" si se termina in "<<y<<endl;
xx[1]=x;
back(2);
cout<<nr<<" lanturi. Cel mai mare: ";
for(int o=1;o<m;o++)
    cout<<mm[o]<<" ";
cout<<" ("<<ms<<")";
}

Fişier

7 6
1 2
1 5
1 6
2 3
2 6
6 7
6
7 5
1

Se citeşte un graf şi o secvenţă de noduri. Să se verifice dacă secvenţa este lanţ/lanţ elementar/ciclu/ciclu elementar.

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int n,m,i,u[10][10],x[100],ok=0,ok1=0,ok2=0,ok3=0;
int main()
{ifstream f("graf");
//int n,m,i,u[10][10],x[100],ok=0,ok1=0,ok2=0,ok3=0;
f>>n>>m;
int a,b,c,j,k;
for(i=1;i<=m;i++)
{
f>>a>>b;
u[a][b]=1;
u[b][a]=1;
}
i=1;
while(f>>c)
    {x[i]=c;
    i++;}
 
for(int ii=1;ii<=n;ii++)
    {for(int jj=1;jj<=n;jj++)
        cout<<setw(3)<<u[ii][jj];
    cout<<endl<<endl;}
  
for(int ii=1;ii<i;ii++)
    cout<<x[ii]<<" ";
cout<<endl;
  
for(j=1;j<i-1;j++)
    if(u[x[j]][x[j+1]]==0)
        {cout<<"Nu este lant, deci nu poate fi ciclu si cu atat mai putin nu se pune problema elementaritatii.";return 0;
        ok=1;}
      
if(ok==0)
{    cout<<"Este lant ";
for(j=1;j<=i;j++)
{    for(k=j+1;k<=i;k++)
        if(x[j]==x[k])
            {cout<<"neelementar ";
            ok1=1;
            break;}
break;}
}
if(ok1!=1)
    cout<<"elementar ";

if(ok==0)
    if(x[1]==x[i-1])
        {cout<<endl<<"Este ciclu ";
        ok2=1;}
    else {cout<<endl<<"Nu este ciclu, deci nu se mai pune problema elementaritatii.";return 0;}
 
if(ok2==1)
    {for(j=2;j<=i;j++)
        for(k=j+1;k<=i;k++)
            if(x[j]==x[k])
                {cout<<"neelementar";
                ok3=1;
                return 0;
                }
    }
             
if(ok3==0)
    cout<<"elementar";
 
}

Fişier

6 5
1 5
1 4
2 4
2 3
3 5
1 5 3 2 1

1. Se citeşte un număr n şi matricea de adiacenţă a unui graf. Să se afişeze muchiile şi listele de vecini.

#include<iostream>
#include<fstream>
using namespace std;
int main()
{ifstream f("date");
int a[10][10],i,j,k=1,n,m,v[10],max=0;
f>>n;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        f>>a[i][j];

cout<<"Liste de vecini"<<endl;
for(i=1;i<=n;i++)
{
cout<<i<<":";
for(j=1;j<=n;j++)
    if(a[i][j]==1)
        cout<<j<<",";
cout<<endl;
}

cout<<"Muchii"<<endl;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
    if(i<j)
    if(a[i][j]==1)
        cout<<i<<","<<j<<endl;
}

2. Se citesc două numere n şi m. Să se afişeaze matricea de adiacenţă pentru un graf cu n noduri şi m muchii. Verificaţi dacă valoarea lui m este corectă (m<n(n-1)/2).

#include<iostream>
#include<iomanip>
#include<fstream>
using namespace std;
int a[10][10],i,j,k=0,n,m,v[10],max=0;
int main()
{ifstream f("date");
cin>>n;
m=n*(n-1)/2;

while(k<m)
{
i=rand()%n +1;
j=rand()%n +1;
if(i!=j && !a[i][j]){ a[i][j]=a[j][i]=1; k++;}
}

cout<<"Afisare matrice"<<endl;
for(i=1;i<=n;i++)
    {for(j=1;j<=n;j++)
        cout<<setw(3)<<a[i][j];
    cout<<endl;
}
}

Se citeşte dintr-un fişier text matricea de adiacenţă a unui graf neorientat. Să se afişeze gradul fiecărui nod. Să se afişeze nodurile izolate. Să se afişeze nodurile de grad maxim.

#include<iostream>
#include<fstream>
using namespace std;
int main()
{ifstream f("date");
int a[10][10],i,j,k=1,n,m,v[10],max=0;
f>>n;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        f>>a[i][j];
int s=0;

for(i=1;i<=n;i++)
{s=0;
for(j=1;j<=n;j++)
    s+=a[i][j];

cout<<"Gradul nodului "<<i<<": "<<s<<endl;
    v[k]=s;
    k++;
if(s>max)
    max=s;
}

cout<<"Noduri izolate: ";
for(i=1;i<k;i++)
    if(v[i]==0)
        cout<<i<<" ";
   
cout<<endl<<"Grad maxim: ";
for(i=1;i<k;i++)
    if(v[i]==max)
        cout<<i<<" ("<<v[i]<<")";
}

http://corina.doit.ro/graf/