Note de curs, clasele 11-12, 19 octombrie 2012
From Algopedia
Jump to navigationJump to search
Rămase din urmă
- demonstrație că metoda lui Kruskal chiar găsește un arbore parțial minim (metoda tăieturii)
Parcurgerea în lățime
- implementare cu o coadă
- conceptual: noduri albe (nedescoperite), gri (în coadă), negre (complet parcurse)
- demonstrație că chiar calculează distanța minimă δ(s, v) pentru orice nod v
Parcurgerea în adâncime
- implementarea recursivă
- conceptual: noduri albe, gri, negre
- timpi de intrare / ieșire din noduri, d[u], f[u]
- intervale și posibilități de ordonare pentru d[u], f[u], d[v], f[v]
- vizualizarea intervalelor pe un fel de grafic Gantt
- tipuri de muchii: tree, back, forward, cross
- tipuri pentru grafuri neorientate: tree, back
- dag: nu are back edges
- sortare topologică
- simplă parcurgere, ordonare descrescătoare după f[u]
- demonstrație că merge, exemplu grafic
Probleme
- este adevărat? dacă u ~~> v și d[u] < d[v], atunci v este urmaș al lui u în DFS.
- este adevărat? dacă u ~~> v atunci d[v] <= f[u]
- este adevărat? dacă u are muchii care intră și muchii care ies, atunci u nu poate fi singur în arborele lui DFS.
- găsirea unui ciclu într-un graf, O(n)