Graphenalgorithmen

Graphenalgorithmen sind Algorithmen, die auf Graphen operieren, um Strukturen zu analysieren, Pfade zu finden oder Optimierungen durchzuführen. Ein Graph besteht aus Knoten (Vertex) und Kanten (Edges); Kanten können gerichtet oder ungerichtet, gewichtet oder ungewichtet sein. Graphen modellieren reale Strukturen wie Straßennetze, Kommunikationsnetze oder soziale Netzwerke und können statisch oder dynamisch sein.

Typische Aufgaben umfassen kürzeste Wege, All-Pairs Shortest Path, Mindestspannbaum, Konnektivität und Zyklerkennung. Weitere Themen sind Topologische Sortierung in gerichteten Graphen, Netzwerkfluss und Matching.

Wichtige Algorithmen umfassen Dijkstra (gewichtet, nicht negativ), Bellman-Ford (negative Gewichte), Floyd-Warshall (alle Paare), A (pfadorientierte Suche mit Heuristik). Für minimale Spanning Trees: Prim und Kruskal; Boruvka als weitere MST-Methode. Im Bereich Flussnetze: Edmonds-Karp und Dinic. Zur Strukturanalyse: Tarjan-Algorithmus und Kosaraju zur Bestimmung starker Zusammenhangskomponenten.

Graphdarstellung erfolgt oft via Adjazenzliste oder Adjazenzmatrix. Die Liste eignet sich gut für spärliche Graphen, die Matrix für dichte Graphen. Typische Komplexitäten: Dijkstra mit Min-Heap O((V+E) log V); BFS bei ungewichteten Graphen O(V+E); Bellman-Ford O(VE); Floyd-Warshall O(V^3). MST-Algorithmen Prim O(E log V), Kruskal O(E log E). Max-Flow-Algorithmen variieren je nach Methode von O(VE^2) bis O(V^2E).

Anwendungen finden sich in Routenplanung, Logistik, Telekommunikation, Analyse sozialer Netzwerke, Biologie und Compilerbau. Die Wahl des Algorithmus hängt von Grapheneigenschaften (Richtung, Gewichtung, Dynamik) sowie von Anforderungen an Genauigkeit und Laufzeit ab.