Algorithmen in einer Kurzfassung, 2.

Kapitel 6. Graph-Algorithmen

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

Graphen sind grundlegende Strukturen, die komplex strukturierte Informationen darstellen. Die Bilder in Abbildung 6-1 sind alle Beispielgraphen.

In diesem Kapitel untersuchen wir gängige Methoden zur Darstellung von Graphen und damit verbundene Algorithmen, die häufig vorkommen. Ein Graph besteht aus einer Reihe von Elementen, den so genannten Knoten, und Beziehungen zwischen diesen Elementen, den so genannten Kanten. In diesem Kapitel verwenden wir diese Begriffe einheitlich; in anderen Beschreibungen könnten die Begriffe "Knoten" und "Verknüpfung" für dieselben Informationen stehen. Wir betrachten nur einfache Graphen, die (a) Selbstkanten von einem Scheitelpunkt zu sich selbst und (b) mehrere Kanten zwischen demselben Paar von Scheitelpunkten vermeiden.

Angesichts der Struktur, die durch die Kanten in einem Graphen definiert ist, lassen sich viele Probleme als Wege von einem Ausgangs- zu einem Zielknoten im Graphen beschreiben, die mit Hilfe der vorhandenen Kanten im Graphen konstruiert werden. Manchmal hat eine Kante einen numerischen Wert, der als Gewicht bezeichnet wird; manchmal ist eine Kante mit einer bestimmten Ausrichtung versehen (wie eine Einbahnstraße). Beim Single-Source Shortest Path Algorithmus erhält man einen bestimmten Knoten s und wird gebeten, den kürzesten Weg (durch die Summe der Kantengewichte) ...