Kontrollflussgraph

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

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. Dann muss es von jedem Knoten u\in V einen Pfad zu x geben.

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[Bearbeiten]