Kontrollflussgraph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
QS-Informatik

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+)

Ein Kontrollflussgraph ist ein Begriff aus der Informatik und bezeichnet einen gerichteten Graphen der dazu dient, den Kontrollfluss eines Computerprogramms zu beschreiben. Sie werden unter anderem zur Programmoptimierung eingesetzt [1].

Aufbau[Bearbeiten | Quelltext bearbeiten]

Jeder Kontrollflussgraph besteht aus

  • einer Menge von Knoten , die Instruktionen darstellen,
  • dem Wurzelknoten , an dem die Ausführung beginnt, und
  • einer Menge von gerichteten Kanten , die mögliche Übergänge, d. h. Programmabläufe darstellen.

Die Schreibweise lautet .

Den Wurzelknoten kann man sich als Startpunkt des Computer-Programmes, den Exit-Knoten als seinen Endpunkt vorstellen.

Wenn von einem Knoten mehrere Kanten wegführen (der Knoten also Quelle mehrerer gerichteter Kanten ist), so entspricht das einer Verzweigung. Schleifen finden sich als Zyklen in Kontrollflussgraphen wieder. Beispielsweise zeigt der Zyklus im unten abgebildeten Graph an, dass im zugrundeliegenden Computer-Programm eine Schleife enthalten ist.

Formale Anforderungen an Kontrollflussgraphen[Bearbeiten | Quelltext bearbeiten]

In jedem Kontrollflussgraphen muss es von zu jedem anderen Knoten einen Pfad geben.

ist kein Flussgraph, da es keinen Pfad von nach gibt.

Der oben dargestellte Graph ist kein Kontrollflussgraph, da es keinen Pfad von nach gibt.

Kontrollflussgraph

Dieser Graph ist ein Kontrollflussgraph, da es von zu jedem anderen Knoten einen Pfad gibt. So gibt es zum Beispiel folgenden Pfad von nach : .

Manchmal wird auch gefordert, dass der Wurzelknoten keine einkommenden Kanten haben darf, also nicht Ziel einer gerichteten Kante sein darf.

Darüber hinaus zeichnet man manchmal auch einen Exit-Knoten eines Kontrollflussgraphen aus. Dann muss es von jedem Knoten einen Pfad zu geben.

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. : Masking wrong-successor Control Flow Errors employing data redundancy. IEEE, S. 201–205. doi:10.1109/ICCKE.2015.7365827