Document, comentariu, eseu, bacalaureat, liceu si facultate
Top documenteAdmitereTesteUtileContact
      
    


 


Ultimele referate adaugate

Adauga referat - poti sa ne ajuti cu un referat?

Politica de confidentialitate



Ultimele referate descarcare de pe site
  CREDITUL IPOTECAR PENTRU INVESTITII IMOBILIARE (economie)
  Comertul cu amanuntul (economie)
  IDENTIFICAREA CRIMINALISTICA (drept)
  Mecanismul motor, Biela, organe mobile proiect (diverse)
  O scrisoare pierduta (romana)
  O scrisoare pierduta (romana)
  Ion DRUTA (romana)
  COMPORTAMENT PROSOCIAL-COMPORTAMENT ANTISOCIAL (psihologie)
  COMPORTAMENT PROSOCIAL-COMPORTAMENT ANTISOCIAL (psihologie)
  Starea civila (geografie)
 

Ultimele referate cautate in site
   domnisoara hus
   legume
    istoria unui galban
   metanol
   recapitulare
   profitul
   caract
   comentariu liric
   radiolocatia
   praslea cel voinic si merele da aur
 
despre:
 
Parcurgerea grafurilor in adancime
Colt dreapta
Vizite: ? Nota: ? Ce reprezinta? Intrebari si raspunsuri
 

Foarte multi algoritmi de prelucrare a grafurilor necesita examinarea tuturor nodurilor unui graf.Pentru aceasta este necesara definirea unei strategii de traversare a grafului.Se poate vorbi in principal de doua tehnici de traversare: n6e20eo
- in adancime (Depth First)
- in latime (Breadth First)
In explicarea modului de functionare a primei variante se foloseste un sir de intregi, VIZITAT, de lungime n cu ajutorul caruia se marcheaza nodurile deja “vizitate” pentru a evita trecerea de mai multe ori prin acelasi nod.Cu alte cuvinte VIZITATaji = 1 daca nodul j a fost deja atins si VIZITATaji = 0 in caz contrar.Vom spune despre un nod i ca a fost explorat daca are toate nodurile adiacente vizitate.
Procedura recursiva care asigura parcurgerea unui graf in adancime incepand cu un anumit varf i:
Procedura Parcurgere_in_adancime(i) pentru toate varfurile k adiacente cu varful i executa daca varful k este neparcurs atunci se parcurge varful k apel parcurgere_in_adancime(k)

Iesirea din recursivitate se produce in momentul in care nu se mai gasesc varfuri neparcurse adiacente cu varfurile parcurse deja. Este posibil ca dupa un apel al procedurii incepand cu un anumit varf i sa ramana in graf varfuri neparcurse.In aceasta situatie apelul procedurii se repeta pentru un alt varf initial (dintre varfurile neparcurse) pana la parcurgerea tuturor nodurilor grafului. Programul apelant trebuie sa asigure parcurgerea varfului utilizat in apel.Conditiile interne care apar in problemele particulare de backtracking pot impune o parcurgere integrala sau numai partiala a grafului.Procedura backtracking(i) este pentru cazul parcurgerii integrale a unui graf in adancime:



Procedura Backtracking(i) pentru toate varfurile k adiacente cu varful i executa daca varful k este neparcurs si sunt indeplinite conditiile de continuare atunci se parcurge varful k se utilizeaza varful k in solutie daca s-a ajuns la o solutie se afiseaza apel Backtracking(k)

Folosind aceasta tehnica de traversare ne propunem sa raspundem la intrebarea:
Fiind dat un graf neorientat G=(V,E), este acesta un graf conex?
Conform acestei metode explorarea unui nod este suspendata ori de cate ori un nou varf este vizitat.Pentru graful G daca pornim din varful 1, vizitarea nodurilor se va face in ordinea: 1,2,4,8,5,6,3,7.

Urmatoarea functie returneaza true daca graful este conex si false in caz contrar folosind tehnica parcurgerii in adancime:
Function Conex: boolean;

Procedura adancime(s) Aparcurge graful in adancimeS
VIZITATasi:=1; pentru fiecare nod w adiacent cu s executa daca VIZITATawi = 0 atunci apel adancime(w) sfarsit daca; sfarsit pentru; sfarsit procedura;

pentru toate nodurile w executa
VIZITATawi:=0; sfarsit pentru; apel adancime(1);
Conex:=true; pentru toate nodurile w executa daca VIZITATawi = 0 atunci conex:=false; sfarsit daca; sfarsit pentru;
Sfarsit functie;


Colt dreapta
Creeaza cont
Comentarii:

Nu ai gasit ce cautai? Crezi ca ceva ne lipseste? Lasa-ti comentariul si incercam sa te ajutam.
Esti satisfacut de calitarea acestui document, eseu, cometariu? Apreciem aprecierile voastre.

Nume (obligatoriu):

Email (obligatoriu, nu va fi publicat):

Site URL (optional):


Comentariile tale: (NO HTML)


Noteaza documentul:
In prezent fisierul este notat cu: ? (media unui numar de ? de note primite).

2345678910

 
Copyright© 2005 - 2024 | Trimite document | Harta site | Adauga in favorite
Colt dreapta