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.

Aufbau[Bearbeiten]

Jeder Kontrollflussgraph besteht aus

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

Die Schreibweise lautet G\langle V,E,r\rangle.

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 B\to C\to E\to D\to B im unten abgebildeten Graph G_2\langle V,E,A\rangle an, dass im zugrundeliegenden Computer-Programm eine Schleife enthalten ist.

Formale Anforderungen an Kontrollflussgraphen[Bearbeiten]

In jedem Kontrollflussgraphen muss es von r zu jedem anderen Knoten u\in V einen Pfad geben.

G_1\langle V,E,A\rangle ist kein Flussgraph, da es keinen Pfad von A nach G gibt.

Der oben dargestellte Graph G_1\langle V,E,A\rangle ist kein Kontrollflussgraph, da es keinen Pfad von A nach G gibt.

Kontrollflussgraph G_2\langle V,E,A\rangle

Dieser Graph G_2\langle V,E,A\rangle ist ein Kontrollflussgraph, da es von A zu jedem anderen Knoten einen Pfad gibt. So gibt es zum Beispiel folgenden Pfad von A nach D: A\to B\to C\to E\to D.

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

Darüber hinaus zeichnet man manchmal auch einen Exit-Knoten x\in V eines Kontrollflussgraphen G\langle V,E,r,x \rangle aus. Dann muss es von jedem Knoten u\in V einen Pfad zu x geben.

Siehe auch[Bearbeiten]