Wir verwenden den Graph als Datenstruktur, um verbundene Objekte zu
repräsentieren. Zum Beispiel: Router in einem Netzwerk, Flugrouten,
Städte, Menschen auf einer Social-Media-Plattform. Ein Graph zeigt an,
wie diese Objekte verbunden sind und wie stark diese Verbindung ist.
Graphen bestehen aus Scheitelpunkten (Nodes) und Kanten (Edges). Es
gibt keine Limitationen, was die Nodes und Edges eines Knoten
betrifft. Ebenfalls haben sie keinen Root-Node. Eine Kante verbindet
zwei Ecken. Ein gutes Beispiel für ein miteinander verbundenes
Netzwerk von Scheitelpunkten und Kanten sind Städte und die Straßen,
die sie miteinander verbinden. Eine Stadt in diesem Beispiel wäre ein
Scheitelpunkt, und die Straßen sind die Kanten.
Graphen können entweder directed(gerichtet) oder
undirected(ungerichtet) sein, directed Graphen sind wie eine
Einbahnstraße. Sind sie undirected, führen sie in beide Richtungen. In
ihrer Darstellung kann man anhand von Pfeilspitzen unterscheiden, ob
sie directed (z.B. "folgen" auf Twitter) oder undirected (z.B.
"Freund" auf Facebook) sind. Wenn sie directed sind, zeigen sie via
Pfeil auf einen oder mehrere Nachbarknoten. Die Edges können gewichtet
sein, damit zeigen sie die Stärke der Verbindung an. Wenn bspw. zwei
Personen auf Facebook häufiger Kontakt haben, dann haben sie ein
stärkeres Gewicht.
Gerichtete Graphen sind der LinkedList am ähnlichsten, jedoch kann jeder Knoten einen Zeiger auf andere Knoten haben. Es wird auch nicht garantiert, dass ein Graph zyklenfrei ist. Ein Zyklus liegt vor, wenn eine Reihe von Kanten mit dem Ursprungsscheitelpunkt verbunden ist. Ähnlich einer kreisförmigen verketteten Liste, bei der der Tail mit dem Head verbunden ist. So können wir beim Durchlaufen des Graphen am selben Knoten beginnen und enden.
Zwei gebräuchliche Methoden, um einen Graphen zu implementieren sind
die "Adjacency Matrix" und die "Adjacency List".
ADJACENCY MATRIX
Die Adjacency Matrix eignet sich gut für Graphen mit mehr Kanten als
Scheitelpunkten. Für jeden Knoten gibt es eine Reihe und eine Zeile.
Wenn zwei Knoten verbunden sind, werden sie mit 1 oder "true"
gekennzeichnet.
Add Node: O(V^2)
Dafür wird einiges an Platz benötigt (n - Knoten = Space: O (V^2)).
Wir nutzen hier Edges/Vertices anstatt "n". Wenn wir einen Knoten
hinzufügen, müssen wir eine Extrareihe und -zeile erstellen und dann
alle aus der alten Matrix in die neue kopieren.
Remove Node: O(V^2)
Wir müssen eine neue, kleinere Matrix erstellen und die Items aus der
alten herauskopieren.
Add Edge: O(1)
Als Erstes müssen wir den Index finden, dafür können wir eine
HashTable nutzen. Dann können wir direkt an den entsprechenden
Platz/zum Item gehen und die Edge hinzufügen.
Remove Edge: O(1)
Derselbe Weg wie beim Hinzufügen einer Edge mit dem Unterschied, dass
der Wert auf "false" bzw. null gesetzt werden muss.
Query Edge: O(1)
Um zu checken, ob 2 Knoten verbunden sind, wird ebenfalls die
HashTable genutzt.
Find Neighbours: O(V)
Erst nutzt man die HashTable, dann wird jedes Element in der Reihe
angesehen, um die verbundenen Knoten aufzuspüren.
remove Node: O(V^2)
Add Edge: O (1)
Das Durchqueren eines Graphen ist ähnlich wie das Durchqueren eines
Baums - wir verwenden die Breitensuche (Breadth-First-Search: BFS) und
die Tiefensuche (Depth-First-Search: DFS). Wie bei Trees durchläuft
die BFS einen Graphen Ebene für Ebene. Die DFS durchquert die Tiefe
eines Graphen - d.h. wir beginnen an einem Scheitelpunkt und
durchlaufen ihn, bis er keine Nachfolger/Nachbarn hat, dann verfolgen
wir die Bahn zurück, bis wir einen Scheitelpunkt finden, der dies tut.
Nun wiederholen wir den Vorgang.
ADJACENCY LIST
Die Adjacency List ist nützlich, wenn wir mit Scheitelpunkten
arbeiten, die Zeichenfolgen/Objekte und keine Dezimalzahlen sind.
Adjacency List verwenden wir, wenn der Graph weniger Kanten als
Scheitelpunkte hat. Sie ist wie ein Array mit integrierter LinkedList.
In jedem Element des Arrays, haben wir eine LinkedList und diese
LinkedList beinhaltet die Nachbarn des jeweiligen Knoten. Wir
verstauen nur die Edges, die existieren. Die Adjacency List ist
platzsparender als die Matrix. Das Worst-Case-Szenario ist der DENSE
GRAPH - ein Grap bei dem jeder Knoten mit allen anderen Knoten
verbunden ist außer sich selbst.
Add Node: O(1)
Einfach ein neues Element einfügen.
Remove Node: O(V^2)
Element löschen und absichern, dass dort keine Knoten mit einem Link
sind. (Das Vorgehen: über die Liste iterieren und die Target- Links
löschen.)
Add Edge: O(K)
Über die Liste iterieren und absichern, dass der Zielknoten nicht dort
ist. Dann mit einer HashTable den Knoten hinzufügen.
Remove Edge: O(K)
Über die Liste iterieren, um den Zielknoten zu finden. Dann den
Zielknoten löschen.
Query Edge: O(K)
Über die Liste iterieren, um zu schauen, ob der Zielknoten da ist oder
nicht.
Find Neighbours: O(K)
Über die Liste iterieren und Nachbarn finden.
Wir können viele Situationen mit Graphen modellieren, und jedes
Problem mit komplexen Beziehungen dadurch ziemlich einfach lösen. Zum
Beispiel können wir den kürzesten Weg zwischen zwei Adressen
heraussuchen. Mit der topologischen Sortierung können wir
herausfinden, wie wir am besten eine Anzahl an Jobs verarbeiten,
welche voneinander abhängig sind.
Undirected Graphs laufen in beide Richtungen. Ihre Kanten sind meist
gewichtet. Die Kanten gewichteter Graphen bezeichnen eine bestimmte
Metrik wie Entfernung, Zeit, die benötigt wird, um sich unter
Verwendung der Kanten zu bewegen usw.
Der "Dijkstra's Shortest Path Algorithm"
Dieser Algorithmus wird verwendet, um den kürzesten Weg zwischen
Knoten unter Verwendung der in einem Graph angegebenen Gewichte zu
berechnen und zu finden (in einem Netzwerk werden die Gewichtungen
durch Link-State-Pakete angegeben und enthalten Informationen wie den
Zustand der Router, Verkehrskosten...). Die Strecke beginnt mit dem
Quellknoten. Der Algorithmus von Dijkstra verfolgt die aktuell
bekannte Entfernung vom Quellknoten zu den restlichen Knoten und
aktualisiert diese Werte dynamisch, wenn ein kürzerer Pfad gefunden
wird.
Ein Knoten wird im Durchquerungs-Prozess als "visited" markiert und
dem Pfad hinzugefügt, wenn die Entfernung zwischen ihm und dem
Quellknoten am kürzesten ist (im Vergleich zu den anderen möglichen
Pfaden). Dies wird so lange fortgesetzt, bis alle Knoten zum Pfad
hinzugefügt wurden. Schließlich erhalten wir den kürzesten Pfad vom
Quellknoten zu allen anderen Knoten.
Wichtig ist hierbei, dass wir positive Gewichte haben, da sie zu den
Berechnungen hinzugefügt werden, um unser Ziel zu erreichen. Negative
Gewichtungen würden dazu führen, dass der Algorithmus nicht die
gewünschten Ergebnisse liefert.
Dieser Algorithmus ist ein sogenannter Greedy-Algorithmus, der
versucht, eine optimale Lösung eines Problems zu finden, indem er bei
jedem Schritt optimale Entscheidungen trifft.
Der "Prims Algorithm"
Der Algorithmus von Prim ist auch ein Greedy-Algorithmus. Es geht
darum die minimale Spannweite (Weg mit günstigster/leichtester
Verbindung) eines Graphen zu finden: den "Minimum Spanning Tree".
Der erste Satz enthält die bereits im "Minimum Spanning Tree"
enthaltenen Scheitelpunkte. Der andere Satz enthält die noch nicht
enthaltenen Scheitelpunkte. Bei jedem Schritt berücksichtigt der
Algorithmus alle Kanten(Edges), die die beiden Sätze verbinden und
wählt die Kante mit minimalem Gewicht aus den Kanten aus. Nachdem die
Kante ausgewählt wurde, wird der andere Endpunkt der Kante auf den
Satz verschoben, der den Minimum Spanning Tree enthält.