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 soluții de comerț electronic

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

Șabloane de proiectare a interfețelor utilizator pentru aplicații 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...

AutoCad

APERTURE - controleazã mãrimea cursorului selector, caracteristic modului object snap. ARC - traseazã un arc de cerc de orice dimensiune. A -...

Biblioteca de Șabloane Standard

Biblioteca de Sabloane Standard (STL) asigura o abstractizare standardizata a datelor prin intermediul containerelor si o abstractizare procedurala...

Clase Derivate

1. Clase derivate. Prin mostenire, atributele unei clase de baza sunt transmise unor clase derivate. Derivarea permite definirea unor clase noi,...

Clase în Java

Clase pentru miniaplicatii Miniaplicatiile constituie extensii ale unei clase deja existente java.applet.Applet. Structura clasei unui applet...

Te-ar putea interesa și

Întreprinderea SA Iugintertrans 2006

I. COMPARTIMENTUL ANALITIC 1.1. Caracteristica generală a întreprinderii SA "IUGINTERTRANS" Această întreprindere a fost înfiinţată în acea...

Generalități despre sistemele de vedere artificială

Dintre toate domeniile în care un robot, sau un calculator, poate fi comparat cu performanţele umane, percepţia (şi componenta sa cea mai...

Programare paralelă în sisteme distrbuite

Retelele de interconectare sunt de 2 tipuri: a)retele statice la care conexiunile intre noduri sunt fixe si punct la punct-transferul informatiei...

Structuri de Date

CURS 1. - STRUCTURI DE DATE Scop : prezentarea celor mai importante structuri de date ce pot fi utilizate pentru modelarea datelor din aplicatii....

Structuri de Date și Algoritmi

Curs 1 Structuri de date Structurile de date erau definite în limbajul C drept organizarea datelor primare. În limbajul C++, acestea reprezinta o...

Structuri de Date și Algoritmi

De ce SDA? Structuri de date : metode de organizare a unei mari cantitati de informatie Analiza algoritmilor : estimarea timpului de executie si...

Structuri de Date și Algoritmi - Curs 1

Curs 1 - Introducere. Structuri de date - noţiuni generale Introducere Tipuri de bază. Pointeri. Tablouri. Paradigme de programare Programare...

Structuri de Date și Algoritmi - Curs 2

Curs 2 – Liste simplu înlănţuite Structura unei liste. Definirea elementului listei Element Listă Curs 2 – Liste simplu înlănţuite typedef int...

Ai nevoie de altceva?