Definition:

Graphen sind Mengen mit Beziehungen zwischen ihren Elementen. Sie bestehen aus einer Menge von Elementen (Punkten, auch Knoten genannt), die über gerichtete oder ungerichtete Linien (Kanten) mit einander verbunden sind.

Mit Hilfe von Graphen lassen sich sehr allgemeine Probleme formulieren, für deren Lösung man keinen schnellen Algorithmus angeben kann.

Beispiele: Netzwerkaufbau, Verkehrsleitsysteme, Fahrroutenplanung, Optimierungsprobleme

Begriffe:

allgemeiner Graph: Anschauliches Modell zur Beschreibung von Objekten, die untereinander in gewisser Beziehung stehen. Ein Graph besteht aus einer Menge von Punkten (Knoten) und einer Menge von Linien (Kanten), die diese Punkte verbinden.

gerichteter Graph: Ein Graph dessen Kanten auf Nachbarknoten mit einem Pfeil gerichtet sind.

ungerichteter Graph: Ein Graph, dessen Kanten zu Nachbarknoten keine Pfeile haben, also keine Richtung aufweisen.

Eulerweg: Alle Kanten werden genau einmal besucht. Knoten mehrfach besucht werden.

Eulerzyklus: geschlossener Eulerweg, Startknoten = Endknoten. Sind der Grad der Kanten an einem Knoten ungrade gibt es keinen Eulerzyklus.

Hamiltonweg: Jeder Knoten wird genau einmal besucht.

Hamiltonzyklus: Endknoten muss Nachbar des Startknoten sein. Nachbarn sind über eine Kante verbunden.

Breitendurchlauf

Verfahren zum Durchlaufen eines Graphen. Jeder Knoten wird genau einmal besucht. Man besucht dabei zu erst alle Nachbarn eines Knotens und geht erst dann weiter zum nächsten Knoten.

Beim Breitendurchlauf werden die Anwärterknoten in einer Schlange verwaltet.

Das Verfahren entspricht der Levelorder-Traversierung.

Tiefendurchlauf

Verfahren zum Durchlaufen eines Graphen. Jeder Knoten wird genau einmal besucht. Man besucht hier zu erst einen noch nicht besuchten Nachbarknoten. Sind nicht alle Knoten so zu erreichen, geht man solange zurück, bis wieder ein Nachbarknoten besucht werden kann. Dieses Verfahren wird Backtracking genannt.

Beim Tiefendurchlauf werden die Anwärterknoten in einem Stack verwaltet oder rekursiv bearbeitet.

Das Verfahren entspricht der Preorder-Traversierung.