Extras din curs
Grafuri orientate/neorientat
Creare graf din matrice/listă de adiacenţă
Adăugarea/ştergerea unui nod
Adăugarea/ştergerea unui arc
Ştergerea grafului
Afişarea conţinutului grafului (vârfuri/arce) – parcurgerea în adâncime/lăţime
Căutare nod/arc
Gradul unui nod (de intrare/ieşire); gradul grafului
Drum simplu; buclă; lungimea drumului
Graf ponderat/ neponderat – drumul minim
Structura unui graf. Definirea vârfurilor şi a listelor de legături corespunzătoare acestora
Vârf
Parcurgerea în adâncime
1, 2, 4, 3, 6, 5
se construieste o stiva pentru varfurile vizitate
vectorul ce evidentiaza daca un varf e vizitat sau nu este initializat (nici un nod nu e vizitat la inceput)
se introduce in coada primul varf al grafului, care devine vizitat, fiind prelucrat (afisat de exemplu)
cat timp coada nu este goala se realizeaza urmatoarele
- se extrage din coada un varf
- daca acest varf are descendenti nevizitati, acestia se vor introduce in coada, devenind vizitati si fiind prelucrati (afisati de ex)
Vizitează toate vârfurile legate de primul vârf, determină arborele expandat al grafului, având ca radăcină primul vârf din graf
Determină un drum între două vârfuri, un ciclu în graf; parcurge toate legăturile; merge spre cel mai depărtat vârf
Parcurgerea în lăţime
1, 2, 4, 5, 3, 6
se construieste o coada pentru varfurile vizitate
vectorul ce evidentiaza daca un varf e vizitat sau nu este initializat (nici un nod nu e vizitat la inceput)
se introduce in stiva primul varf al grafului, care devine vizitat, fiind prelucrat (afisat de exemplu)
cat timp stiva nu este goala se realizeaza urmatoarele
- se extrage din stiva un varf
- daca acest varf are descendenti nevizitati, acestia se vor introduce in stiva, devenind vizitati si fiind prelucrati (afisati de ex)
Vizitează toate vârfurile legate de primul vârf, determină arborele expandat al grafului, având ca radăcină primul vârf din graf
Determină un drum între două vârfuri şi un ciclu în graf; parcurge vârfurile considerând fiecare nivel în întregime
Conținut arhivă zip
- curs5_Grafuri.cpp
- Structuri de Date si Algoritmi Curs 5.ppt
Alții au mai descărcat și
INTRODUCERE IN TEORIA GRAFURILOR Exista situatii când oameni ce lucreaza în diverse domenii ajung la reprezentarea unor cazuri concrete prin...
Comertul electronic reprezinta multitudinea proceselor software si comerciale necesare proceselor business sa functioneze numai, sau în primul...
Capitolul 1 Introducere Lucrarea prezinta sabloanele de proiectare , ce sunt acestea si cum ne ajuta ele in rezolvarea problemelor de proiectare...
GRAFURI NEORIENTATE NOTIUNI INTRODUCTIVE NOTIUNI DE BAZA DEFINITIE: Se numeste graf neorientat o pereche ordonata de multimi(X,U), X fiind o...
Biblioteca de Sabloane Standard (STL) asigura o abstractizare standardizata a datelor prin intermediul containerelor si o abstractizare procedurala...
1. Clase derivate. Prin mostenire, atributele unei clase de baza sunt transmise unor clase derivate. Derivarea permite definirea unor clase noi,...
Clase pentru miniaplicatii Miniaplicatiile constituie extensii ale unei clase deja existente java.applet.Applet. Structura clasei unui applet...
Te-ar putea interesa și
I. COMPARTIMENTUL ANALITIC 1.1. Caracteristica generală a întreprinderii SA "IUGINTERTRANS" Această întreprindere a fost înfiinţată în acea...
Dintre toate domeniile în care un robot, sau un calculator, poate fi comparat cu performanţele umane, percepţia (şi componenta sa cea mai...
8. Arbori 8.1. Arbori generalizaţi 8.1.1. Definiţii În definirea noţiunii de arbore se porneşte de la noţiunea de vector. Fie V o mulţime având...
Retelele de interconectare sunt de 2 tipuri: a)retele statice la care conexiunile intre noduri sunt fixe si punct la punct-transferul informatiei...
CURS 1. - STRUCTURI DE DATE Scop : prezentarea celor mai importante structuri de date ce pot fi utilizate pentru modelarea datelor din aplicatii....
Curs 1 Structuri de date Structurile de date erau definite în limbajul C drept organizarea datelor primare. În limbajul C++, acestea reprezinta o...
De ce SDA? Structuri de date : metode de organizare a unei mari cantitati de informatie Analiza algoritmilor : estimarea timpului de executie si...
Curs 1 - Introducere. Structuri de date - noţiuni generale Introducere Tipuri de bază. Pointeri. Tablouri. Paradigme de programare Programare...