graf - sdd - curs pentru facultate

Upload: mihai-botofei

Post on 05-Jul-2018

245 views

Category:

Documents


0 download

TRANSCRIPT

  • 8/16/2019 Graf - SDD - curs pentru facultate

    1/14

    STRUCTURI DE DATE

    Grafuri

  • 8/16/2019 Graf - SDD - curs pentru facultate

    2/14

    http://www.acs.ase.rohtt ://www.itcsolutions.eu

    GRAFURI

    Utilizare structura de tip graf:

    • Informaţii care au multiple legături între ele;

    • Parcurgerea completă a elementelorstructurii;

    • Localizarea unui element din structură; 

    2

  • 8/16/2019 Graf - SDD - curs pentru facultate

    3/14

    http://www.acs.ase.rohtt ://www.itcsolutions.eu

    Structura de tip graf:

    • Relaţie ierarhică intre nodul părinte şi nodulfiu;

    • Relatie mai puţin restrictivă: un nod are mai

    mulţi succesori dar şi mai mulţi predecesori;• Colecţie de date: două mulţimi:

    - Mulţimea nodurilor grafului;

    - Mulţimea arcelor dintre două noduri vecine.

    3

    GRAFURI

  • 8/16/2019 Graf - SDD - curs pentru facultate

    4/14

    http://www.acs.ase.rohtt ://www.itcsolutions.eu

    Criterii de clasificare a grafurilor:

    • Direcţia arcelor : grafuri neorientate (arcenedirecţionate), grafuri orientate (există

    sens între două noduri);

    • Greutatea arcelor : grafuri cu greutate (arce

    cu valoare numerică), grafuri fără greutate 

    (arcele nu au asociate valori numerice);

    4

    GRAFURI

  • 8/16/2019 Graf - SDD - curs pentru facultate

    5/14

    http://www.acs.ase.rohtt ://www.itcsolutions.eu

    Criterii de clasificare a grafurilor (continuare):

    • Existenţa arcelor : grafuri conectate (nu

    există nici un nod izolat), grafuri

    neconectate (există cel puţin un nod izolat).

    5

    GRAFURI

  • 8/16/2019 Graf - SDD - curs pentru facultate

    6/14

    http://www.acs.ase.rohtt ://www.itcsolutions.eu

    Terminologie:

    • Noduri adiacente: noduri conectate prin arc;

    • Drum: secventa de varfuri care conecteaza

    doua noduri;

    • Graf complet: fiecare varf este conectat

    direct cu toate celelalte varfuri.

    6

    GRAFURI

  • 8/16/2019 Graf - SDD - curs pentru facultate

    7/14

    http://www.acs.ase.rohtt ://www.itcsolutions.eu

    Metode de reprezentare a grafului prin

    structuri de date:

    • Matrice de adiacenţă;

    • Liste înlănţuite;

    • Vector de pointeri la liste simple sau dublu

     înlănţuite de noduri adiacente;

    7

    GRAFURI

  • 8/16/2019 Graf - SDD - curs pentru facultate

    8/14

    http://www.acs.ase.rohtt ://www.itcsolutions.eu

    Metode de reprezentare a grafului prin structuri de

    date:

    • Listă simplu sau dublu înlănţuită de pointeri la

    liste simple sau dublu înlănţuite de noduri

    adiacente;

    • Vector de pointeri la liste simple sau dublu

     înlănţuite de arce;

    • Lista de arce: greutate/informatie arc, capete arc.

    8

    GRAFURI

  • 8/16/2019 Graf - SDD - curs pentru facultate

    9/14

    http://www.acs.ase.rohtt ://www.itcsolutions.eu

    Reprezentarea prin matrice de adiacenţă – 

    eficienta:• Se cunoaşte numărul nodurilor ;

    • Se cunoaşte numărul mediu al arcelor   – 

    grad de umplere al matricei;• Patratica;

    • Reprezentare arce: valoarea 1 (graf fără

    greutate), greutate arc (graf cu greutate).

    9

    GRAFURI

  • 8/16/2019 Graf - SDD - curs pentru facultate

    10/14

    http://www.acs.ase.rohtt ://www.itcsolutions.eu

    Reprezentarea prin lista de adiacenţă:

    • Nu se cunoaşte numărul de noduri;

    • Construirea dinamică a structurii de tip graf;

    • Reţea de liste înlănţuite;

    • Mulţime de noduri, mulţime de arce 

    10

    GRAFURI

  • 8/16/2019 Graf - SDD - curs pentru facultate

    11/14

    http://www.acs.ase.rohtt ://www.itcsolutions.eu

    Traversarea unui graf:

    • Oricare nod al grafului este un posibil punct

    de start al traversării;

    • Nu este unică;

    • Evitarea revenirii într -un nod vizitat:

    asocierea unei etichete;

    11

    GRAFURI

  • 8/16/2019 Graf - SDD - curs pentru facultate

    12/14

    http://www.acs.ase.rohtt ://www.itcsolutions.eu

    Metode de traversare:

    • Traversarea în adâncime: depth-first

    traversal;

    • Traversarea în lăţime: breadth-first traversal.

    12

    GRAFURI

  • 8/16/2019 Graf - SDD - curs pentru facultate

    13/14

    http://www.acs.ase.rohtt ://www.itcsolutions.eu

    Traversare în adâncime a unui graf :

    • Algoritm tip backtracking;• Algoritm similar cu traversarea în preordine

    a unui arbore;

    • Utilizare structuri de ajutor: vector, lista,stiva

    13

    GRAFURI

    GRAFURI

  • 8/16/2019 Graf - SDD - curs pentru facultate

    14/14

    http://www.acs.ase.rohtt ://www itcsolutions eu

    Traversare în lăţime a unui graf :

    • Analog procesului de traversare în inordinea unui arbore;

    • Folosirea unei structuri de tip coada pentrunodurile de verificat.

    14

    GRAFURI