- ( 11 )
- Astronomie ( 113 )
- Biologie ( 571 )
- Chimie ( 266 )
- Diverse ( 201 )
- Drept ( 3 )
- Economie ( 109 )
- Engleza ( 243 )
- Filozofie ( 110 )
- Fizica ( 377 )
- Franceza ( 115 )
- Geografie ( 611 )
- Germana ( 44 )
- Informatica ( 386 )
- Istorie ( 819 )
- Marketing ( 26 )
- Matematica ( 275 )
- Medicina ( 6 )
- Muzica ( 11 )
- Psihologie ( 233 )
- Religie ( 52 )
- Romana ( 1526 )
Referat Traversarea grafurilor in adancime
Categorie: Referate InformaticaReferat downloadat de: 175 ori. |
 
|
Descriere referat: |
| Foarte mul?i algoritmi de prelucrare a grafurilor necesit? examinarea tuturor nodurilor unui graf.Pentru aceasta este necesar? definirea unei strategii de traversare a grafului.Se poate vorbi în principal de dou? tehnici de traversare: - în adâncime (Depth First) - în l??ime (Breadth First) În explicarea modului de func?ionare a primei variante se folose?te un ?ir de întregi, VIZITAT, de lungime n cu ajutorul c?ruia se marcheaz? nodurile deja “vizitate” pentru a evita trecerea de mai multe ori prin acela?i nod.Cu alte cuvinte VIZITAT[j] = 1 dac? nodul j a fost deja atins ?i VIZITAT[j] = 0 în caz contrar.Vom spune despre un nod i c? a fost explorat dac? are toate nodurile adiacente vizitate. Procedura recursiv? care asigur? parcurgerea unui graf în adâncime începând cu un anumit vârf i: Procedura Parcurgere_în_adâncime(i) pentru toate vârfurile k adiacente cu vârful i execut? daca vârful k este neparcurs atunci se parcurge vârful k apel parcurgere_în_adâncime(k) Ie?irea din recursivitate se produce în momentul în care nu se mai g?sesc vârfuri neparcurse adiacente cu vârfurile parcurse deja. Este posibil ca dup? un apel al procedurii incepând cu un anumit vârf i s? r?mân? în graf vârfuri neparcurse.În aceast? situa?ie apelul procedurii se repet? pentru un alt vârf ini?ial (dintre vârfurile neparcurse) pân? la parcurgerea tuturor nodurilor grafului. Programul apelant trebuie s? asigure parcurgerea vârfului utilizat în apel.Condi?iile interne care apar în problemele particulare de backtracking pot impune o parcurgere integral? sau numai par?ial? a grafului.Procedura backtracking(i) este pentru cazul parcurgerii integrale a unui graf în adâncime: Procedura Backtracking(i) pentru toate vârfurile k adiacente cu vârful i execut? daca vârful k este neparcurs ?i sunt îndeplinite condi?iile de continuare atunci se parcurge vârful k se utilizeaza vârful k în solu?ie dac? s-a ajuns la o solu?ie se afi?eaz? apel Backtracking(k) Folosind aceast? tehnic? de traversare ne propunem s? r?spundem la întrebarea: Fiind dat un graf neorientat G=(V,E), este acesta un graf conex? Conform acestei metode explorarea unui nod este suspendat? ori de câte ori un nou vârf este vizitat.Pentru graful G daca pornim din vârful 1, vizitarea nodurilor se va face în ordinea: 1,2,4,8,5,6,3,7 |
Alte referate din materia: Informatica
| Nr. | Nume referat | Hits |
| 1 | TkkvMlabSupl | 10 |
| 2 | qzpymq@dxuzju.com | 111 |
| 3 | email@gmail.com | 224 |
| 4 | pfuqxd@exjswl.com | 249 |
| 5 | ncqcez@hdtnnq.com | 218 |
| 6 | Hard | 677 |
| 7 | ISTORIA INTERNET-ULUI | 745 |
| 8 | Impera | 423 |
| 9 | Info Doc | 479 |
| 10 | Info-TIRON | 432 |
| 11 | Informatica - Grafica pentru web | 892 |
| 12 | Informatica - Introducere in HTML | 662 |
| 13 | Initiere in pc | 657 |
| 14 | Instalarea sistemului de operare Windows | 552 |
| 15 | Internetul ca sursa de comunicare | 535 |
| 16 | Istoria Internetului | 568 |
| 17 | Istoria calculatorului | 491 |
| 18 | Istoria metodelor de proiectare | 327 |
| 19 | Java visavis de C++ | 364 |
| 20 | Java vizavi de C | 299 |
| 21 | LIMBAJUL DE PROGRAMARE PASCAL - Programul defineste tipul salariat, o inregistrare cu variante, valorile citite fiind salvate in fisierul salariat.dat | 0 |
| 22 | Limbajul C | 373 |
| 23 | Lista vinuri prg | 284 |
| 24 | Lotus software | 260 |
| 25 | Lumea internetului | 367 |
Trimite un referat !
Referatul tau ii poate ajuta si pe ceilalti! Ajuta-ti colegii!Ai un referat facut de tine si consideri ca este bun si original ? Trimite-ti lucrarea ta si poti castiga premii, ajutandu-ti colegii sa ia note bune!
Trimite un referat!
Cere un
referat !
Ai nevoie de un referat bun si nu il gasesti ?referat !
Noi te ajutam sa iti faci referatul de care ai nevoie. Da-ne detalii despre lucrarea pe care trebuie sa o redactezi si noi vom scotoci pentru tine!
Cere un referat!
