Kontrollflussgraph
aus Wikipedia, der freien Enzyklopädie
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 
. Die Schreibweise lautet 
.
Darüber hinaus muss es in jedem Kontrollflussgraphen von r zu jedem anderen Knoten 
einen Pfad geben.
ist kein Flussgraph, da es keinen Pfad von A nach G gibt.Der oben dargestellte Graph 
ist kein Kontrollflussgraph, da es keinen Pfad von A nach G gibt.
Dieser Graph 
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: 
.
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 
eines Kontrollflussgraphen 
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 
im oben abgebildeten Graph an, dass im zugrundeliegenden Computer-Programm eine Schleife enthalten ist.
