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)