Einführung in Dynamische Datenstrukturen - Gerichtete und Gewichtete Grafen

Gerichtete Grafen

• In gerichtetem Graphen sind Kanten nur in eine Richtung nutzbar.
• Beispiel: Knoten 6 kann zu 4 anderen Knoten, aber nicht über denselben Weg zurück.
• Knoten können unterschiedliche Anzeilen von eingehenden und ausgehenden Kanten haben.
• Wichtig: Zyklen bzw. Kreise -> Pfade, die zum Ausgangspunkt zurückführen.
• Zyklusfreiheit ist wichtig, um Endlos-Iterationen bei Algorithmen zu verhindern.

Beispiele für gerichtetet Grafen

• Transportwesen: Knoten = Kreuzungen, Kanten = Straßen.
• Web: Knoten = Webseiten, Kanten = Hyperlinks.
• Finanzsektor: Knoten = Banken, Kanten = Transaktionen.

Fragestellungen in gewichteten Grafen

• Existiert ein Weg zwischen zwei Knoten?
• Was ist der kürzeste Pfad zwischen zwei Knoten?
• Kürzester Pfad: Bezüglich Anzahl Zwischenknoten, Kosten, etc.
• Zyklusfreiheit und Konnektivität (Verbindung alle Knoten durch minimalste Kantenanzahl).

Anwendungen von Graphenmodellen im Web

• Webcrawler erstellen durch das Folgen von Links eine Graphenstruktur des Webs.
• Suchmaschinen bewerten Links basierend auf Verlinkungen.

Grafbibliothek in Java: JGraphT

• JGraphT erlaubt das Definieren und Arbeiten mit Knoten und Kanten.

Spezielle Probleme: Minimale Spanning Trees (MST)

• MST: Verbunden, zyklusfrei, alle Knoten enthalten.
• Anwendung in gewichteten Graphen: Fokus auf die kostengünstigste Verbindung.
• Beispiel: Straßen mit unterschiedlichen Mautkosten als Kanten.

Algorithms für MST

Kruskal-Algorithmus

• Sucht den MST durch Auswahl der günstigsten Kanten in jedem Schritt.
• Verwendet eine Liste der Kanten, sortiert nach Kosten.
• Verwendet eine disjunkte Menge der Knoten
• Prüft kontinuierlich auf Zyklusfreiheit.
• Schnelle, aber nicht immer global optimale Lösungen.

Prim-Algorithmus

• Beginnt bei einem Startknoten und erweitert den MST durch Hinzufügen der günstigsten Kanten.
• Hat nur begrenzte Kenntnis über den Gesamtkrafen.
• Berücksichtigt nur sichtbar Kanten vom aktuellen Knoten.
• Zyklusfreiheit wird durch Hinzufügen der Knoten und Auswahl der günstigsten Kanten gewährleistet.
• Ähnlich zum Webcrawler-Ansatz.

Dijkstra-Algorithmus

• Findet den kürzesten Pfad bzw. MST in gewichteten Graphen.
• Nutzt kontinuierliche Bewertung der Kosten, um global optimale Pfade zu finden.
• Beispiel aus Oldenburg Universität: Startknoten 1, Aktualisierung der erreichbaren Knoten und ihrer Distanzen.
• Der Pfad verbessert sich kontinuierlich durch Hinzufügen der günstigsten Optionen.

Vergleich der Algorithmen

• Kruskal: Sicht auf gesamten Grafen, arbeitet mit kompletter Kantenliste, schnell, nicht immer optimal.
• Prim: Sicht nur vom Startknoten und erweitert, garantierte zyklusfreiheit, schnell, nicht immer global optimal.
• Dijkstra: Global optimal durch kontinuierliche Kostenbewertung, aufwendiger.

Fazit

• Verständnis und Implementierung dieser Algorithmen ist entscheidend.
• Empfehlenswert: Nutzung und Testen der Algorithmen auf Papier und in Implementationen.
• Schwerpunkt in Kursen zu Algorithmen und Datenstrukturen.

Vielen Dank für die Aufmerksamkeit!