Structura de date graf. Implementarea grafurilor prin matrici de adiacenta. Traversarea grafurilor

1. Scopul lucrarii este prezentarea implementarii grafurilor prin matrici de adiacenta si a operatiilor de baza cu grafuri in aceasta implementare.

2. Aspecte teoretice. Grafuri si implementarea lor cu matrici de adiacenta

Un graf este o colectie de noduri si arce. Un nod este un obiect care poate avea un nume si eventual alte proprietati; un arc este o conexiune intre doua noduri (nodurile mai sunt numite si varfuri, iar arcele mai sunt numite si muchii). Notand cu N multimea nodurilor si cu A multimea arcelor, un graf G poate fi definit prin multimea nodurilor si a arcelor sale G = (N, A).

Se numeste drum intr-un graf de la nodul x la nodul y, o secventa de noduri n₁, n₂, .., n_j in care nodurile succesive sunt conectate prin arce apartinand grafului. Lungimea unui drum este egala cu numarul de arce ale drumului. Daca exista un drum de la nodul x la nodul y se spune ca acel drum conecteaza cele doua noduri, respectiv nodurile x si y sunt conectate.

Un graf se numeste conex daca de la fiecare nod al sau exista un drum spre oricare nod al grafului, respectiv daca oricare pereche de noduri apartinand nodului este conectata. Un graf care nu este conex este format din componente conexe. De exemplu, graful din figura 7.1 este format din doua componente conexe: 1, 2, 3, 4, 5, 6, 7 si respectiv 8, 9.

Grafurile prezentate sunt grafuri neorientate. Prin asocierea de informatii suplimentare nodurilor si arcelor, se pot obtine alte tipuri de grafuri, si anume:

- grafuri ponderate - fiecarui arc i se asociaza o valoare (de obicei intreaga), de exemplu distanta sau cost.

- grafuri orientate - in acest caz arcele sunt orientate, avand un sens precizat de la x la y, spre exemplu, si nu de la y la x. in acest caz, x se numeste coada sau sursa arcului, iar y varful sau destinatia sa. Pentru reprezentarea acestor arce se utilizeaza sageti sau segmente directionate.

2.1. Implementarea grafurilor cu matrici de adiacenta

Pentru graful G = (N, A) cu multimea nodurilor sale N = , matricea de adiacente este o matrice A[n, n] de elemente booleene, unde A[x, y] este adevarat daca si numai daca exista un arc de la nodul x la nodul y.

In ceea ce priveste reprezentarea in tablou a indicilor, trebuie stabilita o corespondenta intre numele nodurilor si multimea indicilor. Corespondenta poate fi realizata prin precizarea unei asocieri definite pe multimea nodurilor cu valori in multimea indicilor intregi (de exemplu, se identifica nodurile prin numere intregi care coincid cu indicii de acces in matricea de adiacente - asa se considera in exemplele din aceasta lucrare).

La grafurile neorientate reprezentarea are un caracter simetric, astfel incat arcul care conecteaza nodul x cu nodul y este reprezentat prin doua valori in matrice: A[x, y] respectiv A[y, x]. Astfel, in acest caz, matricea poate fi memorata pe jumatate (economie de spatiu de memorie), lucru care are insa si dezavantaje: o prelucrare ulterioara mai complicata.

Structurile de date necesare pentru reprezentarea grafurilor prin matrici de adiacenta sunt urmatoarele:

typedef struct _nodGnodG;

nodG nod[nrN];//tabloul de noduri

int arc[nrN][nrN];

//matricea de adiacenta, nrN este numarul maxim de noduri

Reprezentarea corespunzatoare pentru graful din figura 7.1 este (nrN este numarul de noduri ale grafului):

2.2. Crearea grafurilor. Insertia unui arc si insertia unui nod

Inserarea unui arc intre doua noduri x si y ale unui graf presupune ca elementelor A[x][y] si A[y][x] sa li se atribuie valoarea 1 (adevarat).

Pentru inserarea unui nou nod in graf, acesta trebuie inserat in tabloul de noduri. Totodata trebuie sa creasca si matricea de adiacenta cu o linie si o coloana corespunzatoare noului nod. Elementele acestora se initializeaza cu 0, apoi pot fi setate la 1 daca nodul se conecteaza cu altele.

Ca exemplu consideram inserarea in graful din figura 7.1 a unui nod cu cheia 10, care va fi conectat cu nodul cu cheia 8. Dupa adaugarea nodului si a arcului corespunzator avem:

Mai jos este secventa de adaugare a unui nod cu cheia x:

int i;

nod[nrN].cheie = x;

// + initializarea celorlalte informatii ale nodului

// initializarea cu 0 a conexiunilor cu celelalte noduri:

for(i=0;i<=nrN;i++

arc[i][nrN] = arc[nrN][i] = 0;

nrN++;//incrementarea numarului de noduri

Daca pozitia noului nod in tablou si matrice este importanta, atunci nu vom face insertiile pe ultima pozitie, ci in pozitia corespunzatoare, p, mutand intai fiecare element de pe pozitiile mai mari sau egale ca p pe pozitia urmatoare pozitiei lui (pentru a-i face loc noului nod). Functia de mai jos realizeaza insertia nodului cu cheia x in pozitia poz (numerotata de la 0).

void InsNodOrd(int poz, int x)

}

nod[poz].cheie = x;//setarea cheii nodului

// + initializarea celorlalte informatii ale nodului

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

// initializarea cu 0 a conex. cu celelalte noduri

arc[i][poz] = arc[poz][i] = 0;

Dupa inserarea unui nod cu cheia 0 in pozitia 2 in graful initial, cu aceasta functie, obtinem:

2.3. Cautarea unui nod intr-un graf

In cazul acestei implementari, cautarea unui nod se reduce la cautarea intr-un tablou. Functia urmatoare este un exemplu de cautare (cauta un nod cu cheia k).

Referat: Contabilitatea tertilor Referat: Structurarea elementelor de activ si pasiv dupa criterii financiare

//da pozitia la care se afla sau -1 daca nu se afla

int CautaNod(int k)

2.4. Suprimarea unui arc si suprimarea unui nod

Suprimarea unui arc dintre doua noduri x si y ale unui graf presupune ca elementelor A[x][y] si A[y][x] sa li se atribuie valoarea 0 (fals).

Pentru suprimarea unui nod din graf, acesta trebuie suprimat din tabloul de noduri. Totodata trebuie suprimate din matricea de adiacenta si linia si coloana corespunzatoare nodului.

Ca exemplu consideram suprimarea nodului cu cheia 3 din graful din figura 7.1. Pentru a nu muta toate elementele de pe liniile si coloanele urmatoare pozitiei nodului de sters, efectuam stergerea copiind linia si coloana corespunzatoare ultimului nod memorat peste linia, respectiv coloana din pozitia nodului de sters, apoi renuntam la ultima linie ti coloana din matrice. La fel, in tabloul de noduri copiem ultimul nod in locul celui de sters, apoi renuntam la ultima pozitie.

Dupa suprimare avem:

Mai jos este prezentata o functie care sterge un nod in maniera prezentata. Primeste ca argument pozitia nodului de sters.

void StergNod(int poz)

In aceasta implementare a stergerii, ordinea initiala a nodurilor nu se pastreaza. Daca este important sa se pastreze, atunci nu vom sterge prin copierea ultimei pozitii, ci mutand fiecare element de pe pozitiile mai mari decat pozitia de unde se sterge pe pozitia anterioara pozitiei lui. O astfel de stergere este implementata in functia de mai jos.

void StergNodOrd(int poz)

nrN--;//decrementarea numarului de noduri

Stergand nodul cu cheia 3 din graful reprezentat in figura 7.1 folosind aceasta functie, obtinem:

2.5. Traversarea grafurilor

Traversarea unui graf presupune parcurgerea tuturor nodurilor sale o singura data.

Un subgraf al unui graf G contine doar anumite noduri din G si toate arcele din G care le conecteaza pe acestea.

Un arbore de acoperire al unui graf este un subgraf care contine toate nodurile grafului initial, dar dintre arce doar atatea cate sunt necesare formarii unui arbore.

2.5.1. Traversarea in adancime

Traversarea grafurilor in adancime reprezinta o generalizare a traversarii in preordine a arborilor.

Principiul traversarii (cautarii) in adancime a unui graf G este urmatorul: se marcheaza initial toate nodurile ca fiind nevizitate. Traversarea debuteaza cu selectia unui nod n al lui G pe post de nod de pornire si cu marcarea acestuia ca vizitat. In continuare, fiecare nod adiacent lui n este traversat la randul sau si marcat cu vizitat in cazul in care acesta nu a mai fost vizitat anterior, apeland recursiv aceeasi cautare in adancime. In momentul in care toate nodurile la care se poate ajunge pornind de la un nod initial n au fost vizitate, cercetarea lui n se termina.

Daca in graf au ramas noduri nevizitate, se selecteaza unul dintre acestea pe post de nod de pornire, si procesul anterior se repeta, pana cand toate nodurile grafului au fost vizitate.

In procesul de traversare, arcele care au fost traversate in decursul trecerii de la un nod la altul formeaza asa numitul arbore de acoperire prin traversare in adancime al grafului respectiv (daca graful nu este conex, se obtin mai multi arbori, cate unul pentru fiecare componenta conexa). Pentru un graf dat arborele de acoperire obtinut prin cautare in adancime nu este unic, acesta depinzand de modul de reprezentare al grafului precum si de punctul de pornire, care impune ordinea in care arcele conectate la anumit nod sunt vizitate. Din acest motiv, arborii de acoperire difera ca forma.

Pentru graful din figura 7.1 (considerand reprezentarea data la paragraful 2.1 si nodurile de pornire pentru componentele conexe in ordinea in care apar in tabloul de noduri) traversarea in adancime poate fi reprezentata grafic ca in figura 7.4. In figura 7.5 sunt reprezentati arborii de acoperire rezultati.

Pasii urmati pentru traversare sunt:

- vizitam nodul 1; noduri adiacente nevizitate: 2, 3, 4

- vizitam nodul 2 => arc (1, 2); noduri adiacente nevizitate: 3, 5

- vizitam nodul 3 => arc (2, 3); noduri adiacente nevizitate:

- vizitam nodul 5 => arc (2, 5); noduri adiacente nevizitate: 6

- vizitam nodul 6 => arc (5, 6);

noduri adiacente nevizitate: 4, 7

- vizitam nodul 4 => arc (6, 4);

noduri adiacente nevizitate: 7

- vizitam nodul 7 => arc (4, 7);

noduri adiacente nevizitate:

- nodul 7 a fost deja vizitat

- nodul 3 a fost deja vizitat

- nodul 4 a fost deja vizitat

- vizitam nodul 8; noduri adiacente nevizitate: 9

- vizitam nodul 9 => arc (8, 9); noduri adiacente nevizitate:

Algoritmul de traversare in adancime poate fi utilizat nu numai pentru determinarea arborelui de acoperire pentru un graf, ci si pentru rezolvarea altor probleme fundamentale ale prelucrarii grafurilor. Una dintre acestea o constituie determinarea numarului si a componentelor conexe ale unui graf. Acest lucru se poate face foarte simplu, deoarece strategia algoritmului presupune vizitarea tuturor nodurilor dintr-o componenta conexa inainte de a trece la urmatoarea componenta conexa. Posibilitatea impartirii grafurilor in componente conexe este deosebit de avantajoasa in cazul prelucrarii ulterioare a acestora utilizand algoritmi complecsi (acestia sunt eliberati de detaliile prelucrarii unor componente care nu sunt conexe si astfel devin mai simpli).

Pentru graful din figura 7.1, in urma traversarii in adancime rezulta ca acesta este format din 2 componente conexe:

Componenta conexa 1: arborele de acoperire prin cautare in adancime este format din arcele: (1, 2), (2, 3), (2, 5), (5, 6), (6, 4), (4, 7).

Componenta conexa 2: arborele de acoperire prin cautare in adancime este format din arcul: (8, 9).

O alta aplicatie a cautarii in adancime o constituie verificarea simpla a existentei ciclurilor intr-un graf: astfel, un graf contine un ciclu daca si numai daca se incearca traversarea unui nod deja vizitat.

Ca si implementare pentru reprezentarea grafurilor prin matrici de adiacenta, fata de structurile de date prezentate la 2.1, se mai introduce pentru fiecare nod cate un camp, marc, utilizat pentru a marca faptul ca nodul a fost deja vizitat (traversat) sau nu in procesul de cautare. Functia marcheaza nodurile parcurse; arcele parcurse sunt doar afisate.

typedef struct _nodGnodG;

void CautAdanc(int p)

void CautAdancGraf()

2.5.2. Traversarea prin cuprindere

Principiul traversarii (cautarii) prin cuprindere este urmatorul: pentru fiecare nod vizitat x, se cauta in imediata sa apropiere cuprinzand, in vederea vizitarii, toate nodurile adiacente lui. Se foloseste o structura de coada pentru a retine nodurile care au fost vizitate, initial aceasta fiind vida.

In mod analog cu traversarea prin cautare in adancime, se poate construi si in acest caz arborele de acoperire pentru un graf dat, numit arborele de acoperire prin traversare prin cuprindere. De asemenea, pot fi evidentiate in aceeasi maniera componentele conexe ale grafului, traversarea facandu-se prin epuizarea nodurilor unei componente conexe si apoi trecerea la urmatoarea componenta.

Pentru graful din figura 7.1 (considerand reprezentarea data la paragraful 2.1 si nodurile de pornire pentru componentele conexe in ordinea in care apar in tabloul de noduri) traversarea prin cuprindere poate fi reprezentata grafic ca in figura 7.6. In figura 7.7 sunt reprezentati arborii de acoperire rezultati.

Pasii urmati pentru traversare sunt:

initializarea cozii cu nodul 1 si marcarea lui ca vizitat;

coada: 1

prelucrarea cozii (pentru nodul x: adaugarea in coada a nodurilor adiacente cu x si nevizitate si marcarea lor ca vizitate; marcarea arcului corespunzator pentru arborele de acoperire; scoaterea lui x din coada) => prima componenta conexa:

- nodul 1: coada = 2, 3, 4; arce: (1, 2), (1, 3), (1, 4)

- nodul 2: coada 3, 4, 5; arce: (2, 5)

- nodul 3: coada = 4, 5; arce:

- nodul 4: coada = 5, 6, 7; arce: (4, 6), (4, 7)

- nodul 5: coada = 6, 7; arce:

- nodul 6: coada = 7; arce:

- nodul 7: coada = ; arce:

initializarea cozii cu nodul 8 si marcarea lui ca vizitat;

coada = 8

prelucrarea cozii => a doua componenta conexa:

- nodul 8: coada = 9; arce: (8, 9)

- nodul 9: coada ; arce:

Componenta conexa 1: arborele de acoperire prin cautare prin cuprindere este format din arcele: (1, 2), (1, 3), (1, 4), (2, 5), (4, 6), (4, 7).

Componenta conexa 2: arborele de acoperire prin cautare prin cuprindere este format din arcul: (8, 9).

Se observa ca pentru acelasi graf, in aceeasi reprezentare, arborele obtinut prin cautare in adancime este diferit de cel obtinut prin cautare prin cuprindere.

Ca si implementare pentru reprezentarea grafurilor prin matrici de adiacenta, fata de structurile de date prezentate la 2.1, se mai introduce pentru fiecare nod cate un camp, marc, utilizat pentru a marca faptul ca nodul a fost deja vizitat (traversat) sau nu in procesul de cautare. urmC este campul de legatura in coada folosita - indica pozitia nodului urmator. Functia marcheaza nodurile parcurse; arcele parcurse sunt doar afisate.

typedef struct _nodGnodG;

void CautCuprGraf()

while(incC!=-1)

incC = nod[incC].urmC;

//scoaterea din coada a nodului parcurs

}//sfarsitul prelucrarii cozii => gata componenta conexa

}//gata parcurg. nodurilor grafului => gata toate comp.-le conexe

3. Problema rezolvata

Se considera mai multe grupuri distincte de cunostinte.

a) Toate aceste persoane trebuie sa semneze un document. Pentru aceasta, fiecare grup primeste pe rand documentul. In interiorul unui grup, dupa ce o persoana primeste documentul, il semneaza, il da pe rand cunostintelor sale care nu l-au semnat inca, apoi il inapoiaza celui de la care l-a primit. Sa se afiseze drumul urmat de document.

b) Pentru fiecare grup sa se afiseze perechile de cunostinte necesare si suficiente pentru ca o persoana sa poata ajunge prin cat mai putine cunostinte la fiecare dintre persoanele din grupul sau.

Rezolvare

Grupurile de cunostinte se pot reprezenta sub forma unui graf. Punctul a) presupune traversarea grafului in adancime, iar punctul b) - traversarea prin cuprindere. La traversarea in adancime nu vom afisa muchiile arborelui de acoperire, ci nodurile prin care se trece. In final, in cadrul unui grup, trebuie sa ajungem la nodul de unde am pornit.

Cunostintele sunt date intr-un fisier sub forma de perechi. Pentru simplitate, fiecare persoana e identificata printr-un intreg. Exemplu de fisier (consideram graful din figura 7.1; programul obtine reprezentarea data la paragraful 2.1):

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

Primul numar este numarul de perechi de cunostinte (numarul de arce din graf), apoi urmeaza perechile de cunostinte (arcele). Pentru fiecare nod izolat, in fisier va aparea o legatura de la el la el insusi.

Pentru acest graf (din figura 7.1), rezultatul va fi:

Drumul documentului:

Grupul 1:

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

Grupul 2:

8 9 8

Perechile de cunostinte pentru legaturile minime la fiecare persoana:

Grupul 1, pentru persoana 1:

(1, 2) (1, 3) (1, 4) (2, 5) (4, 6) (4, 7)

Grupul 2, pentru persoana 8:

(8, 9)

Programul este:

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#define nrMaxN 20

typedef struct _nodGnodG;

enum ;

nodG nod[nrMaxN];

int arc[nrMaxN][nrMaxN], nrN, nrA, incC, sfC;

int m[2], i, j;

FILE *f;

int CautaNod(int k)

void AfisImplGraf(void)

void CautAdanc(int p)

//functia de traversare in adancime pentru tot graful

void CautAdancGraf()

void CautCuprGraf()

while(incC!=-1)

incC = nod[incC].urmC;

//scoaterea din coada a nodului parcurs

}//sfarsitul prelucrarii cozii => gata componenta conexa

}//gata parcurg. nodurilor grafului => gata toate comp. conexe

//adaugarea unui nod la sfarsitul tabloului de noduri

void AdaugaNod(int cheie)

int main(void)

//crearea grafului din fisier

fscanf(f, '%d', &nrA);

nrN = 0;//nr. de noduri

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

}

if(p[0]!=p[1])//daca nu este un nod izolat

arc[p[0]][p[1]]=arc[p[1]][p[0]]= 1;

//adaug arcul

}

fclose(f);

AfisImplGraf();

printf('nDrumul documentului: ');

CautAdancGraf();

printf('nnPerechile de cunostinte pentru

legaturile minime la fiecare persoana:');

CautCuprGraf();

getch();

return 0;

4. Probleme propuse

4.1. Sa se modifice problema rezolvata, astfel incat traversarile sa inceapa cu un anumit nod specificat.           Enumerati factorii de care depinde ordinea in care apar nodurile in procesul de traversare.

4.2. Sa se determine pentru un graf dat, daca exista drum intre doua noduri specificate.

4.3. Sa se determine pentru un graf dat, daca acesta contine bucle.

4.4. Pentru doua grafuri date, sa se verifice daca unul este subgraf al celuilalt.

4.5. Sa se scrie un program care verifica daca un graf este bipartit, adica daca nodurile sale pot fi partitionate in doua clase, astfel incat oricare doua noduri din aceeasi clasa sa nu fie adiacente.

4.6. Se da un graf neorientat care se citeste dintr-un fisier. Sa se afiseze pentru fiecare nod gradul sau. Sa se verifice daca graful este un graf regulat: un graf regulat este un graf pentru care toate nodurile au acelasi grad. In cazul unui raspuns afirmativ, sa se afiseze gradul acestui graf. In cazul unui raspuns negativ, sa se determine care este numarul minim de muchii care ar trebui adaugate pentru ca acesta sa devina un graf regulat.