Was ist ein gerichteter Graph und was sind seine Hauptmerkmale?

Ein gerichteter Graph (oder Digraph) ist eine Datenstruktur, die aus einer Menge von Knoten (Vertices) und einer Menge von gerichteten Kanten (Arcs) besteht, die diese Knoten verbinden. Jede Kante hat eine Richtung, die angibt, welcher Knoten der Anfangspunkt und welcher der Endpunkt ist.

Hauptmerkmale:

• Knoten (Nodes / Vertices): Elemente des Graphen, dargestellt durch Punkte. Sie können Objekte, Zustände oder Phasen repräsentieren.
• Kanten (Edges / Arcs): Verbindungen zwischen Knoten. In einem gerichteten Graphen hat die Kante eine Richtung, die den Übergang von einem Knoten zum anderen anzeigt. Sie werden durch ein geordnetes Paar (u, v) dargestellt, wobei u der Anfangsknoten und v der Endknoten ist.
• Richtung: Ein Schlüsselelement, das einen gerichteten Graphen von einem ungerichteten unterscheidet. Die Bewegung ist nur entlang der Richtung der Kante möglich. Eine Kante von A nach B bedeutet nicht, dass man von B nach A bewegen kann, es sei denn, es gibt eine separate Kante von B nach A.
• Schleifen (Loops): Kanten, die einen Knoten mit sich selbst verbinden (v, v).
• Mehrfache Kanten (Multiple Edges): Mehrere Kanten, die dasselbe Paar von Knoten in derselben Richtung verbinden. In einfachen gerichteten Graphen sind mehrfache Kanten nicht erlaubt.
• Isolierte Knoten: Knoten ohne eingehende oder ausgehende Kanten.
• Knotengrad:
  • Eingehender Grad (In-degree): Anzahl der Kanten, die in einen Knoten eintreten.
  • Ausgehender Grad (Out-degree): Anzahl der Kanten, die aus einem Knoten ausgehen.

Anwendungen in QA:

• Zustandsgraphen zur Testung endlicher Automaten.
• Steuerflussgraphen zur Codeanalyse und Erstellung von Testfällen.
• Modellierung von Abhängigkeiten in Systemen (z.B. Abhängigkeiten zwischen Diensten oder Modulen).
• Testen von Nutzungsszenarien mit strengen Aktionssequenzen.