Kurs:Algorithmen und Datenstrukturen/Kapitel 8

Dieses Kapitel gehoert zum Kurs Algorithmen und Datenstrukturen des Fachbereichs Informatik.

Einige Graphenalgorithmen

Kurze Beschreibung dessen, was in diesem Kapitel alles vorkommen wird

Was ist ein Graph?

• Definition von Knoten und Kanten
• Darstellung

Minimum Spanning Tree

• Definition vom Minimum Spanning Tree
• Herleitung vom Algorithmus von Kruskal
• Die passende Datenstruktur

Kuerzester Pfad zwischen zwei Knoten

• Definition des Problems
• Herleitung vom Algorithmus von Dijkstra
• Fibonacci-Heap als passende Datenstruktur
• Herleitung des Floydalgorithmus
• Herleitung des Warshallalgorithmus