Grafové algoritmy, Libor Polák

Grafové algoritmy

Libor Polák

Jan Šerák

implementace

algoritmus

nejkratší cesty

• 1 Úvodní slovo autora
  2 Intro
  2.1 Reprezentace grafu v počítači
  2.2 Složitost algoritmu a její klasifikace
  3 Základní grafové algoritmy
  3.1 Prohledávání do šířky
  3.2 Prohledávaní do hloubky
  3.2.1 Algoritmus prohledávání do hloubky . . . .
  3.2.2 Klasifikace hran grafu po proběhnutí DFS .
  3.2.3 Topologické třídění
  3.3 Silně souvislé komponenty grafu
  4 Užitečné datové struktury
  4.1 Binární halda
  4.2 Prioritní fronta
  4.3 Prioritní fronta implementovaná binární haldou . .
  4.4 Binomiální halda
  4.5 Prioritní fronta implementovaná binomiální haldou
  4.6 Analýza složitosti
  4.7 Fibonaeeiho haldy
  4.8 Zásobník
  4.9 Datové struktury pro disjunktní množiny
  4.9.1 První implementace
  4.9.2 Druhá implementace
  5 Problém minimální kostry
  5.1 Obecný algoritmus
  5.2 Kruskalův algoritmus
  5.3 Prinúv algoritmus
  5.4 Složitost algoritmu
  5.4.1 Složitost Kruskalova algoritmu
  5.4.2 Složitost Primová algoritmu
  6 Nejkratší cesty
  6.1 Nejkratší cesty z daného vrcholu
  6.2 Relaxace
  6.3 Stromy nejkratších cest
  6.4 Dijkstrúv algoritmus
  6.5 Bellman - Fordu v algoritmus
  6.6 Nejkratší cesty z jediného vrcholu v acyklických grafech
  6.7 Nejkratší cesty all pairs
  6.7.1 Floyd - Warshallúv algoritmus
  6.8 Tranzitivní uzávěr orientovaného grafu
  7 Maximální toky v sítích