Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen ::

Graphen und Graphenalgorithmen

Warum der ICE im Dörfchen Oberau hält - aber nicht in Koblenz

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Grundlagen der Graphen

Grundlagen der Graphen

• Der ungerichtete Graph der voherigen Abbildung zeigt einen vereinfachten Ausschnitt aus dem deutschen Bahnnetz (ICE Trassen).
• An den Kanten sind die Entfernungen in Kilometern angegeben.
  • Es handelt sich also um einen gewichteten Graphen.
  • Der Graph ist zusammenhängend, aber nicht vollständig und nicht eben (also eben Deutsche Bahn)

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Vertiefende Literatur

Vertiefende Literatur

[1] H. Ernst, J. Schmidt, and G. Beneken, Grundkurs Informatik. Springer, 2023.

• Auch die bereits behandelten Bäume sind ein Spezialfall von Graphen. Tatsächlich handelt es sich bei Graphen um eine der wichtigsten Datenstrukturen in der Programmierung, die in vielen Anwendungsgebieten zum Einsatz kommen.

• Ein Graph besteht grob aus mit Kanten verbundenen Knoten.

• Unterschiede gibt es in der Art der Kanten sowie in der Realisierung der Kanten und Knoten in einer Datenstruktur, die sich auf die Effizienz der unterschiedlichen Graphenfunktionen auswirkt.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Grundlagen der Graphen

Grundlagen der Graphen

Das Königsberger Brückenproblem. Oben eine Skizze der Innenstadt von Königsberg im 18. Jahrhundert. Unten eine Repräsentation als Graph, wobei die Stadtteile als Knoten und die Brücken als Kanten dargestellt sind

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Taxonomie der Graphen

Taxonomie der Graphen

Arten von Graphen

Graphen werden als eine durch Kanten verbundene Menge von Knoten definiert. Wir werden insbesondere die folgenden drei Klassen von Graphen näher betrachten:

1. Bei ungerichteten Graphen wird angegeben, welcher Knoten mit welchem verbunden ist, ohne dass eine Richtung vorgegeben wird. Ist allgemein von Graphen ohne nähere Einschränkung die Rede, sind in der Regel ungerichtete Graphen gemeint. Typische Anwendungen von ungerichteten Graphen sind die Modellierung von Straßenverbindungen (ohne Einbahnstraßen!), der Nachbarschaft von Gegenständen oder eines Telefonnetzes.

2. Gerichtete Graphen unterscheiden sich von den ungerichteten dadurch, dass Kanten eine Richtung haben. Auch können zwei Knoten nun durch zwei Kanten (d.h. in jeder Richtung eine) verbunden sein.

Typische Beispiele sind Modelle von Förderanlagen, der Kontrollfluss in Programmen oder auch Petri-Netze (Abluafdiagramme mit Tokens).

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Taxonomie der Graphen

Arten von Graphen

3. Ein wichtiger Spezialfall sind gerichtete azyklische Graphen, die oft kurz als DAG für englisch directed acyclic graph bezeichnet werden. In einem DAG gibt es keinen geschlossenen Rundweg entlang der gerichteten Kanten.

Beispiele sind die Vorfahrenbeziehung in Stammbäumen und die Vererbung in Programmiersprachen. Ein DAG ist natürlich als Datenstruktur ein normaler gerichteter Graph; relevant ist hier allerdings der möglichst effiziente Test auf Zyklenfreiheit.

• Die Bestandteile von Graphen können mit zusätzlichen Attributen versehen werden, etwa der Länge einer Kante bei der Modellierung eines Straßennetzes. Derartige Graphen werden als gewichtete Graphen bezeichnet.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Ungerichtete Graphen

Ungerichtete Graphen

• Diese Definition lässt also keine Schleifen, d.h. Kanten von einem Knoten zu sich selbst, und auch keine mehrfachen Kanten zwischen zwei Knoten (Parallelkanten) zu. Möglich ist auch eine erweiterte Definition, in der jedes e ∊ E eine ein- oder zweielementige Teilmenge darstellt.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Ungerichtete Graphen

Ungerichtete Graphen

Als Beispiel für diese Formalisierung von Graphen betrachten wir den Graph G_u:

$${G}_{{u}}={\left({V}_{{u}},{E}_{{u}}\right)}\\ {V}_{{u}}={\left\lbrace{1},{2},{3},{4},{5},{6}\right\rbrace}\\ {E}_{{u}}={\left\lbrace{\left\lbrace{1},{2}\right\rbrace},{\left\lbrace{1},{3}\right\rbrace},{\left\lbrace{1},{4}\right\rbrace},{\left\lbrace{2},{6}\right\rbrace},{\left\lbrace{4},{6}\right\rbrace},{\left\lbrace{3},{6}\right\rbrace},{\left\lbrace{5},{6}\right\rbrace},{\left\lbrace{3},{4}\right\rbrace},{\left\lbrace{3},{5}\right\rbrace}\right\rbrace}$$

Biespiel Ungerichteter Graph mit obiger Knoten- und Kantenmenge

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Gerichtete Graphen

Gerichtete Graphen

Allerdings ist jedes e ∊ E nun ein Tupel (a, b) mit a, b ∊ V. Diese Definition lässt Schleifen (a, a) zu.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Gerichtete Graphen

Gerichtete Graphen

Als Beispiel für diese Definition gerichteter Graphen betrachten wir den Graph Gg aus Abbildung 16–2:

$${G}_{{g}}={\left({V}_{{g}},{E}_{{g}}\right)}\\ {V}_{{g}}={\left\lbrace{1},{2},{3},{4},{5},{6}\right\rbrace}\\ {E}_{{g}}={\left\lbrace{\left({1},{2}\right)},{\left({1},{3}\right)},{\left({3},{1}\right)},{\left({4},{1}\right)},{\left({3},{4}\right)},{\left({3},{6}\right)},{\left({5},{3}\right)},{\left({5},{5}\right)},{\left({6},{5}\right)},{\left({6},{2}\right)},{\left({6},{4}\right)}\right\rbrace}$$

Biespiel Gerichteter Graph mit obiger Knoten- und Kantenmenge

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Gerichtete Graphen

Gerichtete Graphen

• Zustandsautomaten kommen in fast allen Programmen vor. Beispiele sind auch Lexer und Parser.
  • Der Lexer zerlegt einen zusammenhängenden Text in einzelne Tokens (Symbole). Dazu benötigt er eine Sprachstruktur mit Mustern, z.B. ein Muster für die Addition add := expression + expression, und expression spaltet weiter auf (Baumstrukturen!!), z.B. expression := Number | Variable | expression
  • Der Parser setzt nach einem bestimmten Ablauf die Tokens zu Graphenstrukturen zusammen.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Gerichtete Graphen

Gerichtete Graphen

function parse(text) {
  state = {
    instring  : 0,
    incomment : 0,
    last      : '',
    buffer    : ''
  }
  while (next=nexttoken) {
    if (state.incomment) {
      if (next!=NL) continue;
      else state.incomment=0;
    } else if (state.instring==1) {
      if (next!='"') { state.buffer+=next; continue }
    }
    switch (next) {
      case '"': 
        state.instring++; if (state.instring==2) { processString(state.buffer); state.instring=0 }  
        break;
      case '/': if (state.last=='/') state.incomment++; break;
    }
    state.last=next
  }
}

Der programmatische Ablauf eines endlichen Zustandsautomaten kann durch eine Zustandsübergangstabelle und als Graph repräsentiert (abstrahiert) werden. Hier sind die Zustände aber im Programmkode "verborgen"

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Gewichtete Graphen

Gewichtete Graphen

Gewichtete Graphen besitzen zusätzlich zu den bisherigen Graphenbestandteilen noch Kantengewichte. Kantengewichte sind den Kanten zugeordnete Gewichtswerte, etwa natürliche Zahlen oder int- oder real-Werte. Ein gewichteter Graph kann nun für natürliche Zahlen als Kantengewichte durch G = (V, E, γ) mit

$$γ:{E}→{\mathbb{{N}}}$$

definiert werden.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Gewichtete Graphen

Gewichtete Graphen

Beispiel eines gewichteten, gerichteten Graphen. Natürlich gibt es auch gewichtete, ungerichtete Graphen, etwa um Entfernungen in Verkehrsnetzen zu modellieren.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Gewichtete Graphen

Gewichtete Graphen

Beispiel: Kommunikationsnetzwerk wie das Internet. Die Kanten werden mit Geschwindigkeits- und Durchsatzmetriken annotiert und ermöglichen die Fundung einer optimal schnellen Verbidnung.

Beispiel für ein Graph eines Rechnernetzwerkes mit unterschiedlichen Übertragungsgeschwindigkeiten (Bandbreite). Der Pfad A-B-D ist langsamer als der Pfad A-C-D, obwohl die gleiche Anzahl von Knoten entlang der Pfade liegen.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Eigenschaften von Graphen

Eigenschaften von Graphen

1. Knotengrad, der für einen gegebenen Knoten i die Anzahl der verbundenen Knoten bezeichnet.
2. Bei gerichteten Graphen kann noch zwischen Ausgangsgrad (die Anzahl der ausgehenden Kanten) und Eingangsgrad (die Anzahl der eingehenden Kanten) unterschieden werden.
3. Pfade: Es existiert ein Pfad zwischen zwei Knoten u und v wenn ein Knoten v von einem Knoten u aus erreichbar ist, und eine Kantenfolge von u nach v existiert. Der Pfad kann uni- oder bidrektional sein.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Realisierung von Graphen

Realisierung von Graphen

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Realisierung von Graphen

Knoten- und Kantenlisten

Beispiel:

Kantenliste :=
[6, 11, 1, 2, 1, 3, 3, 1, 4, 1, 3, 4, 3, 6, 5, 3, 5, 5, 6, 5, 6, 2, 6, 4]
Knotenliste :=
[6, 11, 2, 2, 3, 0, 3, 1, 4, 6, 1, 1, 2, 3, 5, 3, 2, 4, 5]

• Die Teilfolge 2, 2, 3 beginnend an der dritten Position in dieser Zahlenfolge bedeutet beispielsweise »Knoten 1 hat Ausgangsgrad 2 und herausgehende Kanten zu den Knoten 2 und 3«.

• Man sieht bereits an diesem Beispiel, dass für Graphen mit vielen Kanten Knotenlisten weniger Speicherbedarf als Kantenlisten benötigen. Genauer benötigen Kantenlisten 2 + 2 · |E| Zahlen und Knotenlisten 2 + |V| + |E| Zahlen.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Realisierung von Graphen

Adjazenzmatrix

Insbesondere bei sehr vielen Kanten ist eine Speicherung der Verbindungen als n × n-Matrix sinnvoll. Der Wert n entspricht dabei der Knotenanzahl |V|. Eine derartige Matrix wird als Adjazenzmatrix bezeichnet.

• Die Adjazenzmatrix ist ähnlich einer Zustandsübergangstabelle einer FSM. Sie kann für gerichtete Graphen direkt erstellt werden.

• Die Idee der Adjazenzmatrix lässt sich direkt auf ungerichtete Graphen übertragen, wobei dann eigentlich nur die eine Hälfte der Matrix gespeichert werden muss, da sich die andere Hälfte durch Spiegelung ergibt.

• Beim Vergleich des Speicherbedarfs muss man nun beachten, dass die Matrixelemente boolesche Werte sind, die im Gegensatz zu Zahlwerten nur ein Bit benötigen.

• Es lassen sich zyklische wie azyklische Graphen darstellen

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Realisierung von Graphen

Adjazenzmatrix

Die folgende Adjazenzmatrix stellt den gerichteten Graphen G_g und ungerichteten G_u dar:

$${G}_{{G}}={\left(\matrix{{0}&{1}&{1}&{0}&{0}&{0}\\{0}&{0}&{0}&{0}&{0}&{0}\\{1}&{0}&{0}&{1}&{0}&{1}\\{1}&{0}&{0}&{0}&{0}&{0}\\{0}&{0}&{1}&{0}&{1}&{0}\\{0}&{1}&{0}&{1}&{1}&{0}}\right)}\\ {G}_{{U}}={\left(\matrix{{0}&{1}&{1}&{1}&{0}&{0}\\{1}&{0}&{0}&{0}&{0}&{1}\\{1}&{0}&{0}&{1}&{1}&{1}\\{1}&{0}&{1}&{0}&{0}&{1}\\{0}&{0}&{1}&{0}&{0}&{1}\\{0}&{1}&{1}&{1}&{1}&{0}}\right)}$$

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Realisierung von Graphen

Adjazenzmatrix

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Realisierung von Graphen

Mit Matrizen können wir direkt rechnen:

Wege zwischen Knoten

Man kann nun fragen, wie man über direkte Verbindungen hinaus längere Wege zwischen zwei Knoten finden kann. Eine Methode ist die Bildung von Potenzen A^m der Adjazenzmatrix. Die Komponenten der Matrix A^m geben dann die Anzahl der Wege der Länge m vom i-ten zum k-ten Knoten an. Die Komponenten der Matrix A² berechnet man nach der Regel „Zeile mal Spalte“ als Skalarprodukte der Zeilen- und Spaltenvektoren der Matrix A mit n × n Elementen:

$${\left({a}_{{{i}{k}}}\right)}^{{2}}={\sum_{{{i}={1}}}^{{n}}}{a}_{{{i}{j}}}{a}_{{{j}{k}}}$$

Die obige Formel liefert also die Anzahl der Wege der Länge 2 vom Knoten i zum Knoten k.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Realisierung von Graphen

Die Erreichbarkeitsmatrix

Will man wissen, ob unabhängig von der Länge des Weges überhaupt ein Weg von einem Knoten zu einem anderen existiert, so addiert man alle n Potenzen der Adjazenzmatrix und erhält die Erreichbarkeitsmatrix oder Wegematrix:

$${\mathbf{{E}}}={\sum_{{{i}={1}}}^{{n}}}{\mathbf{{A}}}^{{i}}$$

Die Einträge e_ik von E geben also an, auf wie vielen verschiedenen Wegen ein Knoten von einem anderen Knoten aus erreichbar ist, ohne dass dazwischen liegende Knoten mehrfach besucht werden.

• In der Definition von E sind einige Varianten gebräuchlich. Ist man beispielsweise nur an der Existenz eines Weges interessiert, so setzt man e_ik = 1, wenn der ursprüngliche Eintrag e_ik > 0 war, sonst bleibt der Eintrag 0 erhalten. Man hat dann also wieder eine effizient speicherbare binäre Matrix.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Realisierung von Graphen

Die Erreichbarkeitsmatrix

Grundkurs Informatik Bestimmung der Erreichbarkeitsmatrix an einem Beispiel. Die Potenzen der Matrix A ergebn sich aus dem Matrixprodukt!

Enthält eine ganze Spalte der Erreichbarkeitsmatrix nur die Einträge 0, so kann dieser Knoten von keinem anderen Knoten aus erreicht werden. Sind alle Einträge einer Zeile 0, so kann von dem entsprechenden Knoten aus kein andere Knoten erreicht werden.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Kürzeste und längste Wege

Kürzeste und längste Wege

Weiter mit den Adjazenzmatrizen ...

• Bei einem gewichteten Graphen kann man anstelle der Anzahl der Wege auch eine Summe von Gewichten längs der Kanten des Weges eintragen und diese als Weglängen interpretieren.
• Dies kann etwa das Minimum der Summe der Gewichte sein, wenn man den kürzesten Weg zwischen je zwei Kanten bestimmen möchte, oder auch das Maximum der Summe der Gewichte, wenn der längste Weg gesucht ist.
• Der Eintrag 0 bedeutet dabei nach wie vor, dass kein Weg vorhanden ist.

Berechnung der kürzesten und längsten Wege

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Kürzeste und längste Wege

Der Floyd-Warshall-Algorithmus

Nummeriere die Knoten des Graphen von 1 bis n durch und 
trage die Längen der Wege von Knoten i zu Knoten j in die 
Erreichbarkeitsmatrix e(i,j) ein. Existiert kein solcher 
direkter Weg, trage ein Symol für „unendlich“ ein (Infinity).
Wiederhole für k := 1 bis n
  Wiederhole für i := 1 bis n
   Wiederhole für j := 1 bis n
    Wenn e(i,k) + e(k,j) < e(i,j) dann
      Setze e(i,j) := e(i,k) + e(k,j)
      Ersetze die zu e(i,j) gehörende Knotenliste durch die Knotenliste, die durch
      Verbinden der zu e(i,k) und zu e(k,j) gehörenden Knotenlisten entsteht.
ENDE

Floyd-Warshall-Algorithmus zum Auffinden kürzester Wege in einem Graphen

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Kürzeste und längste Wege

+

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Kürzeste und längste Wege

Längste Pfade

• Wenn jeder Knoten immer wieder besucht werden kann gibt es unendlich viele unendlich lange Pfade

https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Kürzeste und längste Wege

Topologisches Sortieren

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Graphen als dynamische Datenstrukturen

Graphen als dynamische Datenstrukturen

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Graphen als dynamische Datenstrukturen

Graphen als dynamische Datenstrukturen

Graph als dynamische Datenstruktur

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Verkettete Speicherung eines Graphen

Verkettete Speicherung eines Graphen

Forward-Star Datenstruktur

• Eine sehr platzeffiziente Möglichkeit zum Speichern von Graphen ist der Forward Star. Dabei wird zunächst jedem der n Knoten ein Index zugewiesen.

• Nun werden in einem als Knotenliste bezeichneten Array K Verweise auf Positionen in einem zweiten Array, die Nachfolgerliste N, eingetragen.

  • Diese enthält, beginnend mit dem ersten Nachfolger von Knoten 1 der Reihe nach alle Nachfolger von Knoten 1, sofern dieser überhaupt einen hat.
  • Danach kommen alle Nachfolger von Koten 2 usw. Die Nachfolgerliste enthält somit genau einen Eintrag für jede der m Kanten.

• Die in der Knotenliste eingetragenen Verweise K_i geben die Position an, an der in der Nachfolgerliste die zugehörigen Nachfolger beginnen.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Verkettete Speicherung eines Graphen

Forward-Star Datenstruktur

Repräsentation eines Graphen als Forward Star

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Verkettete Speicherung eines Graphen

Forward-Star Datenstruktur

Der Graph wird direkt als verzeigerte Datenstruktur abgebildet. Jeder Knoten hat eine Nachfolgerliste. Algortihmen auf diese Datenstruktur anzuwenden ist wegen Zyklen gefährlich und aufwendig Zyklen zu erkennen.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Vergleich und Komplexität

Vergleich und Komplexität

addp Vergleich der Komplexität. Hierbei gilt n = |V| und m = |E|.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Vergleich und Komplexität

Komplexität der Berechnung der Erreichbarkeitsmatrix

• Die Komplexität für die Berechnung der Erreichbarkeitsmatrix eines Graphen mit n Knoten durch Summierung der ersten n Potenzen der Adjazenzmatrix ist von der Ordnung O(n⁴), also polynomial mit einem recht hohen Exponenten. Dies ergibt sich, da n − 1 Matrixmultiplikationen auszuführen sind, wobei die Komplexität der Multiplikation zweier n × n Matrizen von der Ordnung O(n³) ist.

• Der Floyd-Warshall-Algorithmus hat die Komplexität O(n³), was sich aus den drei ineinander geschachtelten Schleigen mit n Durchläufen sofort ertgit.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Vergleich und Komplexität

Das Löschen eines Knotens löscht auch zugehörige Kanten, so dass hier der Aufwand in allen Varianten unvermutet hoch ist. Zu den einzelnen Varianten sind einige Bemerkungen angebracht:

• Bei Kantenlisten ist sowohl das Einfügen von Kanten (Anhängen zweier Zahlen) und von Knoten (Erhöhung der ersten Zahl um 1) besonders günstig, falls das Anhängen von Zahlen nicht zum Umkopieren eines Feldes führt. Das Löschen von Kanten kann das Zusammenschieben in einer Liste bedeuten; das Löschen von Knoten eine erneute Durchnummerierung der Knoten.
• Bei Knotenlisten ist insbesondere das Einfügen von Knoten (Erhöhung der ersten Zahl und Anhängen einer 0) günstig.
• In der Matrixdarstellung ist insbesondere das Manipulieren von Kanten eine sehr effizient ausführbare Operation. Der Aufwand bei Knoteneinfügung hängt von der Realisierung der Matrix ab, hier wurde von einem Kopieren der Matrix in eine größere Matrix ausgegangen.
• Bei der Realisierung als Adjazenzliste ergibt sich unterschiedlicher Aufwand, je nachdem ob die Knotenliste als Feld (mit Direktzugriff) oder als verkettete Liste (mit sequenziellem Durchlauf) realisiert wird.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Durchsuchen von Graphen

Durchsuchen von Graphen

• Das systematische Durchsuchen eines Graphen ist durchaus keine triviale Aufgabe.
• Da es sich um einen wichtigen Teilaspekt vieler Anwendungen handelt, werden gibt es einige Algorithmen zum Durchsuchen von Graphen.
• Verwendet werden solche Verfahren beispielsweise um einen Weg von einem gegebenen Startknoten zu einem Zielknoten zu finden, der ggf. bestimmten Kriterien genügen soll (wie: gefunden werden soll der kürzest mögliche Weg).

Tiefensuche

Bei der Tiefensuche (Depth First Search) in einem Graphen besucht man von einem Startknoten k ausgehend dessen nächsten noch nicht besuchten Nachfolger, d.h. den als nächsten in der zu k gehörenden Nachfolgerliste befindlichen Knoten und setzt dort die Suche rekursiv fort. Gerät man dabei in eine Sackgasse, so muss der Weg bis zum ersten Knoten zurückverfolgt werden, von dem aus eine alternative Wahl möglich ist (Backtracking).

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Durchsuchen von Graphen

Breitensuche

Bei der Breitensuche (Breadth First Search) besucht man von einem Knoten ausgehend zuerst alle direkten Nachfolger, d. h. die in der zugehörigen Kantenliste enthaltenen Knoten, bevor deren noch nicht besuchte Nachfolger besucht werden. Auch bei der Breitensuche müssen Knoten als schon bearbeitet markiert werden können, wozu wie schon bei der Tiefensuche der Eintrag „Status“ verwendet wird. Anstelle eines Stapels wird bei der Breitensuche ein Puffer (Warteschlange, FIFO) für die temporäre Speicherung benötigt.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Durchsuchen von Graphen

A∗-Algorithmus

• Problematisch bei der uniformen Kosten Suche ist, dass zur Bestimmung kürzester Wege der zu expandierende Knoten nur auf Basis der schon entstandenen Kosten ab dem Startknoten ausgewählt wird, in der Annahme, dass es besser ist zunächst die Wege mit aktuell geringen Kosten weiter zu betrachten.

• Solche Wege können aber kurz sein und in die falsche Richtung gehen, d. h. weg vom Ziel.

• Das Verfahren bemerkt dies erst, wenn andere Wege, die näher am Ziel sind, wieder besser bewertet werden. Man bezeichnet solche Suchverfahren als uninformierte Suche, weil sie keine Informationen darüber haben, wie nahe sie während der Suche dem Ziel schon gekommen sind (ohne den Weg zum Ziel tatsächlich zu berechnen).

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Durchsuchen von Graphen

A∗-Algorithmus

Der A∗ -Algorithmus kombiniert die besten Aspekte zweier anderer Algorithmen:

• Dijkstra-Algorithmus: Dieser Algorithmus findet den kürzesten Weg zu allen Knoten von einem einzigen Quellknoten.
• Greedy Best-First-Suche: Dieser Algorithmus untersucht den Knoten, der dem Ziel am nächsten zu sein scheint, basierend auf einer heuristischen Funktion.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Durchsuchen von Graphen

A∗-Algorithmus

• A∗ findet immer eine Lösung, sofern diese existiert. Das Verfahren ist optimal-effizient.

• Es lässt sich zeigen, dass kein anderer Algorithmus existiert, der bei der Suche weniger Knoten expandiert, wenn die Bedingungen für die heuristische Funktion eingehalten werden.

• Deswegen ist A∗ das Standardverfahren für alle Anwendungen, bei denen kürzeste Wege gesucht werden müssen, so z.B. bei der Routenplanung in Navigationsgeräten oder der Wegplanung in Computerspielen.

• Die Zeitkomplexität von A∗ ist exponentiell in der Länge des kürzesten Pfads zum Ziel.

• Das Hauptproblem in der Praxis ist jedoch der (ebenfalls exponentielle) Speicherverbrauch, da alle Knoten im Speicher gehalten werden müssen.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Durchsuchen von Graphen

Schlüsselkonzepte in der A∗-Suche

https://www.datacamp.com/tutorial/a-star-algorithm

Die Effizienz des A∗ -Algorithmus beruht auf seiner intelligenten Bewertung von Pfaden unter Verwendung von drei Schlüsselkomponenten: g(n), h(n) und f(n). Diese Komponenten arbeiten zusammen, um den Suchprozess auf die vielversprechendsten Pfade zu lenken.

A∗ Kostenfunktionen: Pfadkosten g, heuristische Funktion h

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Durchsuchen von Graphen

function A_Star(start, goal) {
    // Initialize open and closed lists
    openList = [start]          // Nodes to be evaluated
    closedList = []             // Nodes already evaluated
    // Initialize node properties
    start.g = 0                 // Cost from start to start is 0
    start.h = heuristic(start, goal)  // Estimate to goal
    start.f = start.g + start.h       // Total estimated cost
    start.parent = null               // For path reconstruction
    while openList is not empty:
        // Get node with lowest f value - implement using a priority queue
        // for faster retrieval of the best node
        current = node in openList with lowest f value
        // Check if we've reached the goal
        if current = goal:
            return reconstruct_path(current)
        // Move current node from open to closed list
        remove current from openList
        add current to closedList        
        // Check all neighboring nodes
        for each neighbor of current:
            if neighbor in closedList:
                continue  // Skip already evaluated nodes              
            // Calculate tentative g score
            tentative_g = current.g + distance(current, neighbor)    
            if neighbor not in openList:
                add neighbor to openList
            else if tentative_g >= neighbor.g:
                continue  // This path is not better
            // This path is the best so far
            neighbor.parent = current
            neighbor.g = tentative_g
            neighbor.h = heuristic(neighbor, goal)
            neighbor.f = neighbor.g + neighbor.h
    return failure  // No path exists
}

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Durchsuchen von Graphen

A∗-Algorithmus

Was ist wichtig?

• Es werden Listen geführt um noch nicht und breits besuchte Knoten zu merken

Initialisierungsphase

Der Algorithmus beginnt mit der Erstellung von zwei wesentlichen Listen:

1. Die offene Liste beginnt nur mit dem Startknoten
2. Die geschlossene Liste beginnt leer

Jeder Knoten speichert vier kritische Informationen:

1. g: Die tatsächlichen Kosten vom Startknoten
2. h: Die geschätzten Kosten für das Ziel
3. f: Die Summe von g und h
4. parent: Verweis auf den vorherigen Knoten (für Pfadrekonstruktion)

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Durchsuchen von Graphen

Hauptschleife

Der Kern von A∗ ist seine Hauptschleife, die fortgesetzt wird, bis entweder:

1. Das Ziel ist erreicht (Erfolg)
2. Die offene Liste wird leer (Fehler - es existiert kein Pfad)

Während jeder Iteration wird der Algorithmus:

1. Wählt den vielversprechendsten Knoten (niedrigster f-Wert) aus der offenen Liste aus
2. Verschiebt es in die geschlossene Liste
3. Untersucht alle benachbarten Knoten

Nachbarbewertung

Für jeden Nachbarn der Algorithmus:

1. Überspringt Knoten, die sich bereits in der geschlossenen Liste befinden
2. Berechnet einen vorläufigen G-Wert
3. Aktualisiert Knotenwerte, wenn ein besserer Pfad gefunden wird
4. Fügt der offenen Liste neue Knoten hinzu

Stefan Bosse - Algorithmen und Datenstrukturen - Modul G Graphen und Graphenalgorithmen :: Durchsuchen von Graphen

Wegrekonstruktion

Sobald das Ziel erreicht ist, arbeitet der Algorithmus rückwärts durch die übergeordneten Referenzen, um den optimalen Pfad vom Start zum Ziel zu konstruieren.

Diese systematische Vorgehensweise stellt sicher, dass A* immer den optimalen Weg findet, wenn:

1. Die heuristische Funktion ist zulässig (niemals überschätzt)
2. Zwischen dem Start- und dem Zielknoten existiert tatsächlich ein Pfad