TDA GRAF. IMPLEMENTARE

Aplicatia 1

Sa se redacteze un program interactiv pentru prelucrarea unui graf implementat prin structuri de adiacenta:

• • o functie pentru inserarea unui nod in graf;

  • o functie pentru suprimarea unui nod din graf (se vor suprima si arcele aferente, daca exista);

  • o functie pentru inserarea unui arc intre doua noduri existente;

  • o functie pentru suprimarea unui arc intre doua noduri existente;

  • o functie care returneaza numarul de componente conexe ale grafului;

  • o functie care returneaza 1 daca nodurile grafului pot fi colorate cu 2 culori diferite astfel incat sa nu existe 2 noduri adiacente colorate cu aceeasi culoare si 0 in caz contrar;

  • o functie care apeleaza functia anterioara si daca aceasta returneaza 1, afiseaza o posibila solutie de colorare gasita.

rezolvare

Aplicatia 2

Sa se redacteze un program interactiv care prelucreaza cuvinte de aceeasi lungime L (de exemplu, L=5), implementand urmatoarele functii:

• • o functie pentru citirea unui nou cuvant (functia va verifica lungimea noului cuvant si daca este diferita de L, nu va adauga cuvantul);

  • o functie pentru suprimarea unui cuvant;

  • o functie pentru afisarea cuvintelor existente;

  • o functie care citeste doua cuvinte, verifica existenta lor in evidenta si gaseste cel mai scurt drum dintre ele (vezi mai jos).

Pentru aceasta aplicatie, consideram ca intre 2 cuvinte exista un drum de lungime 1 daca ele difera printr-o singura litera si nu exista drum daca ele difera prin mai mult de o litera. Astfel, daca cuvintele din evidenta sunt CERNE, CARNE, CARTE, CERTE, CURTE, CURBE, CURSE, BURSE atunci cel mai scurt drum intre CARTE si BURSE este: CARTE - CURTE - CURSE - BURSE.

Pentru implementare, veti folosi un graf, cuvintele fiind noduri ale grafului. Intre doua cuvinte exista arc daca ele difera printr-o singura litera si nu exista arc in caz contrar. Drumul minim intre 2 cuvinte va fi gasit printr-o cautare prin cuprindere in acest graf.

rez

#define NumarNoduri 100

typedef int TipCheie;

typedef int TipInfo;

typedef struct TipElement {

TipCheie cheie;

TipInfo info;

} TipElement;

typedef unsigned int TipContor; //[0, NumarNoduri]

typedef unsigned int TipIndex; //[1, NumarNoduri]

typedef TipElement TipTablouElem[NumarNoduri]; //

typedef int TipMatrAdj[NumarNoduri][NumarNoduri]; //doar valori boolene

typedef struct Graf {

TipContor Contor;

TipTablouElem Noduri;

TipMatrAdj Arce;

} Graf;

typedef struct TipArc {

TipIndex linie, coloana;

} TipArc;

Graf g;

void InserNod(Graf *g, TipElement e)

{

TipIndex i;

g->Contor++;

//se adauga elementul e in noul nod

g->Noduri[g->Contor] = e;

//se initializeaza matricea de adiacenta pentru noul nod

for(i = 1; i <= g->Contor; i++)

{

g->Arce[i][g->Contor] = 0;

g->Arce[g->Contor][i] = 0;

}

}

void InserArc(Graf *g, TipArc indicArc)

{

g->Arce[indicArc.linie][indicArc.coloana] = 1;

g->Arce[indicArc.coloana][indicArc.linie] = 1;

}

void SuprimNod(Graf *g, TipIndex indicNod)

{

TipIndex i;

//nodul indicat este inlocuit cu ultimul nod

g->Noduri[indicNod] = g->Noduri[g->Contor];

for(i = 1; i <= g->Contor; i++)

{

g->Arce[i][indicNod] = g->Arce[i][g->Contor];

g->Arce[indicNod][i] = g->Arce[g->Contor][i];

}

g->Contor--;

}

void SuprimArc(Graf *g, TipArc indicArc)

{

g->Arce[indicArc.linie][indicArc.coloana] = 0;

g->Arce[indicArc.coloana][indicArc.linie] = 0;

}

Alte lucruri:

define N_MAX 100

typedef struct Nod {

int nume; //index; se poate tine minte direct cheia

struct Nod *legatura;

} Nod;

Nod *StrAdj[N_MAX];

typedef int TipCheie;

typedef int TipInfo;

typedef struct TipElement {

TipCheie cheie;

TipInfo info;

} TipElement;

typedef struct Adj {

TipCheie cheieAdj;

struct Adj *urmAdj;

} Adj;

typedef struct Nod {

TipElement elem;

struct Nod *urmNod;

Adj *incepAdj;

} Nod;

typedef struct TipArc {

Nod *v1, *v2;

} TipArc;

typedef Nod* Graf;

Graf g;

typedef int ATOM;

typedef struct CelulaListNod* POZITIE;

typedef struct CelulaListArc {

int data; //informatia arcului

POZITIE nod; //destinatia arcului

struct CelulaListArc *urm; //inlantuire in liste de arce

} CelulaListArc;

typedef struct CelulaListNod {

ATOM data; //informatia apartinand nodului

POZITIE nod;

CelulaListArc *urm;

} CelulaListNod;

typedef struct ARC {

POZITIE nod1, nod2;

} ARC;

typedef POZITIE GRAF;

void CautaInAdancime(Graf *g, Nod x)

{

/*se parcurg toate nodurile din aceeasi componenta

conexa cu x prin cautare in adancime*/

Nod y;

marc[x] = vizitat; //=1

for(/* fiecare nod y din lista de adiacenta a lui x*/)

if(marc[y] == nevizitat) //==0

CautaInAdancime(g, y);

}

void TraversareInAdancime(Graf *g)

{

Nod x;

for(/*fiecare nod x din graful g*/)

marc[x] = nevizitat; //=0

for(/*fiecare nod x din graful g*/)

if(marc[x] == nevizitat) //==0

CautaInAdancime(g, x);

}

void CautaPrinCuprindere(Graf *g, Nod x)

{

/*se parcurg toate nodurile din aceeasi componenta

conexa cu x prin cautare prin cuprindere*/

CoadaNoduri Q;

Nod y;

ADAUGA(Q, x);

while(VID(Q) == 0)

{

x = SCOATE(Q);

marc[x] = vizitat; //=1

for(/* fiecare nod y din lista de adiacenta a lui x*/)

if(marc[y] == nevizitat) //==0

{

marc[y] = vizitat; //=1

ADAUGA(Q, y);

}

}

}

void TraversarePrinCuprindere(Graf *g)

{

Nod x;

for(/*fiecare nod x din graful g*/)

marc[x] = nevizitat; //=0

for(/*fiecare nod x din graful g*/)

if(marc[x] == nevizitat) //==0

CautaPrinCuprindere(g, x);

}

int Articulatie(int x)

{

Nod *t;

int m, min;

id++;

marc[x] = id;

min = id;

t = StrAdj[x];

while(t != NULL)

{

if(marc[t->nume] == nevizitat) //==0

{

m = Articulatie(t->nume);

if(m < min)

min = m;

if(m >= marc[x])

printf("%d este punct de articulatie\n", x);

}

else

//daca unul din stramosi poate deja ajunge mai sus

if(marc[t->nume] < min)

min = marc[t->nume];

t = t->urm;

}

return min;

}

Problema:

Determinati numarul componentelor conexe si faceti parcurgea in adancime:

#include <iostream>

#include <fstream>

#define MAX 100

using namespace std;

int numarNoduri;

char matriceAdiacenta[MAX][MAX];

char vector[MAX];

char vizitat[MAX];

void citire()

{

ifstream f("graf.txt");

int i,j;

f>>numarNoduri;

for(i=0;i<numarNoduri;i++)

f>>vector[i];

for(i=0;i<numarNoduri;i++)

for(j=0;j<numarNoduri;j++)

f>>matriceAdiacenta[i][j];

f.close();

}

void parcurgere(int nod)

{

vizitat[nod]=1;

int vecin;

for(vecin=0;vecin<numarNoduri;vecin++)

if(matriceAdiacenta[nod][vecin]=='1')

if(vizitat[vecin]==0)

parcurgere(vecin);

}

int nrcomponente()

{

int i,cc=0;

for(i=0;i<numarNoduri;i++)

if(vizitat[i]==0)

{

parcurgere(i);

cc++;

}

return cc;

}

void afisare()

{

for(int i=0;i<numarNoduri;i++)

{

cout<<vector[i]<<" ";

parcurgere(i);

}

}

int main()

{

cout << "Hello world!" << endl;

citire();

cout<<"Numarul componentelor conexe este: "<<nrcomponente()<<endl;

afisare();

return 0;

}