# Portabilitaet: UNIVERSAL
# Zuletzt validiert: 2026-01-28 (Gemini)
# Naechste Pruefung: 2027-01-28
# Quellen: [informatik/datenstrukturen/README.txt]

GRAPHEN
=======

Stand: 2026-01-28

WAS IST EIN GRAPH?
------------------
Die allgemeinste Form der Vernetzung. Alles ist ein Graph: Das Internet, soziale Netzwerke, Strassenkarten.
Er besteht aus:
- **Knoten (Vertices/Nodes):** Die Objekte (Staedte, User, Seiten).
- **Kanten (Edges):** Die Verbindungen.

EIGENSCHAFTEN VON KANTEN
------------------------
1. **Gerichtet (Directed):** Einbahnstrasse (A -> B). Z.B. Twitter-Follower, Hyperlinks.
2. **Ungerichtet (Undirected):** Verbindung gilt beidseitig (A - B). Z.B. Facebook-Freunde, Handschlag.
3. **Gewichtet (Weighted):** Kante hat "Kosten" oder "Distanz". Z.B. Entfernung in km zw. Staedten.

REPRAESENTATION IM SPEICHER
---------------------------
Wie speichert man das Chaos?

### 1. Adjazenzmatrix
Ein 2D-Gitter (Tabelle). Zeile A, Spalte B = 1 wenn verbunden.
- **Vorteil:** O(1) um zu pruefen "Sind A und B verbunden?".
- **Nachteil:** Riesiger Speicherverbrauch O(V^2). Schlecht fuer "sparse graphs" (wenig Kanten).

### 2. Adjazenzliste
Jeder Knoten hat eine Liste seiner Nachbarn.
- `{ A: [B, C], B: [C], C: [] }`
- **Vorteil:** Speichereffizient O(V+E). Standard fuer die meisten Anwendungen.
- **Nachteil:** Pruefung "A -> B?" dauert O(Grad von A).

WICHTIGE GRAPHEN-ALGORITHMEN
----------------------------
- **Traversierung:** BFS (Breitensuche) & DFS (Tiefensuche).
- **Shortest Path:** Dijkstra (gewichtet), Bellman-Ford (negative Gewichte), Floyd-Warshall (alle zu allen).
- **Topological Sort:** Reihenfolge von Abhaengigkeiten finden (z.B. Build-Systeme, Task-Planer).
- **Minimum Spanning Tree (MST):** Alle Knoten mit min. Kosten verbinden (Kabel verlegen).

SIEHE AUCH
----------
wiki/informatik/datenstrukturen/baeume.txt
wiki/informatik/algorithmen/suche.txt
