Algorithmen lernen

Kapitel 7. Diagramme: Nur verbinden!

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

In diesem Kapitel lernst du:

• Der abstrakte Datentyp Stack.

• Der indizierte Min-Prioritäts-Warteschlangen-Datentyp, der der letzte Datentyp in diesem Buch ist.

• Wie man einen Graphen mit Knoten und Kanten modelliert. In einem gerichteten Graphen haben die Kanten eine Ausrichtung. In einem gewichteten Graphen haben die Kanten einen zugehörigen numerischen Wert.

• Wie Depth First Search einen Stapel verwendet, um die Suche in einem Graphen zu organisieren.

• Wie Breadth First Search eine Warteschlange benutzt, um einen Graphen zu durchsuchen. Wenn es einen Pfad zwischen einem Quellknoten und einem Zielknoten gibt, gibt Breadth First Search den kürzesten Pfad zurück, der existiert.

• Wie erkennt man, ob ein gerichteter Graph einen Zyklus enthält: eine Folge von Kanten, die von einem bestimmten Knoten ausgehen und mit diesem enden.

• Wie man Topologische Sortierung in einem gerichteten Graphen verwendet, um eine lineare Reihenfolge der Knoten zu erstellen, die mit allen Abhängigkeiten im gerichteten Graphen kompatibel ist.

• Wie man den kürzesten kumulierten Pfad in einem gewichteten Graphen von einem Knoten zu allen anderen Knoten bestimmt.

• Wie man den kürzesten akkumulierten Pfad in einem gewichteten Graphen zwischen zwei beliebigen Knotenpunkten bestimmt.

Diagramme speichern effizient nützliche Informationen ...