Kontrollflussgraph

Ein Kontrollflussgraph ist ein spezieller gerichteter Graph mit einem ausgezeichneten Wurzelknoten r.

Er besteht somit aus einer Menge von Knoten V, aus einer Menge von gerichteten Kanten E und dem Wurzelknoten $r\in V$. Die Schreibweise lautet $G\langle V,E,r\rangle$.

Darüber hinaus muss es in jedem Kontrollflussgraphen von r zu jedem anderen Knoten $u\in V$ einen Pfad geben.

$G\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\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. Dieser Exit-Knoten darf dann keine ausgehenden Kanten besitzen, also nicht Quelle einer gerichteten Kante sein.

Kontrollflussgraphen werden in der Informatik verwendet, um den Kontrollfluss von Computer-Programmen darzustellen. Sie werden unter anderem zur Programmoptimierung eingesetzt. 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 oben abgebildeten Graph $G_2\langle V,E,A\rangle$ an, dass im zugrundeliegenden Computer-Programm eine Schleife enthalten ist.

Siehe auch

• Dominanzrelation (Kontrollflussgraph)
• Programmablaufplan
• Reduzierbarer und irreduzierbarer Kontrollflussgraph