Ein ungerichteter Graph ist eine Graph-Datenstruktur, bei der jede Kante zwei Knoten ohne Richtung verbindet. Eine Kante zwischen u und v kann in beide Richtungen benutzt werden — man zeichnet sie als einfache Linie statt als Pfeil.
Formale Definition
Ein ungerichteter Graph ist ein Paar G = (V, E) aus Knotenmenge V und Kantenmenge E. Jede Kante ist eine zweielementige Menge {u, v} — die Reihenfolge der Endpunkte spielt keine Rolle: {u, v} und {v, u} sind dieselbe Kante.
Beispiele aus der Praxis
- Straßen- und Wegenetze ohne Einbahnstraßen
- Freundschaftsbeziehungen in sozialen Netzwerken (symmetrisch)
- Strom-, Wasser- oder Glasfasernetze
- Verbindungen zwischen Computern in einem lokalen Netz
Eigenschaften und Algorithmen
Der Grad eines Knotens zählt seine angrenzenden Kanten. Ohne Richtung zerfällt jeder ungerichtete Graph in Zusammenhangskomponenten; ein Zyklus ist ein Pfad, der zum Ausgangsknoten zurückführt. Tiefensuche und Breitensuche durchlaufen den Graphen und finden Komponenten, Kreise oder kürzeste Wege in ungewichteten Netzen. Der minimale Spannbaum (Algorithmen von Kruskal und Prim) ist nur für ungerichtete Graphen definiert.
Im Gegensatz dazu besitzt der gerichtete Graph Kanten mit fester Richtung — etwa für Einbahnstraßen oder Follow-Beziehungen. Auch ungerichtete Graphen lassen sich als Adjazenzliste oder Adjazenzmatrix speichern; bei der Matrix ist diese dann symmetrisch.
Verwandte Grundlagen: Graph-Datenstruktur, Dijkstra.