Graph

Ein Graph ist eine Ansammlung von Knoten ("Ecken") und Verbindungen ("Kanten") dazwischen. Bei vielen Algorithmen wird diese Datenstruktur benötigt.

init: Leere den Graph
insertKnot: Gib (Ecke) zum Graph
insertEdge: Gib die Kante (Ecke) zu (Ecke) zum Graph
connectKnot: Verbinde (Ecke) mit (Ecke) im Graph
isConnectedWith: Mit welchen Ecken ist (Ecke) im Graph verbunden?
isStart: Existiert zur (Ecke) keine Ecke, von der eine Kante zu ihr führt?
removeKnot: Entferne (Ecke) aus dem Graph

dadurch werden natürlich auch alle Kanten, die von dieser Ecke ausgehen und zu ihr hinführen, entfernt.

removeEdge: Entferne die Kante (Ecke) zu (Ecke) aus dem Graph

Der Graph in Scratch

Ein Graph ist kein Wörterbuch! Aber es ist eine Darstellung mit zwei Listen möglich. Die Ecken sind durchnummeriert. Es werden in den Listen nicht die Ecken, sondern nur die Kanten gespeichert. In der ersten Liste werden die Startpunkte der Kanten abgelegt, in der zweiten Liste (an der Position mit dem gleichen Index) die Endpunkte. Für Ecken ohne Kanten gibt es in der zweiten Liste keinen Eintrag.

Es gib gerichtete und ungerichtete Graphen. In gerichteten Graphen kann man sich die Kanten wie Pfeile vorstellen: Es gibt eine Startecke und eine Zielecke. Um einen ungerichteten Graphen abzubilden, speichert man jede Kante auch in Gegenrichtung. Das heißt "insertEdge" legt nicht nur z.B. (3,5) ab, sondern auch (5,3).

Will man einen gewichteten Graphen darstellen (das Gewicht ist etwa die Entfernung zwischen zwei Städten oder der Durchmesser von Rohren), dann ergänzt man eine dritte Liste, in der die Gewichte der jeweiligen Kante gespeichert werden.