Transformarea neconex-conex

Enunt

În fişerul text graf.in este memorat un graf neorientat neconex astfel:

• pe prima linie un număr natural n, care reprezintă numărul de noduri ale unui graf neorientat.

• pe următoarele linii sunt memorate câte două numere naturale care reprezintă muchiile grafului.

Scrieţi un program care să determine numărul minim de muchii care trebuiesc adăugate la graf astfel încât graful să devină conex. Afişaţi şi o posibilă soluţie.

Exemplu:

Graful memorat în fişerul text de mai sus are următorul aspect grafic:

Rezolvare: Graful ales ca exemplu este alcătuit din trei componente conexe după cum urmează::

• Componenta conexă 1 conţine nodurile: 1 2 3 5 6

• Componenta conexă 2 conţine nodurile: 4 8

• Componenta conexă 3 conţine nodurile:7

Folosind algoritmul de parcurgere în lăţime se determină numărul de componente conexe. Numărul minim de muchii care trebuiesc adăugate pentru a transforma un graf neconex într-un graf conex este dat de următoarea relaţie:

numărul componentelor conexe-1

Muchiile care trebuiesc adăugate vor fi formate din nodul de start şi primul nod din fiecare componenta conexă iar graful conex va arata astfel:

Programul C++ este:

#include<iostream>

#include<fstream>

using namespace std;

int a[20][20],c[20],v[20],ns,n,comp;

int prim;

int ultim;

// citirea grafului din fisier text si construirea matricei de adiacenta

void citire(int a[20][20], int &n)

{ ifstream f("graf.in");

int x,y;

f>>n;

while(f>>x>>y)

a[x][y]=a[y][x]=1;

f.close();

}

// afisarea pe ecran a matricei de adiacenta

void afisare(int a[20][20],int n)

{ cout<<"Matricea de adiacenta este : "<<endl;

for( int i=1;i<=n;i++)

{ for(int j=1;j<=n;j++)

cout<<a[i][j]<<" ";

cout<<endl;

}

}

// returnează primului nod nevizitat

int exista_nod_nevizitat(int v[20], int n)

{ for(int i=1;i<=n;i++)

if(v[i]==0)

return i; // primul nod nevizitat

return 0; // nu mai exista noduri nevizitate

}

// parcurgerea în latime a unei componente conexe, plecând din nodul de start ns

void parcurgere_latime(int a[20][20], int n,int ns)

{ comp++;

v[ns]=1;

prim=ultim=1;

c[ultim]=ns;

while(prim<=ultim)

{for(int i=1;i<=n;i++)

if(a[c[prim]][i]==1)

if(v[i]==0)

{ ultim++;

c[ultim]=i;

v[i]=1;

}

prim++;

}

}

// functia principala main()

int main()

{ citire(a,n);

afisare(a,n);

ns=1;

cout<<"Muchiile adaugate sunt:";

parcurgere_latime(a,n,ns);

while(exista_nod_nevizitat(v,n)!=0)

{ns=exista_nod_nevizitat(v,n);

cout<<"(1,"<<ns<<") ";

parcurgere_latime(a,n,ns); //parcurg o alta componenta conexa

}

cout<<endl<<"Numarul minim de muchii adaugate este "<<comp-1<<".";

return 0;

}