Graphentheorie

Ein Graph ist eine Datenstruktur aus der Graphentheorie, die aus einer Menge von Punkten, zwischen denen Linien (Verbindungen) verlaufen, besteht.

Grundbegriffe der Graphentheorie

Graph
Datenstruktur mit einer Menge von Knoten, die über Kanten verbunden sind
Knoten (node)
ein Punkt im Graphen
Kante (edge)
Verbindung zwischen zwei Knoten
gerichtete Kante (directed edge)
Verbindung zwischen zwei Knoten, die nur in eine Richtung besteht
ungerichtete Kante
Verbindung zwischen zwei Knoten, die in beide Richtungen besteht
gerichteter Graph (directed graph)
Graph mit mindestens einer gerichteten Kante
ungerichteter Graph
Graph ohne gerichtete Kanten, d.h. nur ungerichtete Kanten
gewichtete Kante
Kante, die ein Gewicht zugewiesen bekommen hat
gewichteter Graph
Graph mit mindestens einer gewichteten Kante
Richtung/Orientierung
eine Kante kann in eine Richtung oder in beide Richtung weisen.
Gewicht (weight)
Bewertung einer Kante
Schlinge
Kante, die einen Knoten mit sich selbst verbindet
zyklischer Graph
Graph, in dem Knoten in Kreisstruktur miteinander verbunden sind
Eulerweg
Weg über Kanten durch den Graphen von einem Anfangsknoten bis zu einem Endknoten, bei dem alle Knoten genau einmal berührt werden.
Multigraph
Graph, in dem ein Knotenpaar durch mehrere Kanten verbunden werden kann
Adjazenzmatrix
Repräsentation eines Nicht-Multigraphen

Graphalgorithmen

Ein minimaler Spannbaum (Minimum Spanning Tree [MST]) ist ein Baum mit allen Knoten des Graphen, der die minimale Verbindung zwischen den Knoten angibt.

Djikstra
berechnet die kürzeste Entfernung zwischen zwei Knoten.

  1. Weise allen Knoten die beiden Eigenschaften „Distanz“ und „Vorgänger“ zu. Initialisiere die Distanz im Startknoten mit 0 und in allen anderen Knoten mit ∞.
  2. Solange es noch unbesuchte Knoten gibt, wähle darunter denjenigen mit minimaler Distanz aus und
    1. Markiere den Knoten.
    2. Berechne für alle noch unbesuchten Nachbarknoten die Summe des jeweiligen Kantengewichtes und der Distanz im aktuellen Knoten.
    3. Ist dieser Wert für einen Knoten kleiner als die dort gespeicherte Distanz, aktualisiere sie und setze den aktuellen Knoten als Vorgänger.
Kruskal
berechnet den minimalen Spannbaum eines Graphen.

  1. Führe so oft wie möglich aus: Wähle unter den noch nicht ausgewählten Kanten des Graphen die kürzeste Kante, die mit den schon gewählten Kanten keinen Kreis bildet.
Prim
berechnet den minimalen Spannbaum eines Graphen.

  1. Wähle einen beliebigen Knoten als Startgraph T (dieser wird zum minimalen Spannbaum erweitert).
  2. Solange T noch nicht alle Knoten enthält:
    1. Wähle eine Kante e minimalen Gewichts aus, die einen noch nicht in T enthaltenen Knoten v mit T verbindet.
    2. Füge e und v dem Graphen T hinzu.
Tiefensuche
besucht rekursiv alle Knoten, die über Kanten erreichbar sind (kann zum Beispiel die Anzahl der Knoten zählen).

  1. besuche ersten vom Anfangsknoten aus erreichbaren Knoten und markiere diesen
  2. besuche den ersten von diesem Knoten aus erreichbaren und markiere diesen, und so weiter
  3. Wenn kein Knoten mehr erreichbar ist, kehre zum letzten Punkt zurück, an dem es noch weitere Kanten gab.
Breitensuche
durchläuft alle Knoten (kann zum Beispiel den kürzesten Weg zwischen zwei Knoten berechnen).

  1. Bestimme einen Startknoten und speichere ihn in einer Warteschlange ab.
  2. Entnimm einen Knoten vom Beginn der Warteschlange und markiere ihn.
    1. Falls das gesuchte Element gefunden wurde, brich die Suche ab und liefere „gefunden“ zurück.
    2. Anderenfalls hänge alle bisher unmarkierten Nachfolger dieses Knotens, die sich noch nicht in der Warteschlange befinden, ans Ende der Warteschlange an.
  3. Wenn die Warteschlange leer ist, dann wurde jeder Knoten bereits untersucht. Beende die Suche und liefere „nicht gefunden“ zurück.
  4. Wiederhole Schritt 2.
Zyklensuche
durchsucht den Graphen nach einem Zyklus, d. h. überprüft ob ein kreisförmiger Weg durch den Graphen möglich ist. Eine Implementierung gibt entweder als boolschen Wert zurück, ob ein Zyklus gefunden wurde, oder eine Liste der im Zyklus enthaltenen Knoten.

Die Algorithmen von Djikstra, Prim und Kruskal sind Beispiele für Greedy-Algorithmen, d. h. jeder Schritt führt weiter zur Lösung des Problems. Es gibt somit kein Backtracking. Der Aufwand ist fast linear.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.