imported>Georg Hügler am 14. Februar 2023 um 17:13 Uhr

2023-02-14T17:13:38Z

Neue Seite

{{Lückenhaft|1=Anwendungen fehlen bzw. sind nicht detailliert ausgeführt (bspw.: Elimination toten Codes), Beispiele sind unzureichend (Aussehen gängiger Kontrollflusselemente wie if/while/goto fehlt völlig)}}

Ein '''Kontrollflussgraph''' ist ein Begriff aus der [[Informatik]] und bezeichnet einen [[Gerichteter Graph|gerichteten Graphen]], der dazu dient, den [[Kontrollfluss|Programmablauf]] eines [[Computerprogramm]]s zu beschreiben. Kontrollflussgraphen werden unter anderem zur [[Compiler#Programmoptimierung (ausführlich)|Programmoptimierung]] eingesetzt.<ref>{{Literatur |Online=https://web.archive.org/web/20160118005507/http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=7365827&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D7365827 |Titel=Masking wrong-successor Control Flow Errors employing data redundancy |Autor=Javad Yousefi |Datum=2015 |Hrsg=IEEE |Seiten=201–205 |DOI=10.1109/ICCKE.2015.7365827 |Sprache=en}}</ref>

== Aufbau ==

Jeder Kontrollflussgraph besteht aus
* einer Menge von Knoten <math>V</math>, die die Grundblöcke des beschriebenen Programms darstellen, sowie
* einer Menge von gerichteten Kanten <math>E</math>, 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.<ref>{{Literatur |Autor=Aho, Alfred V., Aho, Alfred V. |Titel=Compilers : principles, techniques, & tools |Auflage=2nd ed |Verlag=Pearson/Addison-Wesley |Ort=Boston |Datum=2007 |ISBN=0321486811}}</ref>

Wenn von einem Knoten mehrere Kanten wegführen (der Knoten also Quelle mehrerer gerichteter Kanten ist), so entspricht das einer [[Verzweigung (Programmierung)|Verzweigung]].
[[Schleife (Programmierung)|Schleifen]] finden sich als [[Zyklus (Graphentheorie)|Zyklen]] in Kontrollflussgraphen wieder.
Beispielsweise zeigt der Zyklus <math>B\to C\to E\to D\to B</math> im unten abgebildeten Graph <math>G_2\langle V,E,A\rangle</math> an, dass im zugrundeliegenden Computer-Programm eine Schleife enthalten ist.

== Beispiele ==
[[Datei:Directed acyclic graph.svg|mini|250px|Kontrollflussgraph <math>G_1</math> mit unerreichbarem Code]]
[[Datei:Directed graph, cyclic.svg|mini|225px|Kontrollflussgraph <math>G_2</math> mit Schleife]]

Im abgebildeten Graphen <math>G_1</math> mit Eingangsknoten <math>A</math> und Ausgangsknoten <math>F</math> existiert kein [[Weg (Graphentheorie)|Pfad]] vom Eingangsknoten <math>A</math> zum Knoten <math>G</math>. Der Grundblock <math>G</math> stellt damit [[Toter Code|toten Code]] dar.

Graph <math>G_2</math> enthält einen Zyklus. Das zugrundeliegende Programm enthält damit eine (implizite oder explizite) [[Schleife (Programmierung)|Schleife]].

== Siehe auch ==

* [[Dominanzrelation (Kontrollflussgraph)]]
* [[Programmablaufplan]]
* [[Reduzierbarer und irreduzierbarer Kontrollflussgraph]]
* [[Compilerbau]]
* [[McCabe-Metrik]]

== Einzelnachweise ==
<references />

[[Kategorie:Softwarearchitektur]]
[[Kategorie:Compilerbau]]

Kontrollflussgraph - Versionsgeschichte

imported>Georg Hügler am 14. Februar 2023 um 17:13 Uhr