9 Graphenalgorithmen

• 9.1 Definitionen
• 9.2 Implementation von Graphen
  • Implementation durch Adjazenzmatrix
  • Implementation durch Adjazenzlisten
• 9.3 Shortest Path
• 9.4 All Shortest Paths
• 9.5 Minimum Spanning Tree
  • Pipeline-Heap-Algorithmus
• 9.6 Zusammenhangskomponente
  • 1. Möglichkeit: Berechne transitive Hülle.
  • 2. Möglichkeit: Tiefensuche
  • 3. Möglichkeit: Verschmelzen von Superknoten
  • Aufwand für Phase 1:
  • Aufwand für Phase 2:
  • Aufwand für Phase 3: