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

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

2. Aspecte teoretice.

2.1. Structurile de date

Pentru exemplele din aceasta lucrare consideram graful din figura 8.1 (acelasi ca la lucrarea nr. 7).

In aceasta implementare nodurile grafului sunt memorate intr-o lista. Fiecare nod trebuie sa pastreze, pe langa cheie si alte informatii specifice, o lista de legaturi spre toate nodurile cu care este conectat (lista adreselor acestor noduri).

Intrucat numarul de conexiuni variaza de la nod la nod, construim pentru fiecare nod o lista inlantuita cu adresele nodurilor adiacente lui, iar in nod memoram doar adresa de inceput a acestei liste.

In aceasta implementare se folosesc urmatoarele structuri de date:

typedef struct _nodGnodG;

typedef struct _nodLnodL;

nodG *incG, *sfG;//inceputul si sfarsitul listei de noduri

Atat pentru lucrul cu lista de noduri, cat si pentru prelucrarea listelor de adiacenta, este suficient sa pastram doar inceputul acestora, dar, pentru o prelucrare mai naturala si mai rapida, putem pastra si sfarsitul, asa ca mai sus. Schematic, un graf implementat cu aceste structuri se poate reprezenta astfel (se considera ca exemplu graful din figura 8.1):

Pentru a urmari vizual mai usor conexiunile, in locul pointerilor putem reprezenta direct cheia nodul indicat:

1 - 2 3 4

2 - 1 3 5

3 - 1 2

4 - 1 6 7

5 - 2 6

6 - 4 5 7

7 - 4 6

8 - 9

9 - 8

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

Inserarea unui arc intre doua noduri x si y ale unui graf presupune crearea unui nod indicand spre y in lista de adiacenta a lui x si a unuia indicand spre x in lista de adiacenta a lui y. Daca graful este orientat, nu avem de inserat decat un nod in lista de adiacenta a sursei, care sa indice destinatia. Functia de mai jos realizeaza insertia unui arc orientat de la nodul indicat de s la nodul indicat de d. Insertia legaturii spre d in lista de adiacente a lui s se face la sfarsitul listei.

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

void AdaugMuchie(nodG *s, nodG *d)else

//lista de adiac. este vida => singurul nod va fi acesta (noul creat)

s->incL = s->sfL = l;

Daca dorim sa inseram un arc neorientat intre s si d, putem lansa aceasta functie de doua ori, astfel:

AdaugMuchie(s, d);

AdaugMuchie(d, s);

Pentru inserarea unui nou nod in graf, acesta trebuie inserat in lista de noduri. Aceasta operatie se reduce la insertia unui nod intr-o lista obisnuita si initializarea informatiilor lui. Functia de mai jos insereaza un nod cu cheia k la sfarsitul listei de noduri ale grafului si intoarce o referinta spre nodul nou creat.

nodG *AdaugNod(int k)else //acesta este primul

incG = sfG = p;

return p;

Daca pozitia noului nod in lista este importanta, atunci vom face insertia in pozitia corespunzatoare (aici nu mai este nevoie sa mutam nodurile de pe pozitiile urmatoare, ca si la implementarea cu matrici de adiacenta).

2.3. Cautarea unui nod dintr-un graf

Folosind aceasta implementare, cautarea unui nod se reduce la cautarea unui nod intr-o lista obisnuita. Un exemplu de cautare este functia de mai jos, care cauta nodul cu cheia k si intoarce referinta spre el sau NULL (daca nu se gaseste un astfel de nod).

nodG *CautaNod(int k)

2.4. Suprimarea unui arc si suprimarea unui nod

In aceasta implementare, atat suprimarea unui arc, cat si suprimarea unui nod se reduc la suprimarea unui nod dintr-o lista inlantuita.

Suprimarea unui arc dintre doua noduri x si y ale unui graf presupune stergerea din lista de adiacente a lui x a legaturii spre y si stergerea din lista de adiacente a lui y a legaturii spre x. Daca graful este orientat, suprimarea arcului de la x la y presupune doar o stergere: a legaturii spre y din lista de adiacente a lui x. Functia urmatoare suprima arcul de la nodul referit de n1 la cel referit de n2.

void StergMuchie(nodG *n1, nodG *n2)

else

else//nu am gasit-o

printf('Nu s-a gasit muchie de la

%d la %d.', n1->cheie, n2->cheie);

}

else//lista e vida <=> nu exista conexiuni dinspre n1

printf('Nu s-a gasit muchie de la %d la

%d.', n1->cheie, n2->cheie);

Daca dorim sa suprimam un arc neorientat intre s si d, putem apela aceasta functie de doua ori, astfel:

StergMuchie(s, d);

StergMuchie(d, s);

Pentru suprimarea unui nod din graf, acesta trebuie suprimat din lista de noduri. Totodata trebuie suprimate si arcele dintre nodul de suprimat si cele conectate cu el. Functia de mai jos realizeaza suprimarea nodului cu cheia k dintr-un graf neorientat, astfel: intai se parcurge lista de adiacenta a nodului si la fiecare element facem urmatoarele: din lista de adiacente a nodului indicat stergem legatura spre nodul de sters, apoi suprimam elementul respectiv; in final suprimam nodul.

void StergNod(int k)

//l-am gasit

if(k!=p->cheie) q = p->urmG;

else q = p;

//stergerea tuturor conexiunilor lui

while(q->incL)

//stergerea nodului

if(q==incG)else

La grafurile orientate nu putem ajunge la fel de simplu ca si la cele orientate la nodurile care au arce spre nodul de sters - ele trebuie cautate.

Ca exemplu consideram suprimarea nodului cu cheia 3 din graful din figura 8.1.

Lista legaturilor inainte de suprimare:        Lista legaturilor dupa suprimare:

1 - 2 3 4 1 - 2 4

2 - 1 3 5 2 - 1 5

3 - 1 2 4 - 1 6 7

4 - 1 6 7 5 - 2 6

5 - 2 6 6 - 4 5 7

6 - 4 5 7 7 - 4 6

7 - 4 6 8 - 9

8 - 9 9 - 8

9 - 8

In aceasta implementare a stergerii, ordinea initiala a nodurilor se pastreaza, intrucat ele sunt memorate intr-o lista inlantuita.

2.5. Traversari

2.5.1. Traversarea in adancime

Structurile de date utilizate sunt cele de la paragraful 2.1, in plus avand pentru noduri campul marc pentru marcarea nodurilor vizitate.

typedef struct _nodGnodG;

typedef struct _nodLnodL;

nodG *incG, *sfG;//inceputul si sfarsitul listei de noduri din graf

In continuare este prezentat codul pentru traversarea in adancime in cazul implementarii grafurilor cu liste.

void CautAdanc(nodG *p)

l = l->urmL;//trecem la urmatorul nod adiacent

}

void CautAdancGraf(nodG *p)

p = p->urmG;

}

2.5.2. Traversarea prin cuprindere

Structurile de date utilizate sunt cele prezentate la paragraful 2.1, in plus avand pentru noduri campurile marc (pentru marcarea ca vizitat) si urmC pentru inlantuirea in coada:

typedef struct _nodGnodG;

typedef struct _nodLnodL;

nodG *incG, *sfG, *incC, *sfC;

//inceputul si sfarsitul grafului, resp. inc. si sf cozii

In continuare este prezentat codul pentru traversarea prin cuprindere in cazul implementarii grafurilor cu liste.

void CautCuprGraf(nodG *p)

while(incC)

l = l->urmL;

}

incC = incC->urmC;//scoaterea din coada

}

p = p->urmG;

}

3. Problema rezolvata

In acest paragraf se prezinta varianta de implementare a problemei rezolvate de la lucrarea nr. 7, folosind insa structuri de adiacenta pentru reprezentarea grafului.

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

typedef struct _nodGnodG;

typedef struct _nodLnodL;

enum ;

nodG *incG, *sfG, *incC, *sfC;

//inc. si sf. pentru graf, resp. pentru coada

int n, m[2], i, j;

FILE *f;

nodG *AdaugNod(int k)else//nu mai sunt; acesta este primul nod

incG = sfG = p;

return p;

void AdaugMuchie(nodG *s, nodG *d)else//lista de adiacente este vida

s->incL = s->sfL = l;

nodG *CautaNod(int k)

void AfisImplGraf(void)

p = p->urmG;

}

void CautAdanc(nodG *p)

l = l->urmL;//trecem la urmatorul nod adiacent

}

void CautAdancGraf(nodG *p)

p = p->urmG;

}

void CautCuprGraf(nodG *p)

while(incC)

l = l->urmL;

}

incC = incC->urmC;//'scoaterea' din coada

}

p = p->urmG;

}

void StergGraf()

delete incG;

incG = sfG;

}

void main(void)

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

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

if(p[0]!=p[1])

}

fclose(f);

AfisImplGraf();

printf('nnDrumul documentului:');

CautAdancGraf(incG);

printf('nnPerechile de cunostinte pentru

legaturile minime la fiecare persoana:');

CautCuprGraf(incG);

StergGraf();

getch();

4. Probleme propuse

4.1. Scrieti un program care, pentru un graf neorientat dat, afiseaza nodurile cu gradul maxim respectiv minim. Sa se determine apoi care este numarul minim de muchii care ar trebui adaugat astfel incat graful sa nu contina noduri terminale.

4.2. Determinati suma gradelor tuturor varfurilor unui graf neorientat si comparati-o cu numarul de muchii a acestuia. Ce observati?

4.3. Se da un graf neorientat conex. Realizati programul care identifica care este numarul maxim de muchii care pot fi eliminate astfel incat graful sa ramana conex.

4.4. Se da o harta cu trasee turistice. Sa se realizeze, daca este posibil, un circuit care sa cuprinda toate traseele o singura data.

4.5. Intr-o retea telefonica sunt conectate mai multe centrale, unele direct, altele prin intermediul altora. Sa se scrie programul care identifica si afiseaza lista centralelor telefonice "critice", adica a caror defectare are ca si consecinte intreruperea legaturii telefonice intre alte centrale, diferite de cea defecta.