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:
Descarca toata lectia
Parcurgerea grafurilor în adâncime
- Prima Pagina
- Informatica
- Parcurgerea grafurilor în adâncime
Bac 2020
- ORDIN PRIVIND ORGANIZAREA ȘI DESFĂȘURAREA EXAMENULUI DE BACALAUREAT 2020
- Programa de Bacalaureat 2020 la toate disciplinele
- Modele de subiecte Bacalaureat 2020 la toate materiile
- Calendarul examenului de Bacalaureat 2020
- Lista disciplinelor la care se sustine examenul de bacalaureat
- Continuturi Bacalaureat Limba si Literatura Romana
- SUBIECTE EXTRASE SESIUNEA IUNIE IULIE BAC 2019 la toate materiile
- Întrebări și Răspunsuri în legătură cu examenul de Bacalaureat 2020
- TESTE ONLINE PENTRU PREGATIREA EXAMENULUI DE BACALAUREAT
- 75 exemple de Bilete Limba Romana Oral Proba A
- Lectii Limba Romana pentru examenul de Bacalaureat
- Lectii pregatitoare BIOLOGIE
- GHID BACALAUREAT ISTORIE
- Teorie Logică, argumentare și comunicare pentru Bac
- Teorie Fizica pentru Bac
- 100 de Variante Rezolvate la Matematica
- eBacalaureat pe Facebook
Materii
Noutati
- Bacalaureat 2020 Modele de subiecte si Barem Biologie vegetala si animala (Biologie)
- Bacalaureat 2020 Modele de subiecte la Anatomie si fiziologie umana, genetica si ecologie umana (Biologie)
- Structura si compozitia substantelor organice (Chimie)
- Chimie Organica: Acizi carboxilici (Chimie)
- Chimie Organica: Alcooli (Chimie)
- Bacalaureat 2019: Programa Chimie Anorganica (Chimie)
- Bacalaureat 2019: Programa Chimie Organica (Chimie)
- Rezolvari Anatomie si fiziologie umana genetica si ecologie umana Bacalaureat 2019 Varianta 4 Sesiunea iunie iulie (Biologie)
- Ghid Bacalaureat Fiziologie si anatomie umana - clasa a XI-a Genetica si ecologie umana - clasa a XII-a (Biologie)
- Subiecte si Barem Bacalaureat 2019 Anatomie si fiziologie umana, genetica si ecologie umana sesiunea august-septembrie (Biologie)
Please enable / Bitte aktiviere JavaScript!
Veuillez activer / Por favor activa el Javascript![ ? ]
Veuillez activer / Por favor activa el Javascript![ ? ]