Kurs:Algorithmen und Datenstrukturen/Kapitel 8

Aus Wikiversity

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

Inhaltsverzeichnis 1 Einige Graphenalgorithmen 2 Was ist ein Graph? 3 Minimum Spanning Tree 4 Kuerzester Pfad zwischen zwei Knoten

[Bearbeiten] Einige Graphenalgorithmen

Kurze Beschreibung dessen, was in diesem Kapitel alles vorkommen wird

[Bearbeiten] Was ist ein Graph?

• Definition von Knoten und Kanten
• Darstellung

[Bearbeiten] Minimum Spanning Tree

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

[Bearbeiten] Kuerzester Pfad zwischen zwei Knoten

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