Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE




loading...



AccessAdobe photoshopAlgoritmiAutocadBaze de dateC
C sharpCalculatoareCorel drawDot netExcelFox pro
FrontpageHardwareHtmlInternetJavaLinux
MatlabMs dosPascalPhpPower pointRetele calculatoare
SqlTutorialsWebdesignWindowsWordXml

Grafuri

calculatoare

+ Font mai mare | - Font mai mic








DOCUMENTE SIMILARE

Trimite pe Messenger
Limbajul algoritmic (pseudocodul)
Personal Address Book - Lotus Notes
Modelarea conceptuala a prelucrarilor (MCP)
MANUAL DELFIN
Crearea unei baze da date Oracle9I
Frecvente cumulate - Biostatistica
MICROSOFT OFFICE XP PRO
COPROCESORUL ARITMETIC 8087 SI APLICATII
Sisteme de operare
Unelte de administrare a bazei de date Oracle9I

Grafuri

Parcurgerea DF a grafurilor neorientate




Fie G=(V,M) un graf neorientat. Ca de obicei, notam n=|V| si m=|M|

Parcurgere in adancime a grafurilor (DF = Depth First) generalizeaza parcurgerea in preordine a arborilor oarecare. Eventuala existenta a ciclurilor conduce la necesitatea de a marca varfurile vizitate. Ideea de bazǎ a algoritmului este urmǎtoarea: se pleacǎ dinr-un varf i0 oarecare, apeland procedura DF pentru acel varf. Orice apel de tipul DF(i) prevede urmǎtoarele operatii:

marcarea varfului i ca fiind vizitat;

pentru toate varfurile j din lista Li a vecinilor lui i se executǎ apelul DF(j) daca si numai dacǎ varful j nu a fost vizitat.

Simpla marcare a unui varf ca fiind sau nu vizitat poate fi inlocuitǎ cu atribuirea unui numǎr de ordine fiecǎrui varf; mai precis, in nrdf(i), initial egal cu 0, va fi memorat al catelea este vizitat varful i nrdf(i) poartǎ numele de numǎrul (de ordine) DF al lui i

Este evident cǎ plecand din varful i0 se pot vizita numai varfurile din componenta conexǎ a lui i0. De aceea, in cazul in care graful nu este conex, dupǎ parcurgerea componentei conexe a lui i0 vom repeta apelul DF pentru unul dintre eventualele varfuri incǎ neatinse.

procedure DF(i)

ndf ndf+1; nrdf(i) ndf; vizit(i);

for toti jILi

if nrdf(j)=0 then DF(j)

Programul principal este:

citeste graful;

ndf

for i=1,n

nrdf(i)

for i=1,n

if nrdf(i)=0 then DF(i)

scrie nrdf;

Lucrul cu tablouri in Java

Un tablou este o secventa de componente de acelasi tip. Acest tip poate fi un tip primitiv sau un tip referinta (deci putem lucra cu tablouri de obiecte).

Un tablou a poate fi declarat folosind una dintre urmatoarele modalitati:

tip[] a;

tip a[];

unde tip este tipul componentelor tabloului. In continuare vom folosi numai prima forma.

Declararea unui tablou nu are drept consecinta crearea sa. Crearea tabloului a declarat mai sus trebuie facuta explicit, prin:

a = new tip[n];

unde n este o constanta sau o variabila intreaga ce a primit o valoare strict pozitiva.

Cele de mai sus devin clare daca specificam faptul ca un tablou este un tip referinta. Prin creare se obtine un obiect de tip tablou (obiect numit prin abuz de limbaj tot tablou).

Componentele tabloului pot fi referite prin a[i], cu i luand valori in intervalul 0..n-1; daca i nu este in acest interval, va fi semnalata o eroare la executare. Lungimea tabloului poate fi referita prin a.length

Declararea si crearea pot fi facute si simultan prin:

tip[] a = new tip[n];

sau printr-o initializare efectiva, ca de exemplu:

int[] a =

prin care, evident, a.length devine 5.

Variabilei referinta la tablou i se poate asocia o referinta la un tablou de acelasi tip.

Exemplul 1. Urmatoarea secventa de program:

tip[] a ;

a = new tip[10];

a = new tip[20];

este corecta. Evident, noul tablou nu are nici o legatura cu cel vechi (in particular nu se pastreaza valoarea nici unei componente a tabloului vechi).

Exemplul 2. Pentru interschimbarea continutului a doua tablouri se poate proceda la fel ca pentru interschimbarea valorilor a doua variabile primitive:

int[] a = , b = , c;

c=a; a=b; b=c;

deci practic se interschimba referintele la cele doua tablouri.

Exemplul 3. Deoarece un tablou este un tip referinta, transmiterea sa ca argument la invocarea unei metode se supune regulilor referitoare la apelul prin valoare. Astfel, executarea urmatorului program:

class C

class Tablou2 {

public static void main(String[] s) {

int[] a = ;

C Ob = new C(); Ob.met(a);

for (int i=0 ; i<a.length; i++) IO.write(a[i]+' ');

}

va produce la iesire:

Mai precizam ca un tablou de caractere nu este un sir de caractere.

Limbajul Java permite lucrul cu tablouri multidimensionale. De exemplu expresia C[][] este un tip ce reprezinta tablouri bidimensionale ale caror componente au tipul C

Tablourile multidimensionale trebuie gandite ca tablouri unidimensionale ale caror elemente sunt tablouri unidimensionale etc. De aceea referirea la un element al unui tablou multidimensional a se face prin: a[indice1][indicen]

Este suficient sa reducem discutia la tablouri bidimensionale, generalizarea fiind imediata. Sa consideram urmatorul exemplu:

int[][] a = new int[3][];

a[0] = new int[3];

a[1] = new int[4];



a[2] = new int[2];

Ia nastere astfel un tablou de forma:

 

 

ceea ce arata ca in Java tablourile nu sunt neaparat dreptunghiulare; aceasta conduce desigur la economie de spatiu.

Evident, a[1].length=4

La aceeasi structura se poate ajunge si printr-o initializare efectiva:

int[][] a = , , };

care in plus atribuie valori elementelor tabloului.

Daca in referirea la un element al unui tablou unul dintre indici nu este in intervalul corespunzator, va aparea eroarea (numita in Java exceptie) cu numele:

IndexOutOfBoundsException

Parcurgerea in adancime a unui graf neorientat (program Java)

Vom folosi pentru exemplificare urmatorul graf:


pentru care listele vecinilor varfurilor sunt:

L L1=; L2=; L3=;

L L5=; L6=Æ L7=.

class df

mat[i] = new int[ntemp];

for (int j=0; j<ntemp; j++) mat[i][j] = temp[j];

}

IO.writeln(' ** ** ');

}

void parcurg()

}

private void DF(int i)

}

class ParcDF

Parcurgerea DF a grafurilor neorientate (continuare)

Observatie. Dacǎ dorim doar sǎ determinǎm dacǎ un graf este conex, vom inlocui al doilea ciclu for din programul principal prin:

DF(1)

if ndf=n then write(’CONEX’)

else write(’NECONEX’);

Observatie. Parcurgerea DF imparte muchiile grafului in:

muchii de avansare: sunt acele muchii (i,j) pentru care in cadrul apelului DF(i) are loc apelul DF(j). Aceste muchii formeazǎ un graf partial care este o pǎdure: fiecare varf este vizitat exact o datǎ, deci nu existǎ un ciclu format din muchii de avansare.

muchii de intoarcere: sunt acele muchii ale grafului care nu sunt muchii de avansare.

Determinarea multimilor A si I a muchiilor de avansare si intoarcere, precum si memorarea arborilor partiali din padurea DF se poate face astfel:

in programul principal se fac initializarile:

A Æ; I Æ

for i=1,n

tata(i)

instructiunea if din procedura DF devine:

if nrdf(j)=0

then A AÈ; tata(j) i; DF(j);

else if tata(j)¹ i

then I IÈ

Exemplu. Pentru graful urmator:




cu urmatoarele liste ale vecinilor varfurilor:

L1 L2=; L3=;

L4 L5=; L6=;

L7 L8= L9=

padurea DF este formata din urmatorii arbori partiali corespunzatori componentelor conexe:


Timpul cerut de algoritmul de mai sus este O(max)=O(n+m), adica liniar, deoarece:

pentru fiecare varf i, apelul DF(i) are loc exact o datǎ;

executarea unui apel DF(i) necesitǎ un timp proportional cu grad(i)=|Li|; in consecintǎ timpul total va fi proportional cu m=|M|

Propozitie. Dacǎ (i,j) este muchie de intoarcere, atunci i este descendent al lui j

Muchia (i,j) este detectatǎ ca fiind muchie de intoarcere in cadrul executǎrii apelului DF(i), deci nrdf(j)<nrdf(i). Deoarece existǎ muchie intre varfurile i si j, rezultǎ cǎ in timpul executǎrii lui DF(j) va fi vizitat si varful i, deci i este descendent al lui j

Propozitia de mai sus spune cǎ muchiile de intoarcere leagǎ totdeauna douǎ varfuri situate pe aceeasi ramurǎ a pǎdurii partiale DF. In particular, nu exista muchii de traversare (care sa lege doi descendenti ai aceluiasi varf dintr-un arbore DF).

Observatie. Un graf este ciclic (contine cel putin un ciclu) dacǎ si numai dacǎ in timpul parcurgerii sale in adancime este detectatǎ o muchie de intoarcere.

Aplicatie. Sǎ se determine dacǎ un graf este ciclic si in caz afirmativ sǎ se identifice un ciclu.

Vom memora pǎdurea formatǎ din muchiile de avansare cu ajutorul vectorului tata si in momentul in care este detectatǎ o muchie de intoarcere (i,j) vom lista drumul de la i la j format din muchii de avansare si apoi muchia (j,i)

Procedura DF va fi modificata astfel:

procedure DF(i)

ndf ndf+1; nrdf(i) ndf; vizit(i);

for toti jILi

if nrdf(j)=0

then tata(j) i; DF(j)

else if tata(j)¹i

then k i;

while k¹j

write(k,tata(k)); k tata(k);

write(j,i); stop

end.

Observatii:

daca notam prin nrdesc(i) numarul descendentilor lui i in subarborele de radacina i, aceasta valoare poate fi calculata plasand dupa ciclul for din procedura DF instructiunea nrdesc(i) ndf-nrdf(i)+1

un varf j este descendent al varfului i in subarborele DF de radacina i Û nrdf(i)£nrdf(j)<nrdf(i)+nrdesc(i)

O aplicatie: Problema barfei

Se considera n persoane. Fiecare dintre ele emite o barfa care trebuie cunoscuta de toate celelalte persoane.

Prin mesaj intelegem o pereche de numere (i,j) cu i,jI si cu semnificatia ca persoana i transmite persoanei j barfa sa, dar si toate barfele care i-au parvenit pana la momentul acestui mesaj.

Se cere una dintre cele mai scurte succesiuni de mesaje prin care toate persoanele afla toate barfele.

Cu enuntul de mai sus, o solutie este imediata si consta in succesiunea de mesaje: (1,2),(2,3),,(n-1,n),(n,n-1),(n-1,n-2),,(2,1)

Sunt transmit deci n-2 mesaje. Dupa cum vom vedea mai jos, acesta este numarul minim de mesaje prin care toate persoanele afla toate barfele.

Problema se complica daca exista persoane care nu comunica intre ele (sunt certate) si deci nu-si vor putea transmite una alteia mesaje.

Aceasta situatie poate fi modelata printr-un graf in care varfurile corespund persoanelor, iar muchiile leaga persoane care nu sunt certate intre ele. Vom folosi matricea de adiacenta a de ordin n in care aij este daca persoanele i si j sunt certate intre ele (nu exista muchie intre i si j) si in caz contrar.

Primul pas va consta in detectarea unui arbore partial; pentru aceasta vom folosi parcurgerea DF. Fiecarei persoane i ii vom atasa variabila booleana vi, care este true daca si numai daca varful corespunzator a fost atins in timpul parcurgerii; initial toate aceste valori sunt false. Vom pune aij=2 pentru toate muchiile de inaintare.

vi false, i=1,n



nr

DF(1)

if nr<n

then write('Problema nu are solutie (graf neconex)')

else rezolva problema pe arborele partial construit

unde procedura DF are forma cunoscuta:

procedure DF(i)

vi true

for j=1,n

if aij=1 & not vj

then aij 2; DF(j)

end

Sa observam ca in acest mod am redus problema de la un graf la un arbore! Descriem in continuare modul in care rezolvam problema pe acest arbore partial, bineinteles in ipoteza ca problema are solutie (graful este conex).

Printr-o parcurgere in postordine, in care vizitarea unui varf consta in transmiterea de mesaje de la fiii sai la el, radacina (presupusa a fi persoana 1) va ajunge sa cunoasca toate barfele. Aceasta se realizeaza prin apelul postord(1), unde procedura postord are forma:

procedure postord(i)

for j=1,n

if aij=2

then postord(j); write(j,i)

end

In continuare, printr-o parcurgere in preordine a arborelui DF, mesajele vor circula de la radacina catre frunze. Vizitarea unui varf consta in transmiterea de mesaje fiilor sai. Pentru aceasta executam apelul preord(1), unde procedura preord are forma:

procedure preord(i)

for j=1,n

if aij=2

then write(i,j); preord(j);

end

Observam ca atat la parcurgerea in postordine, cat si la cea in preordine au fost listate n-1 perechi (mesaje), deoarece un arbore cu n varfuri are n-1 muchii. Rezulta ca solutia de mai sus consta intr-o succesiune de 2n-2 mesaje. Mai ramane de demonstrat ca acesta este numarul minim posibil de mesaje care rezolva problema.

Propozitie. Orice solutie pentru problema barfei contine cel putin 2n-2 mesaje.

Sa consideram o solutie oarecare pentru problema barfei.

Punem in evidenta primul mesaj prin care o persoana a ajuns sa cunoasca toate barfele; fie k aceasta persoana. Deoarece celelate persoane trebuie sa le fi emis, inseamna ca pana acum au fost transmise cel putin n-1 mesaje. Dar k este prima persoana care a aflat toate barfele, deci celelalte trebuie sa mai afle cel putin o barfa. Rezulta ca in continuare trebuie sa apara inca cel putin n-1 mesaje. In concluzie, solutia considerata este formata din cel putin 2n-2 mesaje.

Parcurgerea BF a grafurilor neorientate

Fie un graf G=(V,M) si fie i0 un varf al sau. In unele situatii se pune probleme determinarii varfului j cel mai apropiat de i0 cu o anumita proprietate. Parcurgerea DF nu mai este adecvata.

Parcurgerea pe latime BF (Breadth First) urmareste vizitarea varfurilor in ordinea crescatoare a distantelor lor fata de i0. Este generalizata parcurgerea pe niveluri a arborilor, tinandu-se cont ca graful poate contine cicluri. Va fi deci folosita o coada C

La fel ca si la parcurgerea DF, varfurile vizitate vor fi marcate.

Pentru exemplul din primul paragraf al acestui capitol, parcurgerea BF produce varfurile in urmatoarea ordine:

Algoritmul care urmeaza parcurge pe latime componenta conexa a lui i0

for i=1,n

vizitat(i) false

C (i0}; vizitat(i0) true

while C ¹ Æ

i C; viziteaza i

for toti j vecini ai lui i

if not vizitat(j)

then vizitat(i) true; j Þ C

Programul Java corespunzator foloseste:

Clasa Vector

Un vector (obiect de tipul Vector) are lungime variabila si contine obiecte oarecare.

Vector() : constructor ce produce vectorul vid (de lungime 0);

void addElement(Object) : adauga obiectul la sfarsitul vectorului;

boolean removeElementAt(i) : elimina, cu deplasare la stanga, obiectul de pe pozitia i

boolean isEmpty() : verifica daca vectorul este vid;

Object firstElement() : intoarce primul element al vectorului. Obiectul intors trebuie convertit explicit la tipul sau real.

Clasa infasuratoare Integer permite sa asociem un obiect unui intreg si sa obtinem dintr-un astfel de obiect intregul asociat astfel:

Integer(int): constructor ce construieste obiectul asociat intregului respectiv;

int intValue(): intoarce intregul asociat obiectului.

Programul in Java este urmatorul:

import java.util.*;

class BF

class nivel

mat[i] = new int[ntemp];

for (int j=0; j<ntemp; j++) mat[i][j] = temp[j];

}

IO.writeln(' ** ** ');

}

void parc()

}

}

}

La fel ca pentru parcurgerea DF, algoritmul poate fi completat pentru parcurgerea intregului graf, pentru determinarea unei paduri in care fiecare arbore este un arbore partial al unei componente conexe etc.



loading...






Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1191
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2020 . All rights reserved

Distribuie URL

Adauga cod HTML in site