Lektion 8: Graphen – Definitionen und Traversierung

Diese Lektion bietet eine Einführung in eine der wichtigsten und vielfältigsten Abstraktionen der Informatik: Graphen.

Wir beginnen mit den Grundbegriffen der Grapentheorie: gerichtete und ungerichtete Graphen (directed and undirected graphs), Knoten (seltener Ecken; vertices, nodes), Kanten (edges, arcs), Wege (paths), Kreise (Zyklen; cycles), Teilgraphen (subgraphs), Zusammenhangskomponenten (connected components), etc. Als nächstes behandeln wir, wie man Graphen im Computer darstellt.

Schließlich beginnen wir mit den einfachsten Algorithmen auf Grapen: der systematischen Traversierung aller Knoten eines Graphen. Es gibt dazu i.W. zwei Verfahren, Tiefensuche (depth-first search, kurz DFS) und Breitensuche (breadth-first search, BFS), die sich in der Reihenfolge der Knotenbesuche unterscheiden. Neben direkten Anwendungen bildet das Traversieren die Grundlage komplizierterer Graph-Algorithmen, die vielfältige Probleme aus der Praxis lösen.

Lernziele

• Begriffe (Terminologie) der Graphentheorie verstehen
• Fragestellung aus der Praxis als Problem auf Graphen mit den passenden Begriffen formulieren können und mittels einer vorhandenen Bibliothek von Graph-Algorithmen programmatisch lösen können
• Breiten- und Tiefensuche und ihre Eigenschaften kennen
• einfache Algorithmen auf Graphen auf Basis von DFS und BFS entwerfen können

Fragensammlung für die Q&A Session

Tragt hier Fragen ein, die während der Vorbereitung aufkamen, und die ihr gerne klären möchtet. Bewertet außerdem die existierenden Fragen.

Hausordnung

• Es ist explizit erlaubt/erwünscht, Fragen aus den Aufgaben zur Vorbereitung unter den Videos zu übernehmen, wenn ihr diese der Q&A Session besprechen wollt.
• Auch wenn ihr gerade keine eigene Frage stellen möchtet, sind die Fragen der anderen oft hilfreiche Denkanstöße auch für euch. Deshalb, und um Fragen für die Q&A Sessions zu priorisieren, könnt ihr Fragen bewerten.
  Tragt dazu bei einer Frage entweder ein (zusätzliches) »+« ein, wenn ihr diese Frage interessant findet, oder ein (zusätzliches) »-«, wenn ihr sie nicht hilfreich findet (z.B. weil die Antwort direkt im Video gegeben wird). Listet zur besseren Übersicht zuerst alle »+«, dann alle »-«, jeweils in 5er Gruppen.
• Bevor ihr eine neue Frage eintragt, schaut ob eine existierende Frage eurer sehr nahe kommt; wenn ja, schreibt eure Frage als alternative Formulierung zu dieser Frage dazu.
• Wenn ihr der Meinung seid, ihr könnt eine Frage in wenigen Worten beantworten, so ergänzt eure Antwort unterhalb der Frage. Auch diese Antworten könnt ihr bewerten, wenn ihr sie hilfreich findet, oder Erwiderungen ergänzen, wenn ihr sie für falsch haltet.
• Seid konstruktiv.

Material

Teil 1, Teil 2, Teil 3, optionale Themen.

Die Videos entstammen dem Coursera MOOC Algorithms Part II von Robert Sedgewick und Kevin Wayne.

Teil 1 – Ungerichtete Graphen

Teil 1 befasst sich mit ungerichteten Graphen, bei denen die Verbindungen zwischen Knoten stets beidseitig sind.

1.1 – Introduction to Graphs

In diesem Video gibt Sedgewick die abstrakten Definitionen für ungerichtete Graphen, nennt eine Reihe von Beispielen, wo Graphen vorkommen, und welche abstrakten Probleme auf Graphen dabei gelöst werden müssen.

Von den Problemen auf Graphen werden wir nur einige in A&DS behandeln und lösen, aber es ist sehr hilfreich, zumindest die Problemstellungen dem Namen nach zu kenne, um bei Bedarf nach Lösungen recherchieren zu können.

Aufgaben zur Vorbereitung:

1. Woraus besteht ein (ungerichteter) Graph mathematisch?
2. Wie werden Graphen typischerweise graphisch (= als Bild) dargstellt? Welche Rolle spielt dabei die räumliche Anordnung der Knoten (vertices)? (Topologie vs. Geometrie)
3. Was ist ein Weg (Pfad; path)? Was ist ein Kreis (Zyklus; cycle)?
4. Was ist der Grad (degree) eines Knotens?
5. Wann sind zwei Knoten verbunden (connected)? Was ist eine Zusammenhangskomponente (connected component)?
6. Welche Probleme auf Graphen stellt Sedgewick vor? (10 Stück)

1.2 – Graph API

In diesem Video stellt Sedgewick die Java Implementierung von (ungerichteten) Graphen vor. Er diskutiert dabei neben der gewählten Adjazenzlisten-Darstellung (adjacency lists) auch kurz alternative Repräsentationen von Graphen im Computer (Kantenliste (edge list) und Adjazenzmatrix (adjacency matrix)).

Aufgaben zur Vorbereitung:

1. Welche Konvention trifft Sedgewick bezüglich der Namen/Labels der Knoten? Warum ist das (laut Sedgewick) keine gravierende Einschränkung?
2. Welche beiden »Anomalien« bzgl. Kanten erwähnt Sedgewick?

   Es ist best practice bei jeder Anwendung von Graphen explizit zu machen, ob diese Anomalien erlaubt sind oder nicht; allzu leicht werden sie übersehen und führen zu schwer aufzufindenden Fehlern.

3. Welche Operationen enthält die Graph API?
4. Wie sieht die textuelle Repräsentation (zur Eingabe von Graphen) aus?
5. Welche einfachen Operationen auf Graphen erwähnt Sedgewick als Beispiele um die Verwendung der API zu demonstrieren?
6. Welche drei Repräsentationen für Graphen diskutiert Sedgewick und wie begründet er die für die algs4-library getroffene Wahl?

1.3 – Depth-First Search

Tiefensuche (depth-first search, kurz DFS) ist die elementare Operation auf Graphen. Viele verblüffend einfache und trickreiche Algorithmen lassen sich auf Basis von DFS recht einfach formulieren (Beispiele in den optionalen Themen). In diesem Video stellt Sedgewick Tiefensuche im Detail vor und analysiert ihre Eigenschaften.

Aufgaben zur Vorbereitung:

1. Wie kommt man von einem (gemalten) Labyrinth zum zugehörigen Graph?
2. Beschreibe das Vorgehen einer (manuellen) Tiefensuch in einem Labyrinth mit Ariadne-Faden und Kreide.
3. Wie lautet die abstrakte Pseudocode-Formulierung von Tiefensuche als rekursive Method dfs(v)?
4. Was ist die Paths API? Was passiert im Konstruktor von Paths? Welche Gründe führt Sedgewick für die Wahl dieses Design-Patterns an?
5. Was ist die Aufgabe des Arrays edgeTo?
6. Welche Knoten markiert ein Aufruf dfs(s)? Welche nicht?
7. Welche Laufzeit (order of growth) hat dfs(s)? Seid präzise.

1.4 – Breadth-First Search

Die Reihenfolge, in der Tiefensuche die Knoten eines Graphs besucht, ist für manche Anwendungen ungeeignet. Insbesondere um einen kürzesten Weg zwischen zwei Knoten zu finden, eignet sie sich im Allgemeinen nicht. Breitensuche (breadth-first search, BFS) dagegen brilliert in genau dieser Anwendung. Dieses Video beschreibt das Verfahren und gibt einige Anwendungsbeispiele.

Aufgaben zur Vorbereitung:

1. Wie lautet die abstrakte Pseudocode-Formulierung von Breitensuche? Ist Breitensuche ebenfalls eine rekursive Methode?
2. Was sind Gemeinsamkeiten und Unterschiede in dieser Beschreibung zwischen DFS und BFS?
3. Welche Eigenschaft gilt für das Array distTo?
4. Wie unterscheidet sich die Laufzeit von BFS von der von DFS?

Teil 2 – Gerichtete Graphen

In vielen Anwendungen sind die Verbindungen zwischen zwei Objekten nicht automatisch beidseitig; in diesen Fällen ist eine passendere Modellierung über gerichtete Graphen (directed graphs, kurz digraphs, auch dt. Digraphen) gegeben. In diesem Teil verallgemeinern wir die Definitionen und Traversierungsmethoden aus Teil 1 auf Digraphen.

2.1 – Introduction to Digraphs

In diesem Video führt Sedgewick gerichtete Graphen ein. Zuerst wird die Terminologie auf Digraphen erweitert bzw. angepasst und es werden eine Reihe von Anwendungen genannt, in denen die Richtung der Kanten essentiell ist. Schließlich listet Sedgewick wichtige Fragestellungen in Digraphen auf.

Aufgaben zur Vorbereitung:

1. Wie malen wir Digraphen?
2. Was sind indegree (Eingrad) und outdegree (Ausgrad)?
3. Was macht man, wenn man in einem Digraph doch eine Beziehung in beide Richtungen ausdrücken will?
4. Welche Probleme auf Digraphen erwähnt Sedgewick?

2.2 – Digraph API

Wie für ungerichtete Graphen benötigt man eine Repräsentation für Digraphen im Computer. In diesem Video wird die Digraph API auf Basis jener für Graphen erklärt.

Aufgaben zur Vorbereitung:

1. Welche Knoten enthält adj(v) für Digraphen?
2. Was gibt Digraph.reverse() zurück?

2.3 – Digraph Search

In diesem Video beleuchtet Sedgewick, welche Änderungen sich für Tiefen- und Breitensuche ergeben, wenn wir es mit Digraphen zu tun haben.

Aufgaben zur Vorbereitung:

1. Inwiefern ist DFS ein Digraph-Algorithmus?
2. Welche (neuen) Anwendungen für DFS nennt Sedgewick?
3. Ändert sich für BFS etwas auf Digraphen? Wenn ja, was?
4. Was ist das multiple-source shortest path problem?
5. Wie funktioniert der vorgestellte Algorithmus für dieses Problem?

Teil 3 – Weitere Graphprobleme

Fragestellungen aus der Graphtheorie decken das gesamte Spektrum von sehr einfach zu lösenden Aufgaben bis hin zu beweisbar unlösbaren Probleme ab. Als Kontext betrachten wir hier einige weitere klassische Probleme auf Graphen.

3.1 – Graph Challenges

In diesem Video beschreibt Sedgewick sechs weitere Graphprobleme (auf ungerichteten Graphen) und diskutiert wie schwierig diese zu lösen sind.

Aufgaben zur Vorbereitung:

1. Welche Probleme nennt Sedgewick? Beschreibe jeweils was Eingabe und Ausgabe ist.