Structuri de Date și Algoritmi Curs 5

Curs
8/10 (1 vot)
Domeniu: Calculatoare
Conține 2 fișiere: ppt, cpp
Pagini : 13 în total
Mărime: 48.45KB (arhivat)
Cost: Gratis

Extras din document

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

Elemente de Teoria Grafurilor

INTRODUCERE IN TEORIA GRAFURILOR Exista situatii când oameni ce lucreaza în diverse domenii ajung la reprezentarea unor cazuri concrete prin...

Proiectarea unei Solutii de Comert Electronic

Comertul electronic reprezinta multitudinea proceselor software si comerciale necesare proceselor business sa functioneze numai, sau în primul...

Sabloane de Proiectare a Interfetelor Utilizator pentru Aplicatii Web

Capitolul 1 Introducere Lucrarea prezinta sabloanele de proiectare , ce sunt acestea si cum ne ajuta ele in rezolvarea problemelor de proiectare...

Grafuri Neorientate

GRAFURI NEORIENTATE NOTIUNI INTRODUCTIVE NOTIUNI DE BAZA DEFINITIE: Se numeste graf neorientat o pereche ordonata de multimi(X,U), X fiind o...

Algoritmi și Structuri de Date

Introducere: Semiotica se ocupã cu studiul semnelor în natura si în societate. Semnul nu este o calitate în sine a unui obiect, ci o functie pe...

Arbori Partiali de Cost Minim

I. Arbori Fie G un graf orientat. G este un arbore cu radacina r, daca exista in G un varf r din care oricare alt varf poate fi ajuns printr-un...

Algoritmi de Rutare

Algoritmii de rutare pot fi diferenţiaţi după obiectivul particular dorit, impactul asupra reţelei şi resurselor ruterului, metricile folosite....

Modelarea Aplicațiilor Web cu UML 2

Modelarea aplicaţiilor web cu UML 2. Studii de caz Vă prezentăm în continuare (vezi tabelul 1) o metodologie de modelare a unei aplicaţii web cu...

Ai nevoie de altceva?