# Graphen
## Grundlagen
- Bestehen aus `Knoten` und `Kanten`
- Anwendungen: Routenplanung, soziale Netzwerke

### Typen von Graphen
- `Vollstaendiger Graph`: Jeder Knoten ist mit jedem anderen Knoten verbunden
- `Zusammenhaengender Graph`: Man kann jeden Knoten ueber die Kanten erreichen
- `gewichtet` / `ungewichtet`
- `gerichtet` / `ungerichtet`
## Speicherung von Graphen
### Adjazenzmatrix
- zweidimensionales Integer-Array mit Groesse n*n
- `x`: Kante mit Gewicht x / `NaN`: Kante existiert nicht
- **Beispiel:** `matrix[5][1] = 10` -> Kante von Knoten `5` zu `1` mit Gewicht `10`
- `matrix[0][1] = NaN` -> Kante von Knoten `0` zu `1` nicht vorhanden

#### Vorteile:
- schnelles Abfragen von Kanten (`O(1)`)
- schnelles Hinzufuegen/Loeschen von Kanten (`O(1)`)
#### Nachteile:
- Knoten hinzufuegen/loeschen sehr aufwendig
- Enormer Speicherverbrauch, da auch ungenutzte Kanten abgespeichert werden (`O(n²)`)
### Adjazenzliste
- Liste von Knoten, wobei fuer jeden Knoten die direkten Nachfolgeknoten mit ihrem jeweiligen Gewicht abgespeichert werden

| Knoten | Verbindungen |
|---|---|
| A | (B, Gewicht: 17) |
| B | (A, Gewicht: 12), (C, Gewicht: 954) |
| C | (C, Gewicht: 4) |

#### Vorteile
- Speichereffizent: Nur tatsaechlich vorhandene Kanten nutzen Speicherplatz
- Nachfolger eines Knotens finden geht schneller
#### Nachteile
- Pruefen, ob zwei bestimmte Knoten verbunden sind, geht langsamer
## Graphalgorhitmen
### Graph durchlaufen
#### Pseudocode

markiere alle Knoten als nicht besucht
markiere v als besucht
füge v in eine (zunächst leere) Datenstruktur D ein
solange D nicht leer ist
	entnehme einen Knoten w aus D
	für alle Kanten {w, u}
		falls u als nicht besucht markiert ist
			markiere u als besucht
			füge u in D ein

#### Erläuterung
- nutzt man für `Datenstruktur D` eine `Queue`, führt man eine `Breitensuche` durch.
- nutzt man einen `Stack`, eine `Tiefensuche`
##### Breitensuche (Queue)
- Es wird zunächst in die Breite gesucht, d.h. alle nacheinander alle verbundenen Knoten, dann die Knoten, die an diesen verbunden sind, usw. (`Welle`)
##### Tiefensuche (Stack)
- Es wird zunächst in die Tiefe gesucht, d.h. es wird damit begonnen, einen Pfad komplett bis zum Ende zu durchlaufen, bevor abzweigende Pfade betrachtet werden. (`Oktopusarm`)

### Moore
- Ermittelt Abstand eines jeden Knotens vom Startknoten bei einem `ungewichteten` Graphen
- Da der Vorgänger gespeichert wird, kann der kürzeste Weg zu einem Knoten leicht nachvollzogen werden.
#### Pseudocode

für alle Knoten w  
	setze d(w) = ∞, vorg(w) = { }
füge v in eine (zunächst leere) Queue D ein
setze d(v) = 0
solange D nicht leer ist
	entnehme einen Knoten w aus D  
	für alle Kanten {w,u}
		falls d(u) = ∞
			setze d(u) = d(w)+1, vorg(u) = w
			füge u in D ein

### Dijkstra
- Ermittelt Abstand eines jeden Knotens vom Startknoten bei einem `gewichteten` Graphen
#### Pseudocode

für alle Knoten w  
	setze dg(w) = unendlich 
setze dg(v) = 0  
füge v in eine (zunächst leere) Priority-Queue D ein  
solange D nicht leer ist  
	entnehme einen Knoten w mit minimalem dg(w) aus D  
	für alle Kanten {w,u}  
		falls dg(u) = unendlich
			füge u in D ein
			setze dg(u) = dg(w)+g({w,u})
		falls dg(u) > dg(w)+g({w,u})
			setze dg(u) = dg(w)+g({w,u})

### Topologische Sortierung
- Der Graph muss frei von Zyklen sein, damit eine topologische Sortierung gefunden werden kann.
- Die topologische Sortierung ist eine Reihenfolge, in der alle Knoten des Graphen abgearbeitet werden können, wobei die Abhängigkeiten berücksichtigt werden.
#### Pseudocode

Für jeden Knoten k des Graphen:  
	setze den Wert des Knoten auf die Anzahl an Knoten, die auf ihn zeigen

Setze topologische_Sortierung auf leer

Wiederhole solange es einen unmarkierten Knoten mit Wert 0 gibt  
	Nimm einen unmarkierten Knoten k mit Wert 0  
	Markiere k 

	Füge k der topologische_Sortierung hinzu  

	Für jeden Nachbarknoten n von k:  
		reduziere den Wert des Knoten n um 1  

Falls noch unmarkierte Knoten übrig sind:  
	=> es gibt keine topologische Sortierung
sonst:  
	=> topologische_Sortierung ist gefunden