Structuri de Date Dinamice In Limbajul Java
Structuri de date dinamice în limbajul java
Cuprins
MOTIVAȚIA LUCRARII
CAPITOLUL III
Concepția structurii de grafuri
Noțiuni generale
Noțiunea de graf
1.2.1 Definiția grafului neorientat și orientat
1.2.2 Moduri de reprezentare ale unui graf
1.3 Noțiuni de baza în teoria grafurilor
1.3.1 Proprietăți
1.3.2 Ordinul unui graf
1.3.3 Gradul unui nod dintr-un graf
1.3.4 Drumuri și cicluri într-un graf
1.3.5 Conexiuni într-un graf
CAPITOLUL II
Concepția structurii de arbore
2.1 Noțiuni generale
2.1.1 Noțiunea de arbore, proprietăți
2.1.2 Arbori cu rădăcină
2.2 Arbori binari
2.2.1 Definiție
2.2.2 Proprietățile unui arbore binar
CAPITOLUL IV
Algoritmul și reprezentarea unui graf în limbajul java
3.1 Probleme de drumuri minime intr-un graf
3.1.1 Întroducere
3.1.2 Algoritmul lui Dijkstra
3.2 Structuri de date utilizate în reprezentarea grafurilor
3.2.1 Matricea de adiacență
3.2.2 Liste de adiacență (vecinilor
3.3 Adăugarea vârfurilor și a muchiilor într-un graf
3.4 Reprezentarea stivelor și cozilor în limbajul java
3.4.1 Stiva
3.4.2 Coada
3.5 Algoritmul Depth-First Search (DFS) –parcurgerea în adâncime
3.6 Algoritmul Breadth-First Search (BFS) – parcurgerea în lățime
3.7 Algoritmul de căutare a unui arbore de acoperire de lungime minimă
3.7.1 Reprezentarea algoritmului
3.7.2 Întroducerea datelor de la tastatură.Importarea claselor
CAPITLUL IV
Interfețe grafice. Reprezentarea aplicației în limbajul java
4.1 Interfețe grafice
4.1.1. Componente grafice
4.1.2. Peer
4.1.3 Afișarea componentelor
4.1.4 Organizarea componentelor
4.2 Pachete AWT și SWING
4.2.1 Noțiuni generale
4.2.2 Ferestre
4.3 Elemente de control (widgets
4.3.1 Butoane
4.3.1.1 RadioButton
4.3.1.2 ListBox
4.4 REPREZENTAREA APLICAȚIEI
CONCLUZII
BIBLIOGRAFIE
Motivația lucrării
Structurile de date dinamice reprezintă modalitatea în care datele sunt dispuse în memoria calculatorului (pe discul magnetic).
Datele sunt entitati purtatoare de informatie. În informatica, o data este un model de reprezentare a informatiei. În functie de modul lor de organizare, datele pot fi elementare sau structurate.
Algoritmul reprezinta procedura pe care programele o fac pentru a manipula datele din aceste structuri de date.
Din punctul de vedere al unui programator, memoria este împărțită în octeți (succesiune de octeți), referirea la un octet realizându-se cu ajutorul unor adrese de memorie. În memorie se alocă zone pentru toate variabilele cu care lucrează un program. Această alocare se poate face: static (la declararea variabilei respective, zona fiind ocupată până la terminarea execuției programului) sau dinamic (mediul de execuție sau programatorul gestionează alocarea sau eliberarea unei zone).
Lucrarea trateaza subiectul structurilor de date dinamice și al algoritmilor utilizați în programarea orientată pe obiecte. În lucrare, se vor trece in revista principalele structuri de date cum ar fi arbori binari, liste, cozi, grafuri etc. Algoritmii implementati in aceste structuri pot manipula datele in mai multe moduri, de exemplu sortarea elementelor din structura sau cautarea unui anumit element.
Două programe care rezolva aceiasi problema pot sa arate complet diferit, unul poate fi extreme de lizibil, concis si usor de modificat pentru a se adapta la rezolvarea unor probleme asemănătoare iar celalalt poate fi obscur, impenetrabil si greu de adaptat. Cele doua programe pot sa difere ca timp de executie si ca memorie alocata incat, pentru un anumit set de intrare, unul poate furniza raspunsul dupa 2 secunde iar celalalt in 2 ore. Experienta a demonstrat ca aceste diferente sunt provocate de structura programului si structura datelor.
Rezolvarea unei probleme începe cu definirea structurilor de date, continua cu utilizarea acestora si se încheie cu stocarea rezultatelor prelucrării, tot sub forma unor structuri de date. Studierea structurilor de date revine la clasificarea datelor, a operațiilor posibile cu fiecare tip de dată, în așa fel încât realizarea si dezvoltarea programelor să devina avantajoasă pentru cat mai multi programatori.
Capitolul 1 – Principalele structuri de date
1.1 Generalitati
Structurile de date reprezintă modalități ın care datele sunt dispuse ın memoria calculatorului sau sunt păstrate pe discul magnetic.
Structurilor de date sunt utilizate în diferite circumstanțe ca de exemplu:
• Memorarea unor date din realitate;
• Instrumente ale programatorilor;
• Modelarea unor situații din lumea reală.
Cele mai des utilizate structuri de date sunt tablourile, listele, stivele, cozile, arborii, tabelele de dispersie si grafurile.
1.2 Liste
O lista liniară este o structura dinamica de date omogenă, secventială formată din elemente ale listei. Un element, numit cel mai adesea si nod, din lista contine o informație specifică sau eventual o informatie de legatură.
Pozitia elementelor din lista defineste ordinea elementelor. Continutul listei se poate modifica prin adaugarea, inserarea, stergerea orcarui element din lista.
1.2.1 Liste simplu inlantuite
De obicei relația de ordine de la listele liniare simplu înlănțuite o reprezintă relația de succesor, adică fiecare nod conține o adresă către următorul nod al listei. În astfel de liste există numai un nod care nu are succesor (ultimul nod) și numai un nod care nu e succesorul nimănui (primul nod sau capul listei). O asfel de lista ar putea fi reprezentată astfel:
info – reprezinta informatia dintr-un nod;
next – reprezinta adresele elementelor listei;
fiecare nod memoreaza adresa urmatorului nod;
Desi listele pot sa para mai putin attractive decat sirurile, exista totusi cateva avantaje importante. În primul rand inserarea unui element in mijlocul listei nu implica deplasarea tuturor elementelor de dupa punctual de inserare. Deplasarea datelor este foarte costisitoare din punct de vedere al timpului, iar listele inlanuite permit inserarea cu un numar constant de instructiuni de atribuire.
1.2.2 Liste dublu înlantuite
Listele dublu inlantuite au aceleasi caracteristici de baza ca si cele simplu inlantuite.
Diferenta fata de acestea consta in faptul ca, pentru fiecare nod, se retine si adresa elementului anterior, ceea ce permite traversarea listei in ambele moduri. O astfel de lista ar putea fi reprezentata astfel:
Object1,Object2…. – reprezinta informatia dintr-un nod;
header- reprezinta primul nod sau capul listei;
trailer – reprezinta ultimul element din lista sau coada listei;
previous,next- fiecare nod memoreaza adresa anteriorului si respective urmatorului nod;
3.4. Reprezentarea stivelor și cozilor in limbajul java
Înainte de a elabora un algoritm, trebuie să ne gandim la modul in care reprezentam datele. În acest subcapitol vom trece in revistă structurile fundamentale de date cu care vom opera: stive si cozi. Reprezentarea pe care o vom folosi și care este cea mai comodă pentru aceste structuri este cea secvențiala, bazată pe tablouri.
3.4.1. Stiva
O stivă (stack) este o listă liniara cu proprietatea ca operațiile de inserare/extragere a nodurilor se fac în/din coada listei. Dacă nodurile A, B, C, D sunt inserate intr-o stivă in această
ordine, atunci primul nod care poate fi extras este D. In mod echivalent, spunem ca ultimul nod inserat va fi si primul șters. Din acest motiv, stivele se mai numesc si liste LIFO (Last In First Out),sauliste pushdown. Asupra tipului abstract de date stiva sunt definiți următorii cinci operatori: 1) inițializare(st) – face stiva st vida ( inițializarea obiectului se face cu ajutorul unui constructor)
2) peek(st) – furnizează elementul din virful stivei ( deci primul nod al listei ) 3) pop(st) – suprimă elementul din vîrful stivei 4) push(i,st) – inserează elementul x in virful stivei pe care il actualizează 5) isEmpty(st) – funcție booleană ce e adevarată daca stiva este vidă.
Push si pop sunt două operații de bază ale stivei. Dar,cateodată este util să fie posibil să citim valoarea din vârful stivei fară ca s-o extragem. Operatia peek ne permite să efectuam acest lucru.
Cel mai natural mod de reprezentare pentru o stiva este implementarea secventială intr-un tablou st [0..dimMax-1], unde n este numărul maxim de noduri. Primul nod va fi memorat in st[0], al doilea in st[1], iar ultimul in st[top], unde top este o variabilă care conține adresa (indicele) ultimului nod inserat.Inițial, cand stiva este vidă, avem top = -1.
Clasa Stiva
In continuare prezentăm un program ce implementează înserarea și extragerea elementelor dintr-o stiva.
//Stiva.java implementeaza o stiva
class StivaX
{
private int dimMax; // dimensiunea listei tip stiva
private int[] st;
private int top; // varful stivei
//–––––––––––––––––––––
public StivaX(int s) // constructorul clasei StivaX
{
dimMax = s; // setam dimensiunea
st = new int[dimMax]; // initializarea stivei (obiectului st)
top = -1; // initial stiva este vida
}
//–––––––––––––––––––––
public void push(int i) // inseram un nod in stiva
{
st[++top] = i; // top se incrementeaza,inseram nodul
}
//–––––––––––––––––––––
public int pop() // extragem un nod din varful stivei
{
return st[top–]; // top se decrementeaza si se extrage nodul
}
//–––––––––––––––––––––
public int peek() // furnizam nodul din varful stivei
{
return st[top];
}
//–––––––––––––––––––––
public boolean isEmpty() // adevarat daca stiva este vida
{
return (top == -1);
}
//–––––––––––––––––––––
public boolean isFull() // adevarat daca stiva este plina
{
return (top == dimMax-1);
}
//–––––––––––––––––––––
} // starsitul clasei StivaX
////////////////////////////////////////////////////////////////
public class Stiva {
public static void main(String[] args) //metoda principala
{
StivaX stiva = new StivaX(10);// crearea obiectului stiva
stiva.push(10); // inserarea elementelor in stiva
stiva.push(15);
stiva.push(23);
stiva.push(37);
stiva.push(25);
while( !stiva.isEmpty() ) // cat timp stiva nu este vida
{ // se extragem elementele din stiva
int value = stiva.pop();
System.out.print(value); // vizualizam elementul extras
System.out.print(" ");
} // se incheie bucla while
System.out.println(" ");
} // se incheie metoda main()
} // se incheie clasa Stiva
Metoda principală main() crează o stivă ce poate conține cel mult 10 elemente, inserează 5 elemente in stivă si apoi, vizualizează acestea in ordinea extragerii lor din stivă pană când stiva va fi goala. La execuția programului vom obține următorul rezultat:
25 37 23 15 10
Observăm ca ordinea elementelor este inversă. Deoarece ultimul element inserat este primul element extras.
Metodele clasei StivaX
Constructorul StivaX crează o stiva nouă.Dimensiunea stivei––––––––
public int peek() // furnizam nodul din varful stivei
{
return st[top];
}
//–––––––––––––––––––––
public boolean isEmpty() // adevarat daca stiva este vida
{
return (top == -1);
}
//–––––––––––––––––––––
public boolean isFull() // adevarat daca stiva este plina
{
return (top == dimMax-1);
}
//–––––––––––––––––––––
} // starsitul clasei StivaX
////////////////////////////////////////////////////////////////
public class Stiva {
public static void main(String[] args) //metoda principala
{
StivaX stiva = new StivaX(10);// crearea obiectului stiva
stiva.push(10); // inserarea elementelor in stiva
stiva.push(15);
stiva.push(23);
stiva.push(37);
stiva.push(25);
while( !stiva.isEmpty() ) // cat timp stiva nu este vida
{ // se extragem elementele din stiva
int value = stiva.pop();
System.out.print(value); // vizualizam elementul extras
System.out.print(" ");
} // se incheie bucla while
System.out.println(" ");
} // se incheie metoda main()
} // se incheie clasa Stiva
Metoda principală main() crează o stivă ce poate conține cel mult 10 elemente, inserează 5 elemente in stivă si apoi, vizualizează acestea in ordinea extragerii lor din stivă pană când stiva va fi goala. La execuția programului vom obține următorul rezultat:
25 37 23 15 10
Observăm ca ordinea elementelor este inversă. Deoarece ultimul element inserat este primul element extras.
Metodele clasei StivaX
Constructorul StivaX crează o stiva nouă.Dimensiunea stivei este specificată de argumentul s. Câmpurile constructorului conțin o variabilă ce determină lungimea maximă a stivei (dimensiunea tabelului), insuși tabelul, si o variabilă top, care stochează indicele ultimului element din stiva.
Metoda push() incrementează variabila top si inserează un element in stivă.Observăm ca top se incrementează inainte ca elementul sa fie inserat.
Metoda pop() returneazaăultimul element din stivă, si apoi decremeneazaă variabila top.
Metoda peek()returnează ultimul element din stiăa, nemodificând stiva.
Metodele isEmpty() si isFull()returnează true daca stiva este goală, respectiv plina. Atunci cand variabila top are valoarea 1, stiva este goală, si cand are dimMax-1 – stiva este plină.
3.4.2. Coada
O coadă (queue) este o listă liniară in care elementele sunt inserate la un capăt si sunt suprimate la celălalt . Cozile se numesc și liste FIFO (First In First Out), adică de tip primul venit, primul servit.
Asupra tipului abstract de date coada sunt definiți urmatorii cinci operatori: 1) inițializare(cd) – face coada cd vidă (inițializarea obiectului se face cu ajutorul unui constructor). 2) peek(cd) – funcție ce returnează primul element din capul cozii (primul nod al listei). 3) insert(i,cd) – inserează elementul i în coadă. 4) remove(cd) – suprimă primul element inserat in coadă. 5) isEmpty(cd) – funcție ce e adevarata daca coada este vidă.
Observăm că în cazul unei cozi funcțiile membre puch() si pop() sunt inlocuite cu insert(), respectiv remove(). În locul variabilei top, vom avea două date membre, si anume variabilele head si tail.
O reprezentare secventială interesantă pentru coadă se obtine prin utilizarea unui tablou cd [0..dimMax-1], pe care il tratam ca si cum ar fi circular: dupa locatia cd [dimMax-1] urmeaza locatia cd [0].
Să presupunem ca avem o coada cu un numar oarecare de locații numerotate de la 0 la dimMax-1. Inițial coada este goală. Pe masură ce inserăm elemente in coadă acestea ocupa locațiile cd [0],cd [1],…, cd [i].Variabila tail va conține indicele ultimei locații inserate (tail = i). Elementele vor fi extrase din coadă in ordinea in care au fost inserate. Astfel, cand se va extrage primul element inserat, locatia cd [0] va ramane libera.Variabila head va conține indicele locției ce urmează sa fie eliberată.De aceea, cand coada este goală si nu s-a efectuat inca nici o inserare vom avea tail =-1 si head = 0. In timp ce se fac inserări intr-un capăt al cozii si extrageri din celălalt, primele locații din coadă se eliberează si ultimele se ocupaă. Daca ultima locatie din coadă este ocupată (tail = dimMax-1), inserările se vor face din nou in primele locații (tail = -1). Și, daca ultima locație din coaăa este eliberată (head = dimMax), vom incepe să extragem elementele din primele locatii (head = 0).Observăm ca, spre deosebire de o stivă, elementele unei cozi nu intotdeauna ocupă primele locații din tabel. Odată ce un element este extras, valoarea lui head va fi indexul urmatoarei locații ocupate.De exemplu, in figurile date avem o coadă ce contine 10 locatii. Pe masura ce se fac inserări in coadă, observăm ca se ocupă si ultima locație o cozii cd [9]=44. Atunci, următorul element pe care dorim sa-l inserăm (63), va ocupa prima locație liberă din coada – cd s[0]=63.In java vom scrie acest lucru prin metoda insert() sub urmatoarea secventa de cod:
public void insert(int i) // inseram un element in coada
{
if(tail == dimMax-1) // daca ultima locatie este inserata
tail = -1;//atunci indicele ultimei locatii inserate devine -1;
cd[++tail] = i;//incrementam variabila tail si inseram un element
}
si in metoda main() vom face apelul la metoda insert()din clasa coadaX in felul următor:
CoadaX coada = new CoadaX(10);// coada va avea 10 locatii
coada.insert(37); // se insereaza in prima locatie cd[0]=37
… … … // se insereaza in urmatoarele locatii
coada.insert(44); // se insereaza in ultima locatie cd[9]=44
coada.remove();// se extrage primul element inserat cd[0]=37
… … … // se fac extrageri din urmatoarele locatii
coada.insert(63);// se insereaza in prima locatie cd[0]=63
Clasa Coada
În continuare prezentăm un program ce implementează înserarea si extragerea elementelor dintr-o coadă.
//Coada.java implementeaza o coada
class CoadaX
{
private int dimMax; // dimensiunea listei tip coada
private int[] cd;
private int head;
private int tail;
//–––––––––––––––––––––––
public CoadaY(int s) // constructor
{
dimMax = s+1; // tabelul este mai mare cu o locatie
cd = new int[dimMax]; // decat se pretinde a fi
head = 0; // initial coada este goala
tail = -1;
}
//–––––––––––––––––––––––
public void insert(int i) // inseram un element in coada
{
if(tail == dimMax-1) // daca ultima locatie a cozii este ocupata
tail = -1; // inseram elementul in prima locatie libera
cd[++tail] = i; // tail se incrementeaza si se insereaza elementul
}
//–––––––––––––––––––––––
public int remove() // extragem un element din coada
{
int temp = cd[head++]; // head se incrementeaza (indicele locatiei din
// care se va extrage
if (head == dimMax)
head = 0;
return temp;
}
//–––––––––––––––––––––––
public int peek() // furnizam nodul din varful cozii
{
return cd[head];
}
//–––––––––––––––––––––––
public boolean isEmpty() // adevarat daca coada este goala
{
return ( tail+1==head || (head+dimMax-1==tail) );
}
//–––––––––––––––––––––––
public boolean isFull() // adevarat daca coada este plina
{
return ( tail +2==head || (head+dimMax-2==tail) );
}
//–––––––––––––––––––––––
public int size() // (ne asiguram daca coada nu este goala)
{
if(tail >= head) // contiguous sequence
return tail-head+1;
else
return (dimMax-head) + (tail+1);
}
//–––––––––––––––––––––––
} // se incheie clasa CoadaX
class Coada {
public static void main(String[] args)
{
CoadaX coada = new CoadaX(5); // coada va avea 5 locatii
coada.insert(10); // inseram 4 elemente
coada.insert(20);
coada.insert(30);
coada.insert(40);
coada.remove(); // extragem 3 (10)
coada.remove(); //(20)
coada.remove(); //(30)
coada.insert(50); // inseram 4 elemente
coada.insert(60); // (facem circuit)
coada.insert(70);
coada.insert(80);
while( !coada.isEmpty() ) // extragem si vizualizam
{ // elemntele existente in coada
int n = coada.remove(); // (40, 50, 60, 90, 80)
System.out.print(n);
System.out.print(" ");
}
System.out.println("");
} // se incheie metoda main()
}
Programul Coada.java constă din două clase CoadaX si Coada. Prima clasă conține un constructor prin care se inițializeaza coada si metodele insert(int i),remove(),peek(), isEmpty(),isFull()si size().
Metoda principală main()din a doua clasaă crează o coadă cu 5 locatii, inserează 4 elemente (10,20,30,40), extrage primele 3 elemente inserate (10,20,30) si inserează din nou 4 elemente (50,60,70,80). La a sasea inserare se obține un circuit. Apoi, in bucla while se extrag elementele existente din coadă si sunt vizualizate in ordinea extragerii lor. La execuția programului vom obține următorul rezultat:
40 50 60 70 80
Metodele clasei CoadaX
Metoda insert().
Înainte de a insera un element, trebuie sa ne asigurăm ca nu avem o coadă plina.Acest lucru se poate verifica prin douaă metode:
In metoda principală se apelează metoda insert()dupa metoda isFull(). Dacă prima metodă returnează valoarea false , atunci avem locații libere in care putem insera si apelăm metoda insert().
Se poate verifica daca coada este plină printr-o rutina din metoda insert().In timp ce se incearcă sa se insereze intr-o coadă plina se va genera o excepție.
În metoda insert() se incrementează variabila tail si se inserează un element in locatia cd[tail].Daca tail contine indicele ultimei locatii din lista, atunci ne deplasăm la inceputul tabelului inainte de inserare (tail=−1).Astfel, cand se va incrementa variabila, tail va fi indicele primei locații din coadă.
Metoda remove().
Inainte de a extrage un element, trebuie să ne asigurăm ca existaăelemente in coadaăce pot fi extrase. Similar cu metoda insert(), avem două posibilitațti de verificare:
In metoda principală se apeleaza metoda isEmpty() inaintea metodei remove().Dacă valoarea returnată a metodei isEmpty()este false, atunci avem elemente in coadă si le putem extrage.
Putem construi o eroare de verificare in metoda remove().Daca se va incerca să se extraga un element dintr-o coada goala, la compilare va aparea un mesaj de eroare.
Metoda peek()
Aceasta metodă este asemenea cu cea din stivă. Returnează primul element din capul listei cd[head].
Metodele isEmpty(),isFull() si size().
Dacă as avea o variabilă de tip intreg ce indica numarul de elemente din coada (int nElemente), atunci reprezentarea acestor metode ar fi foarte simplă:
O coadă este goală cand nu contine nici un element ( nElemente = 0 ).
O coadă este plina cand toate locațiile sunt ocupate ( nElemente = dimMax-1 ).
Pentru a vedea numarul de elemente dintr-o coada la un moment dat, vom returna variabila nElemente (return nElemente).
Programul Coada.java a fost implementat fară aceasta variabila, de aceea s-a determinat dacă
o coadă este goală, respectiv plina si câte elemente contine cu ajutorul variabilelor membre head si tail.
Vom avea o coadă goală daca locatia în care urmeaza sa se insereze (tail+1) este egala cu locatia din care urmează să se extraga (head). Astfel tail+1=head sau head+dimMax-1=tail.
Să presupunem ca avem o coada plină: s-au inserat elemente in toate locațiile si nu s-a extras nici unul diontre ele. Atunci, vom avea head=0 indicele locației din care urmează
sa se extragă si tail=dimMax-1 indicele locație in care s-a facut ultima inserare. Deci, o coada este plina daca: dimMax-1 +1 = 0 tail+1 = head.Observăm ca coada pare a fi plină si goală in acelasi timp. Pentru a evita aceasta constradictie am construit un tabel cu o celula mai mult fată de numarul maxim de elemente ce pot fi plasate in el (dimMax = s+1). Astfel, vom avea o coadă plina când tail+2=head sau head+dimMax-2=tail.
Pe masur ce se inserează și se extrag elementele in/din coadă putem avea două situțtii:
Dacă tail >= head, atunci nElemente
1.1. Noțiuni generale
În general, pentru situațiile care necesită la rezolvare un oarecare efort mintal, se caută, în primul rând, o metodă de reprezentare a lor care să permită receptarea întregii probleme dintr-o privire și prin care să se evidențieze cât mai clar toate aspectele acesteia.
În acest scop se folosesc imagini grafice gen diagrame, schițe, grafice etc. O reprezentare dintre cele mai utilizate este cea prin grafuri. Acestea sunt utilizate în special pentru vizualizarea sistemelor și situațiilor complexe. În general, vom reprezenta componentele acestora prin puncte în plan iar relațiile (legăturile, dependențele, influențele etc.) dintre componente prin arce de curbă cu extremitățile în punctele corespunzătoare. Între două puncte pot exista unul sau mai multe segmente (în funcție de câte relații dintre acestea, care ne interesează, există),iar segmentelor li se pot asocia sau nu orientări (după cum se influențează cele două componente între ele), numere care să exprime intensitatea relațiilor dintre componente etc.
Este evident, totuși, că această metodă are limite, atât din punct de vedere uman (prea multe puncte și segmente vor face desenul atât de complicat încât se va pierde chiar scopul pentru care a fost creat – claritatea și simplitatea reprezentării, aceasta devenind neinteligibilă) cât și din punct de vedere al tehnicii de calcul (un calculator nu poate "privi" un desen ca un om).
Din acest motiv, alături de expunerea naiv-intuitivă a ceea ce este un graf, dată mai sus, se impune atât o definiție riguroasă cât și alte modalități de reprezentare a acestora, adecvate în general rezolvărilor matematice.
Grafurile sunt una dintre cele mai multilaterale structuri in programare.In rezolvarea unor probleme folosirea grafurilor este indispensabila.
1.2. Noțiunea de graf
1.2.1. Definiția grafului neorientat și orientat
Se numește graf neorientat o pereche ordonata de mulțimi,notată G=(V,E) care satisface condiția E,unde V este o muțime finita și nevidă de elemente numite noduri (sau vârfuri), iar E este o mulțime de perechi (neordonate) de elemente distincte din V numite muchii.O muchie având vârfurile i și j (numite extremitațile sale) este notată cu [i,j] sau [j,i].
Un exemplu de graf orientat este: rețeaua de străzi a unui oraș. Străzile sunt muchii în graf, iar intersecțiile reprezintă vârfurile grafului. Întrucât mergând pe jos ne putem deplasa pe orice stradă în ambele sensuri, vom spune că din punctul de vedere al pietonilor, „graful unui oraș” este neorientat.
Cu totul altfel stau lucrurile în ceea ce privește conducătorii auto, pentru că în orice oraș există străzi cu sens unic. Pentru un șofer străzile trebuie să primească în graf o anumită orientare. Desigur că acele străzi pe care se poate circula în ambele sensuri vor primi orientare dublă. Am ajuns astfel la noțiunea de graf orientat.
Un graf orientat este o pereche ordonată G=(V,E),unde V este o mulțime finită și nevidă de elemente numite noduri (sau vârfuri),iar E este o mulțime de perechi ordonate de elemente distincte ale lui V,numite arce. Un arc având vârfurile i si j (numite extremitațile sale) se notează prin (i,j).Deci, deosebirea fața de grafurile neorientate constă în faptul că fiecare arc (i,j) are un sens de parcurgere și anume de la extremitatea sa inițială la extremitatea sa finală.
Pentru a evita ambiguitatea în notație,specificăm că VE = 0.
Moduri de reprezentare ale unui graf
O primă modalitate de reprezentare este listarea efectivă a tuturor nodurilor și a arcelor sale.
Un graf poate fi reprezentat într-un plan sub forma unei figuri geometrice alcătuite din cerculețe (noduri) și segmente de curbă (muchii) care au ca extremitați nodurile arcului și pe care sunt trecute câte o sageată orientată de la nodul inițial spre cel final.
Putem folosi o reprezentare geometrică în care nodurile sunt reprezentate de două ori, în două șiruri paralele, de la fiecare nod din unul din șiruri plecând săgeți spre nodurile cu care formează arce în care el este pe prima poziție, de pe al doilea șir (reprezentarea prin corespondență).
Putem reprezenta graful dând pentru fiecare nod mulțimea nodurilor cu care formează arce în care el este pe prima poziție.
De asemenea,printr-un graf se poate reprezenta o hartă rutieră. Sa presupunem că nodurile unui graf reprezintă localitățile și muchiile – drumuri între aceste localități.Un graf nu asigură reprezentarea geografică a unei hărți,ci relațiile sau conexiunile ce există între localități (noduri) și drumuri (muchii).
Un graf poate fi reprezentat printr-o matrice pătratică booleană, de dimensiune egală cu numărul de noduri, în care o poziție aij va fi 1 dacă există arcul (xi,xj) și 0 în caz contrar, numită matricea adiacențelor directe.
Un graf poate fi reprezentat printr-o matrice pătratică latină, de dimensiune egală cu numărul de noduri, în care pe o poziție aij va fi xixj dacă există arcul (xi,xj) și 0 în caz contrar.
Exemplu: Dacă în reprezentarea A avem graful G = (V,E), unde V = {x1, x2, x3, x4, x5, x6} și E = {(x1,x1), (x1,x2), (x1,x4), (x1,x5), (x2,x3), (x2,x4), (x2,x6), (x3,x1), (x3,x2), (x4,x5), (x5,x2), (x6,x4)}, atunci în celelalte reprezentări vom avea:
B C(reprezentarea prin corespondență)
D
x2 {x3, x4, x6}
x3 {x1, x2}
x4 {x5}
x5 {x2}
x6 {x4}
E
a) Harta rutieră b) Reprezentarea grafică a hărții rutiere
F G
Desenarea și reprezentarea vârfurilor și segmentelor de curbă în sine este mai puțin relevantă/importanța,ceea ce ne interesează este care dintre perechile de vârfuri formează o muchie și care nu.
Vârfurile unui graf se notează cu V(G) și muchiile cu E(G). Dar pentru comoditate se intrebuințează și notația simplificată : vG și eG.
Noțiuni de bază în teoria grafurilor
Proprietăți
a) Vom spune că un graf este simplu dacă el nu are nici muchii multiple și nici bucle.
b) Un graf cu un număr de V-vârfuri poate avea cel mult V(V-1)/2 muchii.
Demonstrație: Să presupunem că avem un graf cu V numărul de noduri,atunci vom avea V2 perechi de noduri posibile,respectiv muchii:
Dacă excludem mulțimile de perechi de vârfuri {11,22,33,…,VV} și {12,21,13,31,…,(V-1)V,V(V-1)} ce formează muchii bucle și muchii multiple,obținem un număr maxim de muchii posibile într-un graf simplu: (V2 – V)/2 = V(V – 1)/2.
Ordinul unui graf
Numim ordinul unui graf,numărul de noduri al grafului,deci cardinalul mulțimii V(G),și notăm această valoare cu |G|.Numărul de muchii se notează cu ||G||.
Graful null este graful cu 0 muchii și 0 vârfuri – G(0,0) și se notează cu (0).
Vom spune că un nod v este incident cu o muchie e dacă v e;atunci e este o muchie a vârfului v.Două vârfuri incidente cu o muchie formează marginile muchiei.O muchie {x,y}de obicei se notează xy (sau yx).Dacă xX și yY,atunci xy este o muchie X-Y.
Mulțimea tuturor muchiilor X-Y dintr-o mulțime E este notată E(X,Y);în locul lui E({x},Y) și E(X,{y}) noi scriem simplu E(x,Y) și E(X,y).Mulțimea tuturor muchiilor E a vârfului v se notează E(v).
Două vârfuri x și y se numesc adiacente sau vecine,dacă există o muchie care le unește (cu care amandouă vârfurile sunt incidente).
Vom nota (x)={yV;xyE} vecinătatea vârfului x din graful G.
Două muchii ef sunt adiacente dacă au o extremitate comună.
Un graf pentru care oricare 2 vârfuri sunt adiacente,se numește graf complet.Un graf complet cu n numărul de vârfuri se notează ; un graf format din trei vârfuri adiacente- se numește triunghi.O mulțime de vârfuri și muchii se numesc independente dacă nu conțin perechi de elemente adiacente.
Considerăm G := (V , ) și := (,).
Dacă = 0, atunci G și sunt grafuri disjuncte.
Dacă V și E,atunci este un subgraf al lui G (și G este supergraf al lui )și vom scrie G.
Fie ,vom spune că este un subgraf al lui G,dacă acesta conține o parte din vârfurile lui G și numai acele muchii care le conectează ( conține muchiile xyE cu x,y),
induce în G și vom scrie = G[].
Astfel,dacă UV o mulțime de vârfuri,atunci G[U] induce un graf U ale carui muchii aparțin grafului G cu extremitățile sale.
Dacă H este un subgraf a lui G,nu neapărat indus,vom ușura notația acestuia din G[V(H)] în G[H]. În final, este un subgraf indus de G dacă = V .
Dacă U este o mulțime de vârfuri ale unui graf G,prin G – U vom înțelege G[V-U].Cu alte cuvinte,G – U este obținut din graful G prin stergerea vârfurilor UV și muchiilor pe care le formează.Dacă mulțimea U conține un singur element (U = {v}) vom scrie G-v în loc de G-{v}.
În locul lui G-V() vom scrie simplu G-.
Pentru o submulțime F din scriem G-F =(V,E – F) și G+F = (V,EF);
La fel,G-{e} și G+{e} este abreviat cu G-e și G+e.
Dacă G și sunt disjuncte,vom nota prin G* un graf obținut din G prin reuniunea tuturor vârfurilor din grafurile G și .De exemplu, *=.
Gradul unui nod dintr-un graf
Numim gradul unui nod particular x (xV(G)),numărul de arce care sunt conectate la acel nod și se notează cu (x) =|(x)| ,unde (x) numărul vărfurilor adiacente cu vărful x.
De exemplu,dacă (x)=0, x este un vărf izolat și dacă (y)=1,y este un vărf suspendat.
Vom nota cu (G) = min {r(v)| vV} gradul minim al lui G și ∆(G) :=max {r(v)|vV} gradul maxim a lui G.
Vom spune că un graf G este trivial dacă acesta are gradul 0 sau 1.
Dacă toate vârfurile unui graf G au grade egale (r(x)=k),vom spune că G este k-regulat,sau simplu – graf regulat.De exemplu,dacă toate vârfurile unui graf au gradul 3 vom spune că avem un graf regulat de gradul 3 sau un graf cubic.
Notăm prin r(G) gradul unui graf G,care este media aritmetică gradelor tuturor nodurilor din G.
r(G) = r(G)*|V |=. Evident vom avea: (G) ≤ r(G) ≤ ∆(G).
Dacă adunăm gradele tuturor nodurilor din graful G,obținem de două ori numarul de muchii: .Faptul că membrul drept al ecuației va fi mereu par,implică aceeași proprietate în membrul stâng,pentru ca egalitatea să fie satisfacută. Suma tuturor termenilor r(v) impari trebuie să fie o sumă al unui număr par de termeni, pentru a fi pară. Astfel deducem că orice graf are un număr par de noduri al căror grad este impar.
Pentru a evita dublarea numărului de muchii considerăm următorul raționament: fie ε(G),vom demonstra că r(G) și ε(G) sunt valori apropiate. Avem |E| = = r(G)*|V| ε(G)*r(G).Deci,gradul lui G este r(G)= 2*ε(G).
Propoziția 1.Orice graf G care conține cel puțin o muchie,are un subgraf H astfel încât (H)>ε(H)ε(G).Orice graf G are un subgraf a cărui grad mediu nu e mai mic decat gradul lui G: (v)r(v) și al cărui grad minim este mai mare decat jumătate din gradul său.
Drumuri și cicluri într-un graf
Se numește drum simplu o succesiune de muchii adiacente și distincte care conectează două vârfuri dintr-un graf (numite capetele drumului).
Vom nota un drum cu P=(V,E) unde V={,…,} și E ={},cu noduri distincte.
Vârfurile și se numesc capetele drumului,iar sunt vârfurile interne ale lui P.
Numărul muchiilor într-un graf determina lungimea drumului și un drum de lungimea k vom nota cu .De exemplu dacă lungimea unui drum este 0 atunci graful conține un singur vârf: =.Vom spune că avem un drum de la la și vom scrie P=….
Pentru 0 ≤ i ≤ j ≤ k vom folosi urmatoarele notatii pentru drumuri și subdrumuri ale unui graf:
P = … = …
P = … = …
P = … = …
= …
P = …
P = …
P = …
Vom folosi aceste notații pentru reprezentarea și concatenarea drumurilor.De exemplu,dacă avem trei drumuri Px,xQy și yR distincte,concatenarea lor este tot un drum,astfel,vom scrie PxxQyyR PxQyR.
Fig.1
Fig.1
Fie A și B doua mulțimi de noduri ale lui G,vom spune ca P = … este un drum A-B dacă V(P)A = {}si V(P)B = {}.
Un drum în care fiecare nod apare o singură dată se numește drum elementar.
Un drum în care fiecare arc apare o singură dată se numește drum simplu.
Două sau mai multe drumuri se numesc independente dacă nu conțin noduri interioare comune.
De exemplu,două drumuri a-b sunt independente,dacă și numai dacă conțin numai a și b noduri comune.
Se numește drum hamiltonian un drum elementar care trece prin toate nodurile grafului și drum eulerian un drum simplu care conține toate arcele grafului.
Definiția 1. Fie G=(V,E) un graf orientat.Un subgraf al lui G este definit ca fiind graful G'=(V',E') unde V'V și E'(xi) = E(xi) V' pentru orice xi V',adică E' este formată din toate arcele lui E care au drept extremitați nodurile din V'.
Un graf parțial al lui G este graful (V,E') în care E'E.Altfel spus,un graf parțial al lui G ,este chiar G,sau se obține din G păstrând toate vârfurile și suprimând niște muchii.Graful parțial se mai numește și subgraf de acoperire al lui G.
Fie G=(V,E) un graf și V'V o submulțime nevidă al lui V.Numim subgraf al lui G indus de V' și îl notăm <V'> acel subgraf care are ca noduri mulțimea V' și oricare două noduri din V' sunt adiacente în <V'> dacă și numai dacă sunt adiacente în G.
Conexiuni într-un graf
Spunem că un graf este conex dacă între oricare doua vârfuri ale acestuia exista cel puțin un drum sau dacă oricare două vârfuri și sunt unite printr-un lanț. De exemplu grafurile din figurile a) și b) nu sunt conexe, în timp ce graful din figura c) este un graf conex. Graful trivial este considerat conex.
a) Graf neorientat b) Graf orientat c)Graf complex și conex
Fig.2
Complementul unui graf G este graful (V, \E),care conține o muchie între vârfurile x și y dacă și numai dacă G nu conține o astfel de muchie. Complementarul unui graf care nu este conex, este un graf conex.
Un graf în care între oricare două noduri există cel puțin un drum se numeste graf tare conex și un graf în care între oricare două noduri există cel puțin un lanț se numeste graf simplu conex.
Observație: Pentru grafuri neorientate noțiunile de tare conex și simplu conex sunt echivalente, graful numindu-se doar conex;
Daca un graf nu este conex se pune problema determinării componentelor sale conexe.O componentă conexa fiind subgraf conex maximal,adică un subgraf conex în care un vârf din subgraf nu este unit cu unul din afară printr-o muchie din primul graf.O componentă fiind conexă,este întotdeauna nenulă.Respectiv,grafuri nule nu au componente conexe.
Se numește componentă tare conexă a unui graf G = (V,U) un subgraf al lui G care este tare conex și nu este subgraful nici unui alt subgraf tare conex al lui G (altfel spus, între oricare două noduri din componentă există cel puțin un drum și nu mai există nici un nod în afara componentei legat printr-un drum de un nod al componentei).
Determinarea componentelor conexe se poate realiza pentru ca relația "u este conectat cu v" unde u,v V,este o relație de echivalentă.Ea va determina partiționarea lui V în clase de echivalența ,…,,iar gafurile induse <> i= sunt conexe.Ele vor fi componentele conexe ale lui G.
Fig7
În cazul unui ciclu hamiltonian putem considera că vârfurile și muchiile din ciclul hamiltonian formează un subgraf de acoperire al grafului inițial.Graful care conține un ciclu hamiltonian poartă numele de graf hamiltonian.
Dacă A,BV și XVE astfel încât fiecare A-B drum din G conține un vârf sau o muchie din X.Vom spune că X separă mulțimile A și B din G.Aceasta implică în particular ca ABX. Vom spune că X separă G și vom numi X o mulțime de separare în G,dacă X separă două vârfuri din G-X în G.Un vârf ce separă alte două vârfuri ale aceleiași componente,se numește vârf de separare (cutvertex),și o muchie ce separă prin extremitațile sale se numește punte (bridge).Astfel punțile unui graf sunt acele muchii care nu aparțin unui ciclu din graf.
Fig.3 Un graf cu v,x,y,w vârfuri de separare și e=xy o punte
Vom spune că G este k-conex (pentru kN) dacă |G| > k și G-X este conex pentru fiecare mulțime X V cu |X|<k.Cu alte cuvinte,Nu există două noduri ale lui G să fie separate de mai puțin de k alte noduri.Orice graf nenul este cel puțin 0-conex,și 1-conex este graful conex non-trivial.Fie kN cel mai mare număr întreg și fie G un k-conex graf,vom spune că k(G) este conexiunea lui G. k(G) = 0 dacă și numai dacă G nu este conex sau un (graful cu un singur vârf).Astfel vom avea k()=n-1 pentru oricare n1.
Dacă |G| > 1 și G – F este conex pentru oricare F E de cel puțin l muchii,atunci vom spune că G este l-muchii-conex (l-edge-connected).Fie l cel mai mare număr întreg,dacă G este l-muchii-conex vom spune că λ(G) este conexiune de muchii a lui g (edge-connectivity).În particular,vom avea λ(G) = 0 dacă G nu este conex.
Pentru orice non-trivial graf G vom avea k(G) ≤ λ(G) ≤ δ(G).Astfel pentru conexiuni cât mai mari avem grade cât mai mici.Invers,în general,nu este adevărat.Un grad cât mai mic nu implică să avem conexiuni cât mai mari.
Teorema 1. Orice graf cu gradul de cel puțin 4k va conține un k-subgraf conex.
Demostrație:
Pentru k{0,1}demonstrația este absurdă,de aceea vom considera k2.Fie G = (V,E) un graf cu |V|=n și |E|=m numărul de noduri și muchii din G.Prin inducție vom demonstra cu usurință afirmația teoremei.
Graful G are un k-subgraf conex dacă
n 2k -1 si
m (2k – 3)(n – k + 1) +1.
Din ipoteza știm că r(G) 4k unde r(G) este gradul lui G.
Astfel,vom avea n >∆(G) r(G) 4k n 2k-1 (i)
Stim că m2kn m(2k-3)(n-k+1)+1 (ii)
Vom folosi inducția după n.Dacă n = 2k-1,atunci k = (n+1), și de aici avem m n(n-1) din relația (ii). Astfel G = și n2k .Daca v este un nod cu r(v)2k-3, putem aplica ipoteza inductivă pentru G-v.Vom avea δ(G) 2k-2.Dacă G este k-conex,nu avem ce demonstra. Considerăm că G are urmatoarea formă: G = cu || < k și ||,|| < n.Astfel încât fiecare muchie aparține grafului sau ,adică G nu conține muchii între și .Cât timp oricare nod din aceste subgrafuri are cel puțin δ(G) 2k-2 noduri vecine,vom avea ||,|| ≥ 2k-1. Dar cel puțin unul din subgrafuri trebuie să satisfacă ipoteza inductivă de mai sus.Dacă nici un subgraf nu satisface această ipoteză,vom avea
|||| ≤ (2k -3)(||- k+1)
pentru i = 1,2 avem
m |||| + ||||
(2k-3)(|| – k + 1) + (2k-3)(|| – k +1)
(2k-3)(|| + || – 2k +2)
(2k-3)(n – k + 1) (dar || ≤ k-1)
contradicție cu (ii).
Capitolul 2-Concepția structurii de arbore
Noțiuni generale
Noțiunea de arbore, proprietăți
Arborii sunt una dintre cele mai importante structuri neliniare care apar în algoritmii pentru calculatoare. Structura arborescentă implică o relație de ramificare între noduri, foarte asemănătoare celei întâlnite la crengile unui arbore din natură.
Există mai multe moduri echivalente de definire a arborilor.Din punct de vedere al teoriei grafurilor numim arbore un graf neorientat conex și fara cicluri. Dacă graful este aciclic, dar nu este conex îl vom numi pădure. Astfel o pădure este un graf ale cărui componente sunt arbori.
a)Arbore b)Padure(nu e conex)
Fig.1
Proprietăți ale arborilor :
Există un nod în care nu intră nici un arc, numit rădăcina arborelui
Cu excepția rădăcinii,fiecare nod are proprietatea că în el intră un singur arc. Acesta leagă nodul respectiv de un alt nod numit predecesor sau părinte.
Dintr-un nod pot ieși unul sau mai multe arce. Fiecare astfel de arc, leagă nodul respectiv de un alt nod numit sucessor sau fiu al nodului.
Nodurile sunt organizate pe nivele, primul nivel fiind ocupat de nodul rădăcină. Nodurile de pe ultimul nivel se caracterizează prin faptul că din ele nu mai iese nici un arc, și se numesc noduri terminale sau și acestea vor avea întotdeauna gradul nodului (x) = 1.
Nodurile pot conține o așa numită informație utilă, care poate fi de orice tip.Această informație,numită cheie (value key) este folosită pentru căutarea elementelor de date sau alte operații. Grafic cheia unui nod este afișată în interiorul nodului sau lângă acesta.
Oricare arbore non-trivial are cel puțin două noduri terminale, de exemplu capetele celui mai mare drum.Dacă vom șterge o frunză dintr-un arbore,vom obține tot un arbore.
Studiul arborilor este justificat de existența în practică a unui număr mare de probleme care pot fi modelate prin arbori. Dintre acestea amintim:
construirea unor rețele de aprovizionare cu apă potabilă (sau cu energie electrică sau termică etc) a unor puncte de consum, de la un punct central;
construirea unor căi de acces între mai multe puncte izolate;
desfășurarea unui joc strategic;
luarea deciziilor în mai multe etape (arbori decizionali);
evoluții posibile ale unui sistem pornind de la o stare inițială;
construirea unei rețele telefonice radiale, a unei rețele de relee electrice;
legarea într-o rețea a unui număr mare de calculatoare;
organigramele întreprinderilor;
studiul circuitelor electrice în electrotehnică (grafe de fluență etc);
schemele bloc ale programelor pentru calculatoare etc.
În toate problemele de mai sus se dorește ca, dintre muchiile unui graf neorientat, să se extragă arborele optim din mulțimea tuturor arborilor care pot fi extrași din graful dat.
Deoarece definiția arborelui este dificil de aplicat pentru deciderea faptului că un graf este arbore sau nu (și în special sunt greu de verificat conexitatea și mai ales existența ciclurilor) există mai multe caracterizări posibile ale unui arbore, acestea fiind date de teorema de mai jos:
Teorema 1
Fie H = (V,E) un graf neorientat.Următoarele afirmații sunt echivalente:
H este un arbore;
Oricare două vârfuri din H sunt unite printr-un lanț simplu unic.
H este conex minimal,adică dacă i se suprimă o muchie se creează două componete conexe și H-e va fi neconex pentru oricare eE.
H este conex și are |V| – 1 muchii.
H este aciclic și are |V| – 1 muchii.
H este aciclic maximal,adică dacă adaugăm o muchie,graful obținut va conține cicluri (H+xy este ciclic pentru oricare două vârfuri nediacente x,yV).
Demonstrație:
1 2
Dacă H este arbore, atunci H este conex, deci oricare ar fi două vârfuri din graf, acestea sunt unite prin cel puțin un lanț simplu și vom nota acest lanț cu xHy. Presupunem prin reducere la absurd că există x și y două vârfuri unite prin două lanțuri simple distincte l1 și l2 .
Fig.2.
Fie z primul vârf de la care cele două lanțuri se despart, iar t primul vârf în care cele două lanțuri se întâlnesc din nou. Dacă notăm l'1 porțiunea de pe lanțul l1 între z și t, iar cu l'2 porțiunea de pe lanțul l2 între z și t, atunci l'1 și l'2 nu au vârfuri comune, cu excepția vârfurilor z și t. Concatenând l'1 și l'2, obținem un ciclu- contradicție cu ipoteza că H este arbore. Deci, oricare două vârfuri din graf sunt unite printr-un lanț simplu unic.
2 3
Dacă oricare două vrfuri x, yV sunt unite printr-un lanț simplu unic, atunci orice muchie x, yE reprezintă unicul lanț dintre x și y. Suprimând muchia x, y, între x și y nu va mai exista lanț, deci graful obținut nu va mai fi conex.
3 4
Notăm cu n numărul de vrfuri și cu m numărul de muchii din graf.
Pentru a demonstra că orice graf conex minimal are n-1 muchii vom demonstra prin inducție completă după n că m n-1. Cum n orice graf conex m n-1, deducem m n-1.
P(1) Dacă n 1, atunci m 0 m n-1.
P(2) Dacă n 2, atunci m 1 m n-1.
P(n) Presupunem că într-un graf conex minimal cu cel mult n vârfuri numărul de muchii este strict mai mic decât numărul de vârfuri.
P(n1) Demonstrăm că într-un graf conex minimal cu n1 vârfuri, numărul de muchii este cel mult egal cu n.
Fie H conex minimal cu n1 vârfuri și m muchii. Eliminând o muchie oarecare din graf obținem un graf H' cu m-1 muchii și două componente conexe H1 și H2 cu n1, respectiv n2 vârfuri (n1n2 n1) și m1, respectiv m2 muchii (m1m2 m-1). Subgrafurile H1 și H2 sunt conexe minimale, altfel graful H nu ar fi conex minimal. Din ipoteza inductivă rezultă că m1 n1-1, m2 n2-1; dar m1m2 m-1 n1n2 n-2 m n-1. Deci H conex minimal implică H conex cu n-1 muchii.
4 5
Fie H un graf conex cu n-1 muchii. Să demonstrăm că H este aciclic.
Presupunem prin reducere la absurd, că graful H conține un ciclu C format din vârfurile v1, v2, …, vk.
Să considerăm subgraful parțial Hk (Vk, Ek) constând din ciclul C. Deci Vk v1, v2 ,…, vk, iar Ek v1,v2, v2,v3,…,vk-1,vk, [vk,v1 (VkEk k). Dacă Vk<V, atunci viVk și vk1V-Vk astfel încât vi, vk1E, graful E fiind conex.
Construim Hk1 (Vk1, Ek1) astfel :Vk1 Vk vk1; Ek1Ekvi,vk1 și Ek1Vk1k1.
Cât timp k1 < n, aplicăm același procedeu până când obținem un graf Hn (V, En), cu En n, En E; deci E n, contradicție cu ipoteza E n-1.
5 6
Presupunem că graful H este aciclic cu n-1 muchii, să demonstrăm că H este aciclic maximal.
Fie C1, C2,…, Cp cele p componentele conexe ale grafului H, având respectiv n1, n2,…, np vârfuri și m1, m2,…, mp muchii fiecare. Evident că n1n2…np n i m1m2…mp n-1.
Cum graful H este aciclic, deducem că fiecare componentă conexă este un arbore. Deoarece am demonstrat că 1 5, rezultă că m i ni-1, i1, 2, …, p. nlocuind n relația de mai sus, obținem n-p n-1 p 1, deci H conex. Dacă H este conex și aciclic, conform definiției H este arbore. Dar am demonstrat că 1 2, deci oricare două vârfuri din H sunt unite printr-un lanț simplu. Astfel, adăugând orice muchie obținem un ciclu.
6 1
Presupunem că graful H este aciclic, dar dacă am mai adăuga o muchie s-ar obține un ciclu. Să demonstrăm că H este conex.
Fie u și v două vârfuri neadiacente din graf, arbitrar alese. Deoarece adăugând muchia u, v se obține un ciclu, rezultă că u și v sunt unite printr-un lanț ale cărui muchii aparțin grafului H. Cum u,v au fost alese arbitrar, deducem că graful H este conex.
Q.E.D.
Corolar1:Vârfurile unui arbore pot fi oricând enumerate cu v1, v2,…,vn astfel incât oricare vi cu i ≥ 2 va avea un singur vecin in multimea { v1,…,vi-1 }.
Corolar2:Daca H este un arbore si G este un graf oarecare cu gradul minim δ(G) ≥ |H| -1.Atunci H G si G va conține un subgraf isomorfic cu H.
Demonstratie:Putem gasi in graful G o copie a arborelui H dupa principiul de numerotare inductivă a vârfurilor acestuia demonstrat in Colorar1.
Fie G = (V,E) un graf neorientat.Un graf parțial H al lui G,cu proprietatea ca H este arbore,se numeste arbore parțial al lui G.
Un graf neorientat G conține un arbore parțial dacă și numai dacă G este conex.
Arbori cu rădăcină
Pentru problemele în care se impune o ierarhizare a informațiilor ce corespund vârfurilor arborelui, astfel încât anumite vârfuri să fie subordonate altora, este utilă introducerea unei noi noțiuni- arbore cu rădăcină. Arborii cu rădăcină sunt o prezență cotidiană. Fiecare și-a reconstituit la un moment dat arborele genealogic și, după cum vom vedea, cea mai mare parte a termenilor folosiți n limbajul informatic derivă de aici. Un alt exemplu este modul de organizare a competițiilor sportive sau organigrama unei ntreprinderi.
De regula,intr-un arbore un vârf este considerat radacina acestuia.Vom spune ca avem un arbore cu radacina (rooted tree),daca radacina acestuia este fixa.
Definiție:
Un arbore cu rădăcină este o mulțime finită de noduri care fie este vidă fie
– există un nod special numit rădăcina arborelui;
– toate celelalte noduri sunt partiționate în n 0 clase A1, A2, …, An, fiecare clasă fiind un arbore cu rădăcină. Rădăcina arborelui este unită prin muchii de rădăcinile arborilor A1, A2, …, An.
Definiția este recursivă, orice nod al unui arbore fiind rădăcina unui subarbore.
Fig.3
Să observăm că alegând într-un mod arbitrar un vârf drept rădăcină, orice graf neorientat conex și fără cicluri este un arbore cu rădăcină în sensul definiției de mai sus. Arborii A1, A2, …, An se numesc subarborii rădăcinii, numărul de subarbori nevizi ai unui nod fiind numit gradul nodului respectiv.
De exemplu:
Fig.4
Să observăm că definiția conduce la o ierarhizare a nodurilor arborelui,acest lucru are urmatoare consecințe:
Putem aseza arborele pe nivele astfel:
Se plasează radacina r pe nivelul 1;
Dacă notam cu r1, r2, …, rn respectiv rădăcinile arborilor A1, A2, …, An, nodurile r1, r2, …, rn vor constitui nivelul 2 în arbore, ș.a.m.d. Se plaseaza pe fiecare nivel i ≥ 2 vârfurile pentru care lungimea lanțurilor care le leaga de radacina este i-1;
Se trasează muchiile grafului.
Arborele devine graf orientat,stabilindu-se pentru fiecare muchie un sens de parcurgere și anume de la nivelul superior (cu număr de ordine mai mic) la nivelul imediat inferior(cu numărul de ordine mai mic cu o unitate)….(cap9)
Nodurile r1, r2, …, rn, se numesc fiii nodului rădăcină, iar rădăcina r reprezintă părintele nodurilor r1, r2, …, rn, rădăcina fiind singurul nod din arbore care nu are părinte. Fiecărei muchii din arbore îi putem asocia o orientare de la părinte spre fiu. n plus, fiii nodurilor de pe nivelul i0, vor constitui nivelul i1.
Nivelul maxim din arbore va constitui nălțimea (adncimea) arborelui respectiv. Să observăm că orice nod x poate fi atins din rădăcină pe un drum unic. Orice nod y care se găsește pe drumul unic de la r la x se numește ascendent (strămoș) al lui x. Dacă y este un ascendent al lui x, atunci x se numește descendent al lui y. Mai exact, toți descendenții unui nod x sunt nodurile din subarborele cu rădăcină x. Dacă un nod nu are descendenți el se numește nod terminal sau frunză. Două noduri care au același părinte se numesc frați.
În exemplul din fig.4, 2 este un ascendent al lui 6. Nodurile 5, 6, 7, 9, 10 sunt noduri terminale. Nodurile 9,10 sunt frați, iar descendenții nodului 4 sunt nodurile 8, 9,10.
Daca notam cu r radacina unui arbore H,celelalte varfuri V(H) le vom nota intr-o anumita ordine astfel incat x ≤ y daca x rTy și vom spune ca avem un arbore-ordonat (tree-order) cu multimea de vârfuri V(H) si radacina r (ultimul element).Extremitațile oricarei muchii din H pot fi comparabile.Multimile pentru care oricare element x are proprietatea {x | x ≤ y}(unde y este vârf fix oarecare)se numeste un lant (chain),o multime de perechi de elemente comparabile.
Teorema 2. Numerele întregi 0 < r1 r2 … rn (n 2) sunt gradele vârfurilor unui arbore dacă și numai dacă r1r2…rn 2n-2.
Demonstrație:
Necesitatea Condiția este necesară, deoarece orice arbore cu n vârfuri are n-1 muchii, iar suma gradelor vârfurilor oricărui graf este de două ori numărul de muchii. Deci r1r2…rn 2n-2.
Suficiența Fie 0 < r1 r2 … rn astfel încât r1r2…rn 2n-2.
Să demonstrăm că există un arbore cu gradele vârfurilor r1, r2,…, rn. Vom proceda prin inducție.
P(n) Presupunem acum că proprietatea este adevărată pentru orice secvență de n numere naturale 0 < r1 r2 … rn, astfel încât r1r2…rn 2n-2.
P(n1) Să demonstrăm că pentru orice secvență 0 < r'1 r'2 … r'n r'n1 astfel încât r'1r'2…r'n1 2n, există un arbore cu n1 vârfuri cu secvența gradelor r'1, r'2, …, r'n1.
Observăm că există măcar un nod terminal x1 cu gradul r'11, altfel dacă ri 2,i1, 2,…, n1 r'1r'2…r'n1 2(n1), ceea ce contrazice ipoteza. n mod analog, observăm că există măcar un nod neterminal xn1, cu gradul r'n1 > 1, altfel dacă r'i 1,i1, 2, …, n1 r'1r'2…r'n1 n1 < 2n .
Să considerăm următoarea secvență de n numere ntregi r'2,…, r'n, r'n1-1 cu proprietatea că r'2…r'nr'n1 2n-2. Din ipoteza inductivă există un arbore An cu n vârfuri și secvența gradelor r'2,…, r'n, r'n1-1. Adăugăm la arborele An un vârf pe care îl unim printr-o muchie cu vârful având gradul r'n1-1. Obținem un arbore An1 cu gradele vârfurilor r'1, r'2,…, r'n1.
Arbori binari
Definiție
Exista mai multe tipuri de arbori.Daca intr-un arbore un nod are mai mult de doi fii vom spune ca avem un arbore multidrum (multiway tree).Un exemplu de acest tip de arbore putem vedea in fig.1. Dar,daca fiecare nod al unui arbore va avea cel mult doi descendenți(succesori),cu excepția frunzelor,vom spune ca avem un arbore binar.Arborele binar constituie o clasă foarte importantă de arbori cu rădăcină.
Fig.5
Observații :
Orientarea de la arborii cu rădacină (generată de plasarea vârfurilor pe niveluri) se menține si in cazul arborilor binari.
Reprezentarea pe niveluri determină sa nu mai fie necesar sensul arcelor.
Fiecare vârf poate fi considerat radacina pentru un subarbore.Evident,pentru fiecare vârf vom avea subarborele stâng si subarborele drept,eventual unul din ei sau amândoi putând fi arbori vizi (fară nici un varf).
Proprietațile unui arbore binar
Proprietatea 1.
Numărul maxim de noduri de pe nivelul i al unui arbore binar este 2i.
Demonstrație:
Vom proceda prin inducție după numărul nivelului.
P(0) Pe nivelul i 0 se găsește un singur nod (rdăcina).
P(k) Presupunem că numărul maxim de noduri de pe nivelul k este
2k.
P(k1) Vom demonstra că pe nivelul k1 sunt cel mult 2k1 noduri.
Pe nivelul k1 se găsesc fiii nodurilor de pe nivelul k. Din ipoteza inductivă, pe nivelul k se găsesc cel mult 2k noduri, iar fiecare nod poate avea cel mult doi fii, deci pe nivelul k1 se găsesc cel mult 2*2k 2k1 noduri.
Q.E.D.
Proprietatea 2.
Numărul maxim de noduri într-un arbore cu înălțimea h este 2h1-1.
Demonstrație:
Numărul maxim de noduri într-un arbore cu înălțimea h se obține atunci când fiecare nivel i este plin, deci, conform propoziției anterioare, conține 2i noduri. Numărul maxim de noduri într-un arbore cu înălțimea h va fi:
Q.E.D.
Proprietatea 3.
În orice arbore binar nevid cu n0 noduri terminale există n0-1 noduri de grad 2.
Demonstrație:
Notăm cu n0 numărul de noduri terminale, cu n1 numărul de noduri de grad 1 i cu n2 numărul de noduri de grad 2. Deci, numărul total de noduri nn0n1n2.
Dacă numărăm muchiile dintr-un arbore binar, observăm că fiecare nod, cu excepția rădăcinii, are o singură muchie orientată spre el. Notând m numărul de muchii obținem n m1. Dar orice muchie provine de la un nod de grad 1 sau 2, rezultă că m n12n2.
Din n2 + n0 = 2n2 + 1 n2 n0-1.
Q.E.D.
Proprietatea 4.
Un arbore cu n vârfuri are înălțimea cel puțin egală cu log2n.
Demonstrație:
În cazul cel mai favorabil, nodurile sunt dispuse pe niveluri astfel încât fiecare nivel să fie plin, cu excepția, eventuală, a ultimului nivel. Deci arborele binar cu n noduri de înălțime minimă este arborele binar complet cu n vârfuri, care, din modul de construcție, are înălțimea log2n.
Q.E.D.
Proprietatea 5.
Definim lungimea drumurilor interne (I) ca fiind suma lungimilor drumurilor de la rădăcină la noduri neterminale (interne) și lungimea drumurilor externe (E) ca fiind suma lungimilor drumurilor de la rădăcină la noduri terminale (frunză sau externe). Într-un arbore binar cu n noduri interne, E I2n.
Demonstrație:
Vom proceda prin inducție după n, numărul nodurilor interne.
P(0) Într-un arbore cu 0 noduri interne (vid sau format numai din rădăcină) E I 0.
P(n-1) Presupunem că într-un arbore binar An-1, cu n-1 noduri interne, are loc relația En-1 In-12(n-1).
P(n). Vom demonstra că într-un arbore binar An, cu n noduri interne, are loc relația En In2n.
Fie An un arbore binar cu n noduri interne. Există n An un nod intern x care are drept fii două noduri terminale. Îndepărtând din An fiii nodului x, nodul x se transformă în nod terminal, deci obținem un arbore An-1 cu n-1 noduri interne. Din propoziția inductivă rezultă că n arborele A n-1, En-1 In-12(n-1). Dacă notăm cu d, lungimea drumului de la rădăcină la nodurile eliminate, obținem relațiile :
En En-12d-(d-1) (în An nodurile eliminate sunt terminale, dar nodul x nu, lungimea drumului de la rădăcină la x fiind d-1).
In In-1(d-1) (în An nodul x este intern).
Deci En In-12(n-1)d1 In-d12n-2d1 In2n.
Q.E.D.
Capitolul 3-Algoritmul si reprezentarea unui graf in limbajul java
Probleme de drumuri minime intr-un graf
Întroducere
Definiția 1 :Se numeste graf ponderat sau valuat și se notează G=(V,E,l) un graf (V,E) căruia i se asociază o funcție l:E → R+ numită ponderea arcelor.
Exemple:
l(x,y) = lungimea tronsonului de drum,(x,y) care uneste localitatile x si y;
l(x,y) = capacitatea tronsonului de drum (x,y).
Definiția 2: Se numeste rețea de transport un graf orientat,G=(V,E), fără bucle, cu următoarele proprietăți:
exista un nod x0 unic,numit originea rețelei,si care nu are ascendenti;
exista un nod xf unic,numit destinația rețelei,si care nu are descendenti;
fiecărui arc eE ii este asociat un număr l(u) ≥ 0 numit capacitatea arcului e.
Fie G = (X,U,l) un graf conex (ipoteza necesară pentru a asigura existența cel puțin a unui arbore) ponderat neorientat.Se pune problema găsirii arborelui de acoperire de lungime minima,adica,folosind arce ale grafului să se lege intre ele toate nodurile astfel incat lungimea totală a arcelor folosite (suma ponerilor) să fie minima.O astfel de problemă apare in proiectarea rețelelor de comunicații,unde obiectivul este să se minimizeze lungimea cablului necesar conectării tuturor nodurilor care trebuie să comunice intre ele,in proiectarea retelelor de drumuri,benzi rulante,sisteme de canalizare etc.În continuare sunt prezentați doi algoritmi care rezolva aceasta problema.
3.1.1 Algoritmul lui Dijkstra
Se pune problema determinării unui plan de transport printr-o rețea rutieră (de transport) astfel incât cheltuielile de transport sau duratele de transport să fie minime.Este necesar să se determine drumul cel mai "scurt" dintre două noduri oarecare ale rețelei rutiere.Acest tip de problemă se intalnește si in proiectarea rețelelor de calculatoare,in stabilirea treaseelor mijloacelor de transport in comun etc.(Henry-Labordere,1995)
Algoritmul lui Dijkstra permite calcularea lungimilor celor mai scurte drumuri de la un vârf s la toate vârfurile x ale unui graf conex G = (X,U,l),dacă lungimile tuturor arcelor sunt nenegative.
Fie (x) lungimea celui mai scurt drum de la s la x.Fie S multimea vârfurilor pentru care se calculează .Atunci, (x) {lungimea celui mai scurt drum de la s la x,care are toate vârfurile in S cu excepția lui x }.Se notează cu (x) = {mulțimea arcelor care pornesc din nodul x},iar cu (x) = {mulțimea arcelor care intra in nodul x}.Dacă graful este neorientat (x) = (x) = (x) = mulțimea arcelor incidente in nodul x.
AlgoritmulDijkstra
Pas 1. {Inițializări}
S := {s}; s nodul de start, (s) :=0;
Pentru orice x X S dacă x (s) atunci (x) := l(s,x) altfel
(x) := + ;
Pas 2. {Iterația curentă}
Repetă
Determină y X S astfel încât (y) = (z);
Dacă (y) < atunci S := S {y};
Pentru z (y) (z) := min {(z), (y)+ l(z,y)};
pâna când S = X sau (y) = .
Pas 3. Stop.
Se observă că valorile (z) rămân nemodificate pentru z S,lucru ce poate fi exploatat în transpunerea pe calculator a algoritmului.
Exemplu.In Figura 1 sunt date 7 localitați numerotate de la 1 la 7 și timpul (în ore) necesar parcurgerii distanței pe arterele care le leaga.Să se determine ruta pe care se realizează timpul minim între localitațile 1 și 7.
Rezolvare.Se aplică algoritmul Dijkstra grafului reprezentat de Figura 1.
Fig.1
Pas 1. s=1, S = {1}, (1) = {2,4},
Pas 2.
{(y)} = {(z)}= min{(2), (3), (4), (5), (6), (7)}= (2),
y = 2, S = {1,2}, (2) = {1,3,4}.
(2) = l([1,2]) = 1
(3) = min{(3), (2) + l([2,3])} = min{ ,1+4} = 5
(4) = min{(4), (2) + l([2,4])} = min{ 4,1+2} = 3
Iterația a II-a.
{(y)} = {(z)}= min{(3), (4), (5), (6), (7)}= (4), y = 4, S = {1,2,4},
(4) = {1,2,3,5,6}.
(3) = min{(3), (4) + l([3,4])} = min{ 5,3+5} = 5
(5) = min{(5), (4) + l([4,5])} = min{,3+2} = 5
(6) = min{(6), (4) + l([4,6])} = min{,3+9} = 12
Iterația a III-a.
{(y)} = {(z)}= min{(3), (5), (6), (7)}= (3), y = 3, S = {1,2,3,4},
(3) = {2,4,5,6}.
(5) = min{(5), (3) + l([3,5])} = min{5,5+2} = 5
(6) = min{(6), (3) + l([3,6])} = min{12,5+3} = 8
Iterația a IV-a.
{(y)} = {(z)}= min{(5), (6), (7)}= (5), y = 5, S = {1,2,3,4,5},
(5) = {3,4,6,7}.
(6) = min{(6), (5) + l([5,6])} = min{8,5+6} = 8
(7) = min{(7), (5) + l([5,7])} = min{,5+7} = 12
Iterația a V-a.
{(y)} = {(z)}= min{(6), (7)}= (6), y = 6, S = {1,2,3,4,5,6},
(6) = {3,4,5,7}.
(7) = min{(7), (6) + l([6,7])} = min{12,8+1} = 9
Iterația a VI-a.
{(y)} = {(z)}= min{(7)}= (7), y = 7, S = {1,2,3,4,5,6,7},
Pentru nodurile din mulțimea S (y) nu s-au mai evaluat (y).
Algoritmul se oprește deoarece S=X. Vectorul (y) conține cele mai mici distanțe de la nodul 1 la celelalte noduri.Drumul cel mai scurt între nodurile 1 si 7 se obține din muchiile (marcate cu litrere îngroșate ) D = {[1,2],[2,3],[3,6],[6,7]} și este de 9 ore.
În Management Scientist modulul determina cel mai scurt drum dintre doua noduri ale rețelei și precizează muchiile care realizează acest drum.
3.2 Structuri de date utilizate în reprezentarea grafurilor
Graful are o organizare variabilă.Spre deosebire de un arbore binar, in care fiecare vârf are cel mult doi fii, vârful unui graf poate fi adiacent cu un numar arbitrar de alte vârfuri.
Exemplu: In Figura 2 avem un graf conex in care vârful A este adiacent cu alte trei vârfuri,in timp ce vârful C este adiacent numai cu un singur vârf .
Exista două metode uzuale de reprezentare a grafurilor: matricea
de adiacentă si lista de adiacentă.
Fig.2
3.2.1. Matricea de adiacentă
O matrice de adiacentă este un tablou bidimensional in care fiecare element indică dacaă există o muchie între două noduri sau nu.Daca un graf are N numărul de noduri, matricea de adiacentă va fi un tablou cu N linii si N coloane.
Definiție: Fie G=(V,E) un graf si n=|V|,m=|E|.Se numeste matricea de adiacență a grafului G, matricea =() cu n linii și n coloane,ale carei elementele satisfac relatia:
unde V={} si unde s-a ales o ordine pe mulțimea vărfurilor.
Observații:
1.Deasemenea putem folosi și valori booleene true/false petru reprezentarea elementelor matricii.
2.În functie de ordinea aleasă pe multimea vârfurilor matricea de adiacență este unic determinată.
3 În cazul grafului neorientat matricea de adiacență este simetrică (in raport cu diagonala principală.
4.În cazul grafului orientat,deoarece arcul () nu este totuna cu arcul (),matricea de adiacență nu mai este simetrica față de diagonala principală.
Exemplu: Mai jos avem matricea de adiacentă pentru graful neorientat din Figura 2. Observăm ca A este adiacent cu toate cele trei vârfuri, B este adiacent cu A si D, C este adiacent numai cu A, si D este adiacent cu A si B. Conexiunea varfului la el insusi este notată cu 0, astfel diagonala principală a matricii are valoarea 0. Triungiul deasupra diagonalei principale este simetric cu cel de desuput. Intr-un graf neorientat aceste triunghiuri conțin aceeasi informțtie.
3.2.2. Liste de adiacența (vecinilor)
Este a doua metoda de reprezentare a grafurilor.O listă de adiacentă este un tablou de liste (sau o listă de liste).Fiecare listă individuală arată care vârfuri sunt adiacente cu un varf dat.
Exemplu: In Tabelul 1 avem liste de adiacentă pentru graful din Figura 2.
Tabelul 1. Liste de adiacentă
Simbolul → indică legătura intr-o lista . In fiecare listă varfurile sunt aranjate intr-o ordine alfabetică.De regulă, acesta nu este obligatoriu.
Într-un graf orintat pentru fiecare nod x , cu x, se construiesc două liste ale vecinilor săi :
L+(x) – lista vecinilor succesori; conține nodurile ce sunt extremități finale ale arcelor care ies din nodul x
L-(x) – lista vecinilor predecesori; conține nodurile ce sunt extremități inițiale ale arcelor care intră în nodul x
Reprezentăm graful orientat din Figura 3 prin cele două metode:
Matricea de adiaceță Liste de adiacență
Mai tarziu vom explica in ce situații se intrebuințeaza fiecare metodă de reprezentare a unui graf. De regulă se folosește matricea de adiacentă ,dar in unele situații liste de adiacentă sunt mai eficiente.
3.3. Adăugarea vârfurilor și a muchiilor intr-un graf
Pentru adăugarea unui vârf in graf vom crea cu new un obiect nou listaVarfuri in clasa Vertex.În programe complexe un vârf poate conține mai multe elemente de date,dar pentru comodiate vom presupune că vârfurile grafului nostru conține un singur tip de date.Deci, pentru crearea unui vârf vom folosi urmatoarea secvețta de cod:
listaVarfuri[nVarfuri++] = new Vertex ('F');
aceasta inserează un vărf F, unde nVarfuri este numărul curent al vârfurilor din graf. Modul de adaugarea a unei muchii in graf depinde de tipul structurii de date pe care o folosim pentru reprezentarea grafului. Să presupunem ca lucrăm cu matricea de adiacență si vrem sa introducem o muchie intre vârfurile 1 si 3.Aceste numere corespund cu indicii tabelului listaVarfuri unde sunt stocate vârfurile.Când creem o matrice de adiacentă matAdiacenta , ințtial elementele matricei vor fi 0-uri.Pentru a insera o muchie,vom scrie:
matAdiacenta[1][3] = 1;
matAdiacenta[3][1] = 1;
Dar dacă vom folosi o lista de adiacenta,vom adauga 1 la lista lui 3, si 3 la lista lui 1.
Clasa Graf
Considerăm următorul program in care avem o clasa Graf ce contine metodele addVertex addEdge si displayVertex pentru adăugarea vârfurilor și muchiilor intr-un graf si vizualizarea acestora:
{
private class Graf
final int V_MAX = 20; // numarul constant maxim de varfuri
private Varf listaVarfuri[]; // lista de varfuri
private int matAdiacenta[][]; // matricea de adiacenta
private int nVarfuri; // numarul curent de varfuri
private StivaX stiva;
// ––––––
public Graf() // constructorul clasei Graf
{
listaVarfuri = new Varf[V_MAX]; //initializam obiectul listaVarfuri
matAdiacenta = new int[V_MAX][V_MAX]; //initializam Matricea de adiacenta
nVarfuri = 0;
for(int i=0; i<V_MAX; i++) //initial setam elementele matricii cu 0
for(int j=0; j<V_MAX; j++)
matAdiacenta[i][j] = 0;
stiva = new StivaX();
} // se incheie constructorul
// ––––––
public void addVertex(char lab) // metoda de adaugare a unui varf
{
listaVarfuri[nVarfuri++] = new Varf(lab);
}
// ––––––
public void addEdge(int start, int end) //metoda de adaugare a unei muchii
{
matAdiacenta[start][end] = 1;
matAdiacenta[end][start] = 1;
}
// ––––––
public void displayVertex(int v) //metoda de vizualizare a varfurilor
{
System.out.print(listaVarfuri[v].label);
}
} // se incheie clasa Graf
In cadrul clasei Graf vârfurile sunt indentificate prin numărul indicilor din lista de vârfuri listaVarfuri. Prin constructia System.out.print(listaVarfuri[v].label) am tiparit eticheta vârfului nou creat ,pentru vizualizarea. Matricea de adiacentă (sau lista de adiacentă) furnizează informații generale despre vârfuri create,cum ar fi adiacentța lui cu alte vârfuri,etc.
= tail-head+1.
Dacă s-a produs un circuit si head > tail, atunci
nElemente = (dimMax-head) + (tail+1).
3.5 Algoritmul Depth-First Search (DFS) – parcurgerea in adâncime
Depth-First-Search este tehnica de parcurgere (explorare) a grafurilor in adâncime.
Dat fiind G = (V,E) un graf conex și nodul sursa s. Vizităm mai intâi nodul s, apoi primul nod nevizitat adiacent cu s, mergând in adâncime cat este posibil. Când un nod x nu mai are vecini nevizitati ne intoarcem să cercetam dacă nodul din care a fost atins x mai are sau nu vecini nevizitați si continuam parcurgerea.In metoda Depth-First-Search vom folosi stiva pentru ca sa știm unde trebuie să mergem după ce am atins ultimul vârf.
Exemplu: Să realizam parcurgerea DFS pentru graful din Figura 8 :
Fixăm nodul de start s = A. Conform algoritmul DFS vizităm acest nod, marcand-ul, ca să stim ca a fost deja vizitat și il introducem in stiva, astfel incât sa-l tinem minte. Apoi, alegem un nod oarecare adiacent cu A, din cele care nu au fost inca vizitate. Daca avem mai multe noduri ce satisfac aceeasi conditție (in cazul nostru nodurile B,C,D,E), pentru a ne fi mai usor le vom așeza
în ordinea alfabetica. Deci, B va fi urmatorul nod vizitat. Il marcam si îl plasăm in stiva. Acum repetăm acelasi rationament cu nodul B: alegem un nod adiacent cu B, care nu a fost incă vizitat.Astfel, ajungem la nodurile F si H.
Definim prima regula de parcurgere:
Regula 1: Dacă este posibil,se vizitează un nod adiacent si nevizitat, se marcheazaăsi se introduce in stiva.
Aplicând regula 1 ajungem la nodul H.Observăm ca aceasta regula nu mai are aplicabilitate, deoarece H nu are vârfuri adiacente si nevizitate. În această situatie aplicăm regula a 2-a:
Regula 2: Dacă nu se poate urma regula 1, si este posibil, se scoate un vârf din stivă.
Conform acestei reguli, in exemplul nostru scoatem H din stivă, si ajungem inapoi la F. Acesta din urma nu are varfuri adiacente nevizitate. Il scoatem din stiva. La fel procedam cu B. Acum doar A mai este in stiva. A are trei varfuri adiacente nevizitate C,D,E dintre care alegem C,etc. Repetăm rationamentul, pană când vom reveni din nou la vârful A si vom descoperi ca A nu mai are vârfuri adiacente nevizitate. Îl scoatem din stivă.Si aplicăm regula 3.
Regula 3: Dacă nu se poate urma nici una din regulile precedente,graful este parcurs si algoritmul este incheiat.
Fig.4
Codul java
Scopul algoritmului DFS este de a gasi vârfurile ce nu au fost vizitate și sunt adiacente cu un vârf specificat. Pentru a reprezenta acest lucru vom folosi o matrice de adiacentă. Să presupunem că avem un graf simplu conex ca in Figura 5. Matricea de adiacentă pentru acest graf este M5×5. Graful nu este orientat, de aceea matricea de adiacentă asociată lui va fi simetrică fata de diagonala principala. Să presupunem ca incepem parcurgerea grafului de la varful A (pozitia 0×0 din matrice).
Cautăm vârfurile adiacente cu A, adica elementele de pe prima linie a matricii cu valoarea 1. După ce am gasit vârfurile adiacente cu A, verificăm daca ele nu au fost vizitate. Daca da, vărful găsit este urmatorul vârf ce va fi vizitat. Daca nu, vom scrie ca nu există pe prima linie vârfuri adiacente cu A si nevizitate in acelasi timp.
Repetăm rationamentul pentru toate liniile din matrice i=.
Fig.5
În java vom reprezenta acest mecanism in metoda obtineVarfAdiacentNevizitat() prin urmatoare secventă de cod:
//returneaza un varf nevizitat adiacent cu v
public int obtineVarfAdiacentNevizitat(int v)
{
for(int i=0; i<nVarfuri; i++)
if(matAdiacenta[v][i]==1 && listaVarfuri[i].aFostVizitat==false)
return i;
return -1;
}
Acum suntem gata pentru metoda dfs() a clasei Graf care practic duce la bun sfârsit parcurgerea in adâncime (Deph-First-Search). Putem observa ca codul ce urmează va cuprinde cele trei reguli relatate mai sus.Vom folosi un ciclu in care se vor efectua anumite operații cât timp stiva nu este goală:
while( !stiva.isEmpty() )
În cadrul ciclului se vor efectua patru operații de bază:
Se va examina nodul din vârful stivei,folosind metoda peek().
Se va cauta un vecin nevizitat al acestui vârf.
Dacă nu se va gasi,vârful nostru se va scoate din stivă
Dacă se va găsi asemnenea vârf, îl vom vizia si il vom plasa in stivă
Codul pentru metoda dfs() va arăta in felul următor:
public void dfs() // parcurgerea in adancime
{ // vom incepe cu primul varf,cu indicele 0
listaVarfuri[0].aFostVizitat = true; // il marcam
displayVertex(0); // il vizualizam
stiva.push(0); // inseram in stiva
while( !stiva.isEmpty() ) // pana cand stiva este goala,
{
// obtinem un varf nevizitat adiacent cu cel din varful stivei
int v = obtineVarfAdiacentNevizitat( stiva.peek() );
if(v == -1) // daca nu exista asemenea varf,
stiva.pop(); // extragem un varf din stiva
else // daca exista asemenea varf,
{
listaVarfuri[v].aFostVizitat = true; // il marcam
displayVertex(v); // il vizualizam
stiva.push(v); // il plasam in stiva
}
} //se incheie bucla while
// stiva este goala,am terminat
for(int i=0; i<nVarfuri; i++) // resetam flagurile
listaVarfuri[i].aFostVizitat = false;
} // se incheie metoda dfs()
La sfărsitul metodei dfs() am resetat toate flagurile care au fost vizitate astfel incât să putem rula metoda din nou.În timp ce stiva este goală din nou si nu necesita sa fie resetată.Deci, avem toate componentele necesare unei clase Graf.În continuare vom crea graful din Figura 5 (un obiect al clasei Graf), vom adăuga vârfurile si muchiile acestuia, si vom realiza o parcurgere in adâncime:
Graph unGraf = new Graph();
unGraf.addVertex('A'); // 0 varful de start in parcurgerea dfs
unGraf.addVertex('B'); // 1
unGraf.addVertex('C'); // 2
unGraf.addVertex('D'); // 3
unGraf.addVertex('E'); // 4
unGraf.addEdge(0, 1); // AB
unGraf.addEdge(1, 2); // BC
unGraf.addEdge(0, 3); // AD
unGraf.addEdge(3, 4); // DE
System.out.print("Ordinea de parcurgere in adancime a varfurilor este:");
unGraf.dfs(); //apelam metoda dfs()
System.out.println();
La execuția programului vom obține următorul rezultat:
Ordinea de parcurgere in adancime a varfurilor este: ABCDE
Astfel, putem reprezenta oricare alt graf si urmări cum se desfasoara parcurgerea lui in adâncime.
Pentru a finisa reprezentarea algoritmului Depth-First-Search prezentăm programul DFS.java, ce reunește clasele StivaX,Varf,Graf si DFS. Programul crează graful din Figura 5 și efectueazaăparcurgerea lui in adâncime:
package Grafuri;
class StivaX
{
private final int SIZE = 20;
private int[] st;
private int top;
public StivaX() // constructor
{
st = new int[SIZE]; // initializam stiva,cream un tablou
top = -1;
}
public void push(int j) // inseram elementul in stiva
{ st[++top] = j; }
public int pop() // extragem elementul din stiva
{ return st[top–]; }
public int peek() // furnizam nodul din varful stivei
{ return st[top]; }
public boolean isEmpty() // adevarat daca stiva este vida
{ return (top == -1); }
} // starsitul clasei StivaX
////////////////////////////////////////////////////////////////
class Varf
{
public char label; // eticheta varfului,'A' de exemplu
public boolean aFostVizitat;
// ––––––
public Varf(char lab) // constructor
{
label = lab;
aFostVizitat = false;
}
// ––––––
} // se incheie clasa Varf
////////////////////////////////////////////////////////////////
class Graf
{
private final int V_MAX = 20;
private Varf listaVarfuri[]; // lista de varfuri
private int matAdiacenta[][]; // matricea de adiacenta
private int nVarfuri; // numarul curent de varfuri
private StivaX stiva;
// ––––––
public Graf() // constructorul clasei Graf
{
listaVarfuri = new Varf[V_MAX];
// matricea de adiacenta
matAdiacenta = new int[V_MAX][V_MAX];
nVarfuri = 0;
for(int i=0; i<V_MAX; i++)//setam matricea de adiacenta cu 0 initial
for(int j=0; j<V_MAX; j++)
matAdiacenta[i][j] = 0;
stiva = new StivaX();
} // se incheie constructorul
// ––––––
public void addVertex(char lab)
{
listaVarfuri[nVarfuri++] = new Varf(lab);
}
// ––––––
public void addEdge(int start, int end)
{
matAdiacenta[start][end] = 1;
matAdiacenta[end][start] = 1;
}
// ––––––
public void displayVertex(int v)
{
System.out.print(listaVarfuri[v].label);
}
// ––––––
public void dfs() //parcurgerea in adancime
{ // vom incepe cu primul varf,cu indicele 0
listaVarfuri[0].aFostVizitat = true; // il marcam
displayVertex(0); // il vizualizam
stiva.push(0); // inseram in stiva
while( !stiva.isEmpty() ) // pana cand stiva este goala,
{
// obtinem un varf nevizitat adiacent cu cel din varful stivei
int v = obtineVarfAdiacentNevizitat( stiva.peek() );
if(v == -1) // daca nu exista asemenea varf,
stiva.pop(); // extragem un varf din stiva
else // daca exista asemenea varf
{
listaVarfuri[v].aFostVizitat = true; // il marcam
displayVertex(v); // il vizualizam
stiva.push(v); // il plasam in stiva
}
} // se incheie bucla while
// stiva este goala,am terminat
for(int i=0; i<nVarfuri; i++) // resetam flagurile
listaVarfuri[i].aFostVizitat = false;
} // se incheie metoda dfs()
// ––––––
//returneaza un varf nevizitat adiacent cu v
public int obtineVarfAdiacentNevizitat(int v)
{
for(int i=0; i<nVarfuri; i++)
if(matAdiacenta[v][i]==1 && listaVarfuri[i].aFostVizitat==false)
return i;
return -1;
} // se incheie metoda obtineVarfAdiacentNevizitat()
} // se incheie clasa Graf
////////////////////////////////////////////////////////////////
public class DFS {
public static void main(String[] args)
{
Graf unGraf = new Graf();
unGraf.addVertex('A'); // 0 (varful de start in parcurgerea dfs)
unGraf.addVertex('B'); // 1
unGraf.addVertex('C'); // 2
unGraf.addVertex('D'); // 3
unGraf.addVertex('E'); // 4
unGraf.addEdge(0, 1); // AB
unGraf.addEdge(1, 2); // BC
unGraf.addEdge(0, 3); // AD
unGraf.addEdge(3, 4); // DE
System.out.print("Ordinea de parcurgere in adancime a varfurilor este: ");
unGraf.dfs(); // apelam metoda dfs()
System.out.println();
}
}
3.6 Algoritmul Breadth-First Search (BFS) – parcurgerea in lațime
O alta tehnică de parcurgere (explorare) a grafurilor este metoda Breadth-First-Search (parcurgerea in lațime).
Dat fiind un graf conex G = (E,V) și un nod sursa s V, metoda BFS impune vizitarea mai intâi a nodului și, apoi a tuturor nodurilor nevizitate adiacente cu s, apoi a tuturor nodurilor nevizitate adiacente nodurilor adiacente cu s, s.a.m.d.
Așa cum am văzut în parcucgerea Depth-First-Search ne indepărtam de vârful de start cât mai repede posibil. Pe de altă parte, in parcurgerea Breadth-First-Search observăm ca algoritmul preferă să stea cat mai aproape de vârful de start. Conform algoritmului BFS in primul rând se vizitează toate varfurile adiacente cu vârful de start, si abia după aceea următoarele vârfuri. Spre deosebire de parcurgerea in adâncime, parcurgerea in lățime nu este in mod natural recursivă. Pentru parcurgerea in lătime,vom utiliza o coada.
Codul java
Metoda bfs() a clasei Graf este similară cu metoda dfs(), cu exceptiă faptului ca se foloseste o coadă in locul unei stive si coține două bucle while , una in interiorul alteia. Bucla
exterioară asteapta ca coada sa fie goaăa, in care bucla interioară caută un vârf nevizitat si adiacent cu un vârf curent.
Codul pentru metoda bfs() va arata in felul următor:
public void dfs() // parcurgerea in latime
{ // vom incepe cu primul varf,cu indicele 0
listaVarfuri[0].aFostVizitat = true; // il marcam
displayVertex(0); // il vizualizam
coada.insert(0); // inseram in coada
int v2;
while( !coada.isEmpty() ) // cat timp coada este goala,
{
int v1 = coada.remove(); // extragem varful din capul cozii
// cat timp acest varf nu are vecini nevizitate
while ( (v2 = obtineVarfAdiacentNevizitat(v1)) != -1 )
{
listaVarfuri[v2].aFostVizitat = true; // il marcam
displayVertex(v2); // il vizualizam
coada.insert(v2); // il inseram in coada
} //se incheie bucla while interna
} //se incheie bucla while externa
// coada este goala,am terminat
for(int i=0; i<nVarfuri; i++) // resetam flagurile
listaVarfuri[i].aFostVizitat = false;
} // se incheie metoda bfs()
În continuare prezentăm programul BFS.java care crează graful din Figura 5 si efectuează parcurgerea lui in lățime.Acest program este similar cu programul DFS.java cu exceptia introducerii clasei CoadaX in locul clasei StivaX si a metodei bfs() in locul metodei dfs().
//programul BFS.java efectueaza parcurgearea in latime a unui graf
package Grafuri;
class CoadaX
{
private final int SIZE = 20;
private int[] cd;
private int head;
private int tail;
public CoadaX() // constructor
{
cd = new int[SIZE]; // initializam coada,cream un tablou
head = 0;
tail = -1;
}
public void insert(int i) // inseram un elemnt in coada
{
if(tail == SIZE-1)
tail = -1;
cd[++tail] = i;
}
public int remove() // extragem un element din coada
{
int temp = cd[head++];
if(head == SIZE)
head = 0;
return temp;
}
public boolean isEmpty() // adevarat daca coada este goala
{
return ( tail+1==head || (head+SIZE-1==tail) );
}
} // se incheie clasa CoadaX
////////////////////////////////////////////////////////////////
class Varf1
{
public char label;
public boolean aFostVizitat;
// ––––––––––––––––––––-
public Varf(char lab) // constructor
{
label = lab;
aFostVizitat = false;
}
// ––––––––––––––––––––-
} // se incheie clasa Varf
////////////////////////////////////////////////////////////////
class Graf
{
private final int V_MAX = 20;
private Varf listaVarfuri[]; // lista de varfuri
private int matAdiacenta[][]; // matricea de adiacenta
private int nVarfuri; // numarul curent de varfuri
private CoadaX coada;
// ––––––
public Graf() // constructorul clasei Graf
{
listaVarfuri = new Varf[V_MAX];
matAdiacenta = new int[V_MAX][V_MAX]; // matricea de adacenta
nVarfuri = 0;
for(int i=0; i<V_MAX; i++) // setam elementele matricei
// initial cu 0
for(int j=0; j<V_MAX; j++)
matAdiacenta[i][j] = 0;
coada = new CoadaX();
} // se incheie constructorul
// ––––––––––––––––––––-
public void addVertex(char lab)
{
listaVarfuri[nVarfuri++] = new Varf(lab);
}
// ––––––––––––––––––––-
public void addEdge(int start, int end)
{
matAdiacenta[start][end] = 1;
matAdiacenta[end][start] = 1;
}
// ––––––––––––––––––––-
public void displayVertex(int v)
{
System.out.print(listaVarfuri[v].label);
}
// ––––––––––––––––––––-
public void bfs() // parcurgerea in latime
{ // vom incepe cu primul varf
listaVarfuri[0].aFostVizitat = true; // il marcam
displayVertex(0); // il vizualizam
coada.insert(0); // inseram in coada
int v2;
while( !coada.isEmpty() ) // cat timp coada nu este vida,
{
int v1 = coada.remove(); // extragem un varf din capul cozii
// cat timp v2 este un varf nevizitat si adiacent cu v1
while( (v2=obtineVarfAdiacentNevizitat(v1)) != -1 )
{
listaVarfuri[v2].aFostVizitat = true; // il marcam
displayVertex(v2); // il vizualizam
coada.insert(v2); // il inseram
} // se incheie bucla while interna
} // se incheie bucla while externa
// coada este goala,am terminat
for(int i=0; i<nVarfuri; i++) // resetam flagurile
listaVarfuri[i].aFostVizitat = false;
} // se incheie metoda bfs()
// ––––––––––––––––––––-
// returnam un varf nevizitat adiacent cu v
public int obtineVarfAdiacentNevizitat(int j)
{
for(int i=0; i<nVarfuri; i++)
if(matAdiacenta[j][i]==1 && listaVarfuri[i].aFostVizitat==false)
return i;
return -1;
} // se incheie metoda obtineVarfAdiacentNevizitat()
// ––––––––––––––––––––-
} // se incheie clasa Graf
////////////////////////////////////////////////////////////////
class BFS
{
public static void main(String[] args)
{
Graf unGraf = new Graf();
unGraf.addVertex('A'); // 0(varful de start in parcurgerea bfs)
unGraf.addVertex('B'); // 1
unGraf.addVertex('C'); // 2
unGraf.addVertex('D'); // 3
unGraf.addVertex('E'); // 4
unGraf.addEdge(0, 1); // AB
unGraf.addEdge(1, 2); // BC
unGraf.addEdge(0, 3); // AD
unGraf.addEdge(3, 4); // DE
System.out.print("Ordinea de parcurgere in latime a varfurilor este: ");
unGraf.bfs(); // parcurgerea in latime
System.out.println();
} // se incheie metoda main()
} // se incheie clasa BFS
////////////////////////////////////////////////////////////////
3.7. Algoritmul de căutare a unui arbore de acoperire de lungime minimă (Minimum Spanning Tree)
3.7.1. Reprezentarea algoritmului
Să presupunem că am proiectat un circuit electronic și dorim sa ne asigurăm ca am folosit un numar minim de trasee, că nu avem trasee in plus intre pini care să ocupe loc sau care să ingreuneze proiectarea. Daca am avea un algoritm ce ne-ar ajuta sa determinam aceste trasee si sa le indepărtam, proiectarea ar fi mult mai simplă. În rezultat, am obtine un graf cu un număr minim de muchii necesare pentru conectarea tuturor vârfurilor. De exemplu, in Figura 6 a) avem cinci vârfuri cu un număr excesiv de muchii, in timp ce in Figura 6 b) avem aceleasi varfuri cu un numar minim de muchii necesare pentru a conecta toate cele cinci varfuri. Acesta reprezinta un arbore de acoperire de lungime minima (minimum spanning tree). Pot exista mai multi arbori de acoperire de lungime minima pentru acelasi set de varfuri. In Figura 6 b) sunt aratate muchiile AB, BC, CD si DE, dar, la fel de bine se poate construi un arbore de acoperire de lungime minima cu muchiile AC, CE, ED, si DB. Observam ca, intr-un arbore de acoperire de lungime minima numarul de muchii este intotdeauna mai mic cu o unitate fata de numarul de varfuri (E = V − 1) .
a)Numarul maxim de muchii posibile b) Numarul minim de muchii
Fig.6
Algoritmul pentru arborele de acoperire de lungime minima este aproape identic cu cel folosit pentru parcurgerea unui graf. Acesta se bazeaza pe parcurgerea in adancime (depth-first-search) sau parcurgerea in latime (breadth-first-search). In exemplul de mai jos vom folosi parcurgerea depth-first-search.Vom vedea ca executand parcurgerea in adancime si inregistrand muchiile pe care le-am parcurs, se va construi automat un arbore de acoperire de lungime minima. Singura diferenta intre metoda mst()(minimum spanning tree), pe care o vom explica mai jos si metoda dfs() reprezentata mai sus este ca in metoda mst() trebuie sa inregistram intr-un fel muchiile parcurse.
Prin urmare, putem sa construim un program MST.java asemanator cu programul DFS.java, in care vom avea o metoda noua mst() asemenea cu metoda dfs(). In metoda principala vom contrui graful din Figura 6 a) si vom apela metoda mst()pentru a determina un arbore de acoperire de lungime minima asemenea celui din Figură b) .
Diferenta intre metodele dfs() si mst() este ca in clauza else din ultima metoda sunt vizualizate doua varfuri in locul unui singur varf: varful curent si urmatorul varf nevizitat vecin al acestuia. Ele determina o muchie parcursa de algoritm pentru a ajunge la urmatorul varf si care va apartine unui arbore de acoperire de lungime minima.
In java metoda mst()va avea urmatoarea secventa de cod:
public void mst() // arbore de acoperire de lungime minima
//(parcurgerea in adancime)
{ // vom incepe cu primul varf,cu indicele 0
listaVarfuri[0].aFostVizitat = true; // il marcam
stiva.push(0); // inseram in stiva
while( !stiva.isEmpty() ) // cat timp stiva nu este goala,
{ // determinam varful stivei
int varfCurent = stiva.peek();
// obtinem urmatorul varf vecin nevizitat
int v = obtineVarfAdiacentNevizitat( varfCurent );
if(v == -1) // daca nu exista asemenea varf,
stiva.pop(); // extragem un varf din stiva
else // daca exista asemenea varf
{
listaVarfuri[v].aFostVizitat = true; // il marcam
stiva.push(v); // il inseram in stiva
displayVertex(varfCurent); //vizualizam muchia de la varful
// curent
displayVertex(v); // la varful nou gasit v
System.out.print(" ");
}
} // se incheie bucla while
// stiva este goala,am terminat
for(int i=0; i<nVarfuri; i++) // resetam flagurile
listaVarfuri[i].aFostVizitat = false;
} // se incheie metoda mst()-minimum spanning tree
In metoda principala a programului MST.java vom crea graful din Figura 6 a) si vom face apelul la metoda mst()in felul urmator:
public class MST {
public static void main(String[] args)
{
Graf unGraf = new Graf();
unGraf.addVertex('A'); // 0(varful de start)
unGraf.addVertex('B'); // 1
unGraf.addVertex('C'); // 2
unGraf.addVertex('D'); // 3
unGraf.addVertex('E'); // 4
unGraf.addEdge(0, 1); // AB
unGraf.addEdge(0, 2); // AC
unGraf.addEdge(0, 3); // AD
unGraf.addEdge(0, 4); // AE
unGraf.addEdge(1, 2); // BC
unGraf.addEdge(1, 3); // BD
unGraf.addEdge(1, 4); // BE
unGraf.addEdge(2, 3); // CD
unGraf.addEdge(2, 4); // CE
unGraf.addEdge(3, 4); // DE
System.out.print("Arborele de acoperire de lungime minima este: ");
unGraf.mst(); // apelam metoda mst()
System.out.println();
} //se incheie metoda principala
} // se incheie clasa MST
La executia programului MST.java vom obtine un arbore de acoperire de lungime minima care va contine doar patru muchii (Figura 6 b) ) din cele zece ale grafului initial. La iesire vom avea urmatorul rezultat:
Arborele de acoperire de lungime minima este: AB BC
3.7.2 Întroducerea datelor de la tastatură. Importarea claselor.
Vom modifica putin programul MST.java ca sa oferim utilizatorului posibilitatea sa aleaga varful de start pentru parcurgerea grafului. In rezultat, in dependenta de varful ales,vom vedea ca obtinem arbori partiali de acoperire de lungime minima diferiti. Pentru a realiza acest lucru vom costrui o metoda noua citireVarf() in clasa Graf cu ajutorul careia vom citi datele introduse de la tastatura. In timpul executiei acestei metode pot aparea erori, care lanseaza (throws) o exceptie de tip IOException.De aceea, in asemenea situatii, este necesar sa scriem clauza throws IOException dupa antetul metodelor main(),citireVarf() si mst().
În programele Java pot fi folosite direct toate clasele din pachetul java.lang, pachet care conține elementele de baza ale limbajului. Dacă un program folosește clase din alte pachete, atunci pachetele respective trebuie precizate explicit in program. Această precizare se face cu ajutorul instrucțiunii import.
Metoda citireVarf() pe care o folosim pentru introducerea datelor de la tastatură utilizează clase din pachetul java.io, pachet destinat operațiilor de intrare / ieșire (input / output). De aceea, în programele în care folosim această metodă trebuie să introducem instrucțiunea: import java.io.*;.Această instrucțiune permite să se preia toate clasele necesare din pachetul java.io .
Clasele apelate dintr-un program care nu aparțin pachetului java.lang se pot preciza și individual. Astfel, in metoda citireVarf() sunt folosite clasele InputStreamReader, BufferedReader și IOException. De aceea, programul in care sunt folosite aceste clase ar putea conține instrucțiunile:
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
Pare mai comod să precizăm intreg pachetul din care se preiau clasele, dar printr-o instrucțiune de forma import java.io.*; nu se pun in evidență clasele care sunt utilizate efectiv de program.
In continuare prezentam metoda citireVarf ( ) si metoda mst()cu urmatoarele modificari:
public String citireVarf() throws IOException {
String h;
//cream un flux pentru procesarea datelor
InputStreamReader f=new InputStreamReader(System.in);
BufferedReader g=new BufferedReader(f);
h=g.readLine(); // permite citirea unui flux linie cu linie
return h;
}
//––––––-
public void mst() throws IOException
//arbore de acoperire de lungime minima (parcurgerea in adancime)
{
String s;
int varfStart;
System.out.println("Alegeti varful de start intre 0 si 4 :");
// oferim utilizatorului posibilitatea sa aleaga varful de start
// intre cele cele posibile
s=citireVarf(); // apelam metoda citireVarf()
varfStart=Integer.valueOf(s).intValue(); //convertim valoarea lui
// s intr-un numar intreg
if (varfStart > 5)
System.out.print("Ati introdus un varf inexistent !" );
else {
System.out.print("Arborele de acoperire de lungime minima
este:");
listaVarfuri[varfStart].aFostVizitat = true; // il marcam
stiva.push(varfStart); // inseram in stiva
while( !stiva.isEmpty() ) // cat timp stiva nu este goala,
{ // determinam varful stivei
int varfCurent = stiva.peek();
// obtinem urmatorul varf vecin nevizitat
int v = obtineVarfAdiacentNevizitat( varfCurent );
if(v == -1) // daca nu exista asemenea varf,
stiva.pop(); // extragem un varf din stiva
else // daca exista asemenea varf
{
listaVarfuri[v].aFostVizitat = true; // il marcam
stiva.push(v); // il inseram in stiva
displayVertex(varfCurent);// vizualizam muchia de la
// varful curent
displayVertex(v); // la varful v
System.out.print(" ");
}
} // se incheie bucla while
// stiva este goala,am terminat
}
for(int i=0; i<nVarfuri; i++)
listaVarfuri[i].aFostVizitat = false;
} // se incheie metoda mst()-minimum spanning tree
Asa cum am vazut, executia programului incepe cu metoda main().Ca urmare, după lansarea programului in execuție, pe ecranul calculatorului apare textul:
Alegeti varful de start intre 0 si 4 :
și programul așteaptă să introducem un număr intreg. Programul trece in starea de așteptare in momentul execuției instrucțiunii h=g.readLine(); din metoda citireVarf(). Șirul tastat de noi este atribuit variabilei h. Acest șir este returnat in metoda mst() și se atribuie variabilei s. Valoarea variabilei s este convertită la un număr intreg in timpul execuției instrucțiunii varfStart=Integer.valueOf(s).intValue(); Numărul intreg obținut in urma conversiei este atribuit variabilei varfStart ce determina varful cu care vom incepe parcurgerea grafului.
Pentru a face posibil fluxul de date intre utilizator si computer am intrebuintat in metoda citireVarf() urmatoarele doua clasele din pachetul java.io :
BufferedReader clasa folosita pentru a introduce un buffer in procesul de citire a informatiilor, reducand astfel numarul de accese la dispozitivul ce reprezinta sursa originala de date.Este mult mai eficienta decat fluxul fara buffer si din acest motiv se recomanda folosirea acestei clasei ori de cate ori este posibil.
InputStreamReader aceasta clasa formeaza o punte de legatura intre fluxurile de caractere si fluxurile de octeti. Un flux InputStreamReader citeste octeti dintr-un flux InputStream convertindu-le in caractere folosind codificarea standard sau o codificare specificata de program.
Orice flux este un obiect al clasei ce implementeaza fluxul respectiv.Crearea unui flux se realizeaza asadar similar cu crearea obiectelor prin intructiunea new. Crearea unui flux primitiv de date care citeste informatii de la un dispozitiv extern are forma generala:
FluxPrimitiv numeFlux = new FluxPrimitiv (dispozitiv extern)
Fluxirile de procesare nu pot exista de sine statator, ci se suprapun pe un flux primitiv de citire a datelor. Din acest motiv constructorii claselor pentru fluxurile de procesare nu primesc ca argument un dispozitiv extern de memorare a datelor, ci o referinta la un flux primitiv responsabil cu citirea efectiva a datelor.
Capitolul 4-Interfețe grafice.Reprezentarea aplicației în limbajul java
4.1 Interfețe grafice. Pachetul java.awt
Acest pachet ne ofera o coletie de clase pentru crearea interfetelor grafice. Aceste clase permit lucrul cu ferestre, desenari, lucrul cu imagini si utilizarea componentelor ca butoane, liste, meniuri intr-un mod independent de platforma. Pachetul java.awt contine clasele AWT (Abstract Window Toolkit) GUI iar java.awt.image ne ofera niste facilitati in plus pentru lucrul cu imagini. Dupa cum numele sugereaza AWT este o abstractie. Clasele si functionalitatile oferite sunt aceleasi pentru orice implementare Java. Pentru a obtine Independenta de platforma AWT utilizeaza toolkituri interschimbabile care actioneaza cu sistemul de ferestre pe care se ruleaza aplicatia. De exemplu sa presupunem ca aplicatia noastra creaza un buton. Cand se ruleaza aplicatia, toolkitul specific platformei afiseaza butonul conform platformei. Daca aplicatia se ruleaza sub Windows vom obtine un buton de tip Windows, iar daca se ruleaza sub Unix se va afisaun buton de tip X Windows.
Utilizarea componentelor din acest pachet este relativ usoara, pe cand toolkiturile GUI sunt foarte complexe, dar aceasta este treaba celor care vor sa implementeze AWT-ul pe o noua platforma.
Realitatea este ca cele mai multe probleme despre Java se ridica la folosirea acestui pachet. Implementarea toolkiturilor pentru acest pachet contin cele mai multe buguri Java. Tocmai din aceasta cauza JavaSoft a introdus Swing care reprezinta noua generatie de componentele grafice si fac parte din JFC (Java Foundation Classes).
4.1.1Componente grafice
Componentele sunt elementele care se utilizeaza la crearea unei interfete grafice. Componentele sunt incluse in containere, care la randul lor sunt componente speciale. Anumite componente pot fi containere pentru alte componente: de exemplu o fereastra cu doua panouri. In acest caz fereastra este containerul, iar panelele sunt componentele continute. Daca adaugam elemente ca butoane, liste, etichete, casete text etc. in cele doua panouri atunci panoul va fi containerul iar elementele adaugate vor fi componentele.
Fig.1 Erarhia claselor pentru componente
Pentru simplitate impartim functionalitatea clasei Component in doua categorii: modul de afisare si comportament. Aceasta clasa contine metode si variabile care controleaza modul de afisare general al componentei. Aici sunt incluse atributele pentru vizibilitate, marime, pozitie si atribute ca culoarea si fontul. Clasa contine metode abstracte, care sunt implementate de subclasele pentru diferite tipuri de componente, si care determina imaginea grafica a componentei. Prin comportamentul componentei intelegem actiunile componentei la evenimentele primite de la utilizator. In momentul cand utilizatorul actiuneaza asupra unei componente (de exemplu apasa butonul mouse-ului) un fir de executie AWT informeaza toti receptorii (componentele care vor sa primeasca acest eveniment) despre evenimentul produs. De exemplu la apasarea unui buton se genereaza evenimentul ActionEvent. Cei care vor sa primeasca acest eveniment trebuie sa fie inregistrati, aceasta insemnand ca trebuie sa fie obiecte care respectainterfataActionListener.
Evenimentele sunt receptionate de catre obiecte de tip Listener, care la primirea evenimentului apeleaza o metoda de tratare a evenimetului. Obiectele care doresc sa primeasca evenimente trebuie sa implementeze interfetele pentru tipurile de evenimente pe care doresc sa le primeasca. De exemplu evenimentele de tip MouseEvents sunt primite de catre obiectele care respecta interfata MouseListener. Evenimentele reprezinta un mecanism de comunicare intre obiecte (nu numai obiecte grafice). Evenimentele sunt importante mai alesin cazul beanurilor Java.
Containerele rezolva tratarea evenimentelor pentru toate componentele continute. De obicei containerul se inregistrează la sursa de evenimente pentru a primi evenimentele necesare pentru o anumită componentă.
4.1.2. Peer
În sectiunea precedentă tocmai am descris functionarea acestor componente si evenimentele cu ajutorul carora aceste componente comunică intre ele. Asa sunt privite componentele de Java, dar nu si in lumea reală, adica pe platforma pe care vor fi efectiv afisate componentele. Lumea reală este caracterizata de o anumita arhitectura si de dispozitive fizice. La un anumit nivel obiectele noastre vor comunica cu obiecte care contin metode native pentru mediul in care componentele trebuie sa interacționeze. Pentru a tine această interactiune sub control Java utilizează interfețele peer. Această interfată peer face posibilă ca o componenta AWT Java sa utilizeze componenta corespunzatoare din lumea reală – obiectul peer din mediul nativ. Programele noastre vor lucra cu obiectele AWT Java, restul, partea grea este rezolvata de clasa Component.
Este important sa intelegem aceasta arhitectură deoarece astfel putem intelege cam ce putem realiza cu componentele. În figura precedentă se poate vedea ce se intampla la crearea unui buton. Toolkitul este de fapt o "fabrica de componente" native. Java utilizeaza aceasta fabrica pentru a separa funtionalitatea componentelor de modalitatea de implementare pe un sistem de afisare nativ. Obiectul Toolkit contine metode pentru crearea tuturor tipurilor de componente grafice. Daca nu ne place acest Toolkit oferit de mediul Java, putem sa scriem toolkitul nostru propriu.
Pachetul java.awt.peer contine o interfata pentru fiecare tip de componenta grafica. În acest pachet clasa de baza este ComponentPeer de la care se deriva aproape toate celelalte clase
4.1.3. Afișarea componentelor
Componetele pot fi rugate sa se autoafiseze. De exemplu daca fereastra care contine componentele este acoperita de o alta fereastra, in momentul revenirii la fereastra initiala aceasta trebuie reafisata cel putin partial. Cand AWT roaga componenta sa se autoafiseze, aceasta apeleaza metoda paint(). Metoda update() are aceasi functionalitae, dar aceasta prima data sterge suprafata componentei si dupa aceea apeleaz metoda paint(). Componentele nu vor apela direct update(), aceasta metoda fiind apelata de catre repaint(). Aceasta metoda roaga AWT sa programeze componenta in cauza pentru improspatare. Atat paint() cat si update() au un parametru de tip Graphics care reprezinta contextul grafic a componentei in cauza. Corespunde suprafetei ecran pe care componenta poate desena. Acesta este mecanismul utilizat de componente pentru autoafisare. Noi vom utiliza aceste metode doar in cazul containerelor speciale, adica in cazul obiectelor de tip Panel, Canvas si Applet.
4.1.4. Organizarea componentelor
Un organizator al componentelor este un obiect care stabileste marimea si pozitia componentelor in cadrul unui container. Fiecare container are un organizator implicit care in caz de necesitate poate fi modificat. Containerele principale sunt diferitele tipuri de ferestre, apleturi, panele etc. In cazul ferestrelor organizatorul implicit este un obiect de tip BorderLayout, iar in cazul apleturilor si ale panourilor unul de tip FlowLayout. Clasele principale organizatori de componente sunt: FlowLayot, GridLayout,CardLayout, BorderLayout si GridBagLayout.
FlowLayout organizeaza componentele de la stanga la dreapta si daca se umple randul curent atunci componetul urmator va fi plasat in randul urmator. Inaltimea randului este data de componenta de cea mai mare inaltime pe randul respectiv.
FlowLayout fLayout = new FlowLayout();
setLayout( fLayout );
Button butonOk = new Button("Ok");
add(butonOk);
Button butonCancel = new Button("Cancel");
add(butonCancel);
sau scris mai compact:
set Layou(new Flow La yout();
add(new Button("Ok"));
add( new Button("Cancel"));
Organizatorul centreaza componentele adaugate, dar acest tip de aliniere poate fi schimbata prin metoda setAlignment(). Metoda primeste ca parametru tipul alinierii. Tipurile de aliniere posibile sunt definite ca constante in clasa FlowLayout (LEFT, RIGHT, CENTER) si se utilizeaza in modul urmator:
FlowLayout fLayout = new FlowLayout();
fLayout.setAlignment(FlowLayout.LEFT)
setLayout( fLayout );
BorderLayout aranjeaza componentele in cinci regiuni: Nord, Sud, Vest, Est si Centru. La adaugarea componentelor utilizand acest organizator trebuie specificat pe langa componenta adaugata si regiunea la care se adauga. Atat Border Layout cat si CardLayout specificarea spatiului intre componente indicand numarul de pixeli pe orizontala respectiv pe verticala.
setLayout( new BorderLayout(), 10,6);
add( new Button("Unu"),"North");
add( new Button("Doi"),"East");
add( new Button("Trei"),"South");
add( new Button("Patru"),"West");
CardLayout (teanc de carti) se utilizeaza la organizarea componentelor care nu incap pe o anumita suprafata. Componentele sunt organizate pe aceste carti dintre care unul singurul se va vedea pe ecran. Visual Caffe introduce ferestrele cu mai multe pagini care pot inlocui acest organizator.
GridLayout imparte suprafata in randuri si coloane permitand aranjarea componentelor in aceste celule de dimensiuni egale. Componentele sunt plasate in celule incepand cu primul rand dupa aceea urmatorul rand si asa mai departe.
GridBagLayout este organizatorul cel mai avansat. Lucreaza asemanator ca GridLayout. Principala diferenta fata de acesta este ca in caul acestui organizator o componenta poate ocupa mai mult decat o singura celula.
4.2. Pachetele AWT și SWING
4.2.1. Notiuni generale
O interfată grafică se creaza de obicei cu sprijinul sitemului de operare (printr-o componenta numita server grafic).
Limbajul Java pune la dispozitia programatorului doua biblioteci pentru realizarea unei interfete grafice: java.awt si javax.swing. In figura sunt expuse clasele corespondente cu cele din awt:
In plus fata de pachetul standard awt, pachetul swing adauga noi clase care permit imbunatatirea interfetei realizate. In figura urmatoare sunt prezentate clasele noi introduse de catre swing:
4.2.2. Ferestre
Oricarei aplicatii grafice ii corespunde o fereastra principala (de tip FRAME) si una sau mai multe ferestre aditionale.In swing exista trei clase pentru gestionarea ferestrelor: Jframe, JWindow si JDialog.
Clasa JFrame permite crearea unei ferestre de aplicatie. Fereastra are o bara de titlu, o margine, butoane de minimizare, maximizare si inchidere (butoane "system").
Clasa JWindow permite crearea unei ferestre fara bara de titlu, meniu, butoane sistem etc.
Clasa JDialog permite crearea de ferestre de dialog. Ferestrele de dialog sunt dependente de ferestrele parinte de tip Frame. O fereastra de dialog poate fi modala (blocheaza aplicatia pana la inchiderea dialogului) sau nemodala (nu blocheaza).
Pentru a crea ferestre de afisare a unor mesaje se poate utiliza direct o functie statica, fara a mai crea explicit un obiect tip dialog:
JOptionPane.showMessageDialog(frame, “Mesajul meu.");
Pentru ferestre de dialog standard exista clase specializate: JFileChooser si JColorChooser. Acestea pot fi utilizate pentru a selecta un fisier sau a alege o culoare.
Crearea unei ferestre principale:
public static void main(String args[]) {
JFrame win = new JFrame(“Titlul ferestrei");
win.setSize(200, 200);
win.show();
}
Pentru a accesa continutul unei ferestre se va folosi functia getContentPanel():
Container c = win.getContentPane();
Pentru a obtine inchiderea automata a aplicatiei atunci cand se apasa butonul de Close, se va utiliza metoda:
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
Pentru a organiza elementele intr-o fereastra se vor utiliza panouri. Swing pune la dispozitie doua tipuri de panouri: JPanel (panou simplu) si JScrollPane (panou cu derulare).
4.3. Elemente de control (widgets)
4.3.1. Butoane
Butoanele deriva din clasa JButton. In costructor primesc textul afisat pe buton. Prin procedura setMnemonic se pot asocia taste de apelare rapida (shortcut).
Pentru a adauga un cuvant de comanda asociat butonului (cuvant ce va fi testat pentru efectuarea actiunii asociate) se foloseste metoda addActionCommand().
JButton buton = new JButton("I'm a Swing button!");
buton.setMnemonic('i');
buton.addActionCommand("butonulSwing");
JPanel panouButon = new JPanel();
panouButon.add(buton);
4.3.1.1. RadioButton
Butoanele radio sunt elemente de control care retin o anumita stare, la fel cu cele de marcaj. Deosebirea principala consta in faptul ca toate butoanele radio incluse in acelasi grup logic sunt mutual exclusive. Pentru gestionarea grupurilor de butoane radio se va folosi clasa ButtonGroup, respectiv metoda add() care adauga un buton la grup.
Si pentru butoanele radio se pot apela metodele setSelected(boolen marcat) pentru a stabili marcajul prin program, respectiv getSelected() pentru a afla starea marcajului.
// Create the radio buttons.
JRadioButton birdButton = new JRadioButton(“Pasare”);
birdButton.setMnemonic(KeyEvent.VK_B);
birdButton.setActionCommand(“Pasare”);
birdButton.setSelected(true);
JRadioButton catButton = new JRadioButton(“Pisica”);
catButton.setMnemonic(KeyEvent.VK_C);
catButton.setActionCommand(“Pisica”);
…
// Group the radio buttons.
ButtonGroup group = new ButtonGroup();
group.add(birdButton);
group.add(catButton);
…
// Put the radio buttons in a column in a panel
JPanel radioPanel = new JPanel();
radioPanel.setLayout(new GridLayout(0, 1));
radioPanel.add(birdButton);
radioPanel.add(catButton);
4.3.1.2. ListBox
ListBox-urile afiseaza liste de optiuni. Ele se compun dintr-un element care se ocupa de vizualizare (derivat din clasa JList), respectiv dintr-un element care se ocupa cu gestionarea continutului (derivat din ListModel).
Interfata ListModel pune la dispozitie o metoda addElement() care permite adaugarea unei noi optiuni in lista.
Constructorul clasei JList primeste un obiect de tip ListModel pe care il va afisa pe ecran. Pentru a avea la dispozitie bare de derulare asociate listei, aceasta va trebui inclusa intr-un element de tip JScrollPane (un panou derulant).
Aditional listelor simple se pot defini si liste cu derulare (de tip ComboBox). Acestea afiseaza in mod obisnuit o singura optiune din lista iar pentru a accesa restul optinulor lista trebuie derulata de la un buton special. Listele derulante nu trebuie adaugate intr-un JScrollPane.
ListModel listModel = new DefaultListModel();
listModel.addElement(“Linie1");
…
JList list = new JList(listModel);
list.setSelectionMode(ListSelectionModel.SINGLE_SELECTION);
list.setSelectedIndex(0);
JScrollPane listScrollPane = new JScrollPane(list);
–––
String[] culori = { "Alb", "Negru", "Rosu", "Verde", "Albastru" };
JComboBox listaCulori = new JComboBox(culori);
listaCulori.setSelectedIndex(1); // selecteaza elementul 2 (Negru)
listaCulori.setEditable(true);
4.4. Reprezentarea aplicației
Interfața utilizator grafica (engl.: GUI – Graphical User Interface) permite utilizatorului sa comunice cu aplicația, folosind in acest scop obiecte grafice de pe ecran: ferestre, butoane, casete de validare, meniuri etc. Acționarea asupra acestora se face folosind tastatura sau dispozitive de intrare speciale, dintre care cel mai raspandit este mouse-ul.
În JDK exista pachete de clase care permit realizarea de interfețe grafice, unul dintre acestea fiind java.awt. Initialele AWT provin de la Abstract Window Toolkit – set de dezvoltare de ferestre abstracte. Acest set permite realizarea de interfețe grafice care nu depind de platforma pe care ruleaza aplicația. El ofera programatorului clase de componente organizate sub forma unei ierarhii care are ca radacina clasa Component.
Folosirea interfețelor grafice implica si o abordare specială in programare, numita programare orientată pe evenimente (engl: Event Oriented Programming) sau programare ghidata de evenimente (engl.: Event Driven Programming). În aceasta conceptie, obiectele din program pot fi surse de evenimente sau consumatoare ("ascultatoare") de evenimente (eng.: Event Listeners). Evenimentele inseși sunt obiecte (instante ale unor clase de evenimente ) generate de surse si interceptate de consumatori. Clasele consumatoare de evenimente sunt cele care conțin metodele prin care aplicația reactionează la evenimentele respective.
Se disting evenimente de nivel inferior (cele generate de diferite componente) si evenimente abstracte (care reprezinta diferite evenimente conceptuale, independente de componenta care le-a generat). Fiecarei clase de evenimente ii corespunde o interfata pe care trebuie sa o implementeze clasele concepute de programator, care interceptepteaza si trateaza evenimentele respective. Interfetele sunt, de asemenea organizate intr-o ierarhie, similara celei a claselor. Pentru unele interfete s-au realizat si clase-prototip care le implementeaza, numite adaptoare. Clasele de evenimente, interfetele si adaptoarele se gasesc in pachetul java.awt.event.
Clasa Graphics
In pachetul java.awt este definita clasa abstracta Graphics, care este clasa de baza a tuturor contextelor grafice care permit trasarea de desene pe suprafata componentelor grafice realizate pe diverse dispozitive fizice.
Un obiect din clasa Graphics incapsuleaza informatia de stare a contextului grafic la care se refera si anume:
– obiectul din clasa Component (sau dintr-o subclasa a acesteia) pe care se deseneaza;
– o translatie a originii sistemului de coordonate; toate coordonatele din desen sunt raportate la aceasta origine;
– decupajul curent (dreptunghiul in interiorul caruia se traseaza desenul);
– culoarea curenta; – fontul curent;
– operatia logica pe pixeli curenta (XOR sau paint);
– alternarea curenta de culori pentru operatia pe pixeli XOR.
Clasa interfata_grafica face desenarea interfetei grafice:
public class interfata_grafica
{
Font f = new Font("", Font.PLAIN, 30);
Ascultadecomenzi trateaza=new Ascultadecomenzi();
Frame frame=new Frame("Aplicatie");
MenuBar mb=new MenuBar();
Menu m1=new Menu("Comenzi");
menuiesire m1B1=new menuiesire("Iesire");
butoniesire b3 = new butoniesire("Iesire");
butonulmeu b4 = new butonulmeu("Calculeaza",this);
setbuton actiune_b5 = new setbuton("Set");
butonopriere b6= new butonopriere("Oprire cautare");
JTextField status = new JTextField("", 5);
JLabel untext =new JLabel("Status");
JLabel untext1 =new JLabel("Plecare: ");
JLabel untext2 =new JLabel("Destinatie: ");
JLabel actiune_untext1 =new JLabel("Plecare: ");
JLabel actiune_untext2 =new JLabel("Destinatie: ");
JLabel actiune_untext3 =new JLabel("Actiuni: ");
JLabel actiune_untext4 =new JLabel("Valoare: ");
JTextField actiune_val = new JTextField(4);
JRadioButton optiunea1 = new JRadioButton("Stergere");
JRadioButton optiunea2 = new JRadioButton("Setare lungime");
ButtonGroup group = new ButtonGroup();
JPanel panel=new JPanel();
Retea retea;
final int x=10,y=20;
Choice plecare = new Choice();
Choice destinatie = new Choice();
Choice actiune_plecare = new Choice();
Choice actiune_destinatie = new Choice();
Thread a;
TextArea rezultate = new TextArea();
interfata_grafica()
{
Clasa principal.java contine metoda main. Aici se fac 2 thread-uri, unul pentru interfata grafica si unul care deseneaza odata la 100 ms graful curent, in functie de configuratia retelei:
public class principal {
static interfata_grafica a;
static class Fir_grafica extends Thread
{
Fir_grafica()
{
a = new interfata_grafica ();
}
public void run()
{
yield();
}
}
static class Desenare_drum extends Thread
{
int i,j,x1,x2,y1,y2,m,n;
Font f1 = new Font("", Font.PLAIN, 20);
Font f2 = new Font("", Font.PLAIN, 18);
Desenare_drum()
{
}
public void run()
{
try
{
Thread.sleep(200);
yield();
Pentru modelarea retelei s-au folosit clasele retea, nod, linie.
Clasa nod.java are campuri datele despre respectivul nod (nume, coordonate, legaturi cu alte nod-uri) si metodele care permit sa se faca/stearga legatura cu alte noduri.
public class Nod {
String nume;
Linie legatura[] = new Linie[15];
int nr_legaturi=0;
int x,y;
interfata_grafica interfata;
Nod(String nume, int x, int y, interfata_grafica interfata)
{
this.nume=nume;
this.x=x;
this.y=y;
this.interfata=interfata;
}
public void setLegatura(Nod destinatie, int lungime)
{
legatura[nr_legaturi]=new Linie(this,destinatie,lungime, interfata);
nr_legaturi++;
destinatie.setLegaturaReverse(this, lungime); //seteaza si distanta inversa
}
public void setLegaturaReverse(Nod destinatie, int lungime)
{
legatura[nr_legaturi]=new Linie(this,destinatie,lungime, interfata);
nr_legaturi++;
}
Clasa retea.java se face configurarea retelei folosind figura:
Fig.4
public class Retea {
interfata_grafica interfata;
Nod nod[] = new Nod[20];
int lungime=16;
Retea(interfata_grafica interfata)
{
nod[0]=;
nod[1]=bucuresti;
nod[2]=tulcea;
nod[3]=;
nod[4]=;
nod[5]=;
nod[6]=;
nod[7]=;
nod[8]=piatra_neamt;
nod[9]=cluj;
nod[10]=;
nod[11]=;
nod[12]=baia_mare;
nod[13]=suceava;
nod[14]=orsova;
nod[15]=;
}
} this.interfata=interfata;
Clasa linie.java stabilește sursa, destinația și lungimea drumului:
public class Linie {
int lungime;
Nod sursa, destinatie;
interfata_grafica interfata;
Linie(Nod sursa, Nod destinatie, int lungime, interfata_grafica ref)
{
this.sursa=sursa;
this.destinatie=destinatie;
this.lungime=lungime;
Clasa calculare.java face calcularea drumului. Fiecare instanta catre aceasta clasa ruleaza pentru un thread separat pentru a nu se intepa interfata grafica cand se face calculul drumului. Algoritmul de cautare este unul recursiv, se merge din nod in nod si la fiecare nod se cauta vecinii. Se stocheaza intr-un vector nod-urile vizitate pentru a nu se merge de două ori prin acelasi nod (fig.5).
public class calculare extends Thread
{
interfata_grafica interfata;
Nod drum[] = new Nod[50];
int gasite=0;
Nod vector[][] = new Nod[400][50];
int vector_lungime[] = new int[400];
int indexi[] = new int[400];
boolean gasit=true;
int temp;
Nod p; Nod d;
calculare(interfata_grafica interfata, Nod p, Nod d)
{
this.interfata=interfata;
this.p=p;
this.d=d;
}
public void cauta_in_vecini(Nod nod, Nod plecare, Nod destinatie, int lungime, int pas)
{
Fig.5 Calcularea drumului minim
Concluzii
Principalele probleme tratate în lucrare:
Utilizarea structurilor de date și al algoritmilor în programarea la calculator
Grafuri, arbori – traversări, parcurgeri
Crearea unei interfețe grafice
Calcularea unui drum minim
Această lucrare reprezintă ceea ce avem nevoie să știm “după”ce am învățat un limbaj de programare.
Scopul esențial al lucrării a fost de a face toate subiectele expuse, ușor de înțeles.
Lucrarea prezentată este ilustrată cu ajutorul unor programe demonstrative reprezentate pas cu pas ,cu “imagini în mișcare”, principiile de bază ale funcționării structurilor de date.
BIBLIOGRAFIE
1. Athanasiu Irina, Costinescu B., Drăgoi O.A., Popovici F.I. Limbajul Java. O perspectivă pragmatică. Editura Agora, Tg.Mureș
2. Fraizer C., Bond J. Java API. Pachetele API java.applet si java awt. Editura Teora, București, 1998. .3. Rotariu E. Limbajul Java. Editura Agora, Tg.Mureș, 1996.
3. Norton P., Stanek W. Ghid de programare in Java. Editura Teora, București, 1997
4. Prodan A., Prodan M. Mediul Java pentru Internet. Editura Promedia Plus, , 1997.
5. Rotariu E. Limbajul Java. Editura Agora, Tg.Mureș, 1996.
SURSE INTERNET
http://thor.info.uaic.ro/~acf/java/curs/6/interf_grafica.
htmlhttp://developer.java.sun.com/developer/onlineTraining/
http://forum.portal.edu.ro/index.php?showtopic=53322
http://csam.univ-ovidius.ro/~tudrescu/cursuri/constructii/Laborator%208.pd
http://java.sun.com/docs/books/tutorial/,
http://developer.java.sun.com/developer/onlineTraining/
BIBLIOGRAFIE
1. Athanasiu Irina, Costinescu B., Drăgoi O.A., Popovici F.I. Limbajul Java. O perspectivă pragmatică. Editura Agora, Tg.Mureș
2. Fraizer C., Bond J. Java API. Pachetele API java.applet si java awt. Editura Teora, București, 1998. .3. Rotariu E. Limbajul Java. Editura Agora, Tg.Mureș, 1996.
3. Norton P., Stanek W. Ghid de programare in Java. Editura Teora, București, 1997
4. Prodan A., Prodan M. Mediul Java pentru Internet. Editura Promedia Plus, , 1997.
5. Rotariu E. Limbajul Java. Editura Agora, Tg.Mureș, 1996.
SURSE INTERNET
http://thor.info.uaic.ro/~acf/java/curs/6/interf_grafica.
htmlhttp://developer.java.sun.com/developer/onlineTraining/
http://forum.portal.edu.ro/index.php?showtopic=53322
http://csam.univ-ovidius.ro/~tudrescu/cursuri/constructii/Laborator%208.pd
http://java.sun.com/docs/books/tutorial/,
http://developer.java.sun.com/developer/onlineTraining/
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Structuri de Date Dinamice In Limbajul Java (ID: 150655)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.