Kontrollflussgraph

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

Jeder Kontrollflussgraph besteht aus

• einer Menge von Knoten ${\displaystyle V}$, die die Grundblöcke des beschriebenen Programms darstellen, sowie
• einer Menge von gerichteten Kanten ${\displaystyle E}$, die mögliche Übergänge, d. h. Programmabläufe darstellen.

Üblicherweise fügt man zur Knotenmenge zusätzlich einen speziellen Eingangs- und Ausgangsknoten hinzu, für die im Programm keine Anweisungen existieren. Diese entsprechen dem Betreten bzw. Verlassen des entsprechenden Programmabschnitts.

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

Im abgebildeten Graphen ${\displaystyle G_{1}}$ mit Eingangsknoten ${\displaystyle A}$ und Ausgangsknoten ${\displaystyle F}$ existiert kein Pfad vom Eingangsknoten ${\displaystyle A}$ zum Knoten ${\displaystyle G}$. Der Grundblock ${\displaystyle G}$ stellt damit toten Code dar.

Graph ${\displaystyle G_{2}}$ enthält einen Zyklus. Das zugrundeliegende Programm enthält damit eine (implizite oder explizite) Schleife.

• Dominanzrelation (Kontrollflussgraph)
• Programmablaufplan
• Reduzierbarer und irreduzierbarer Kontrollflussgraph
• Compilerbau
• McCabe-Metrik

1. Kontrollflussorientierte Testverfahren
2. McCabe-Metrik
3. Kontrollfluss
4. Dominanzrelation (Kontrollflussgraph)
5. Interprozesskommunikation
6. Reduzierbarer und irreduzierbarer Kontrollflussgraph
7. CFG
8. Gerichteter Graph
9. Datenflussanalyse
10. Dynamisches Software-Testverfahren
11. Analytische Qualitätssicherung
12. ConQAT
13. Maximale Laufzeit