Control flow graph

Материал из WikiGrapp
Перейти к навигации Перейти к поиску

Control flow graphуправляющий граф, уграф, граф потока управления, граф переходов.

A program can be represented as a directed graph (called control flow graph or cf-graph), in which vertices (or nodes) correspond to program statements and arcs reflect possible transfers of control between the corresponding statements. There are initial (or entry) and terminal (or exit) nodes in the graph that correspond to input and output statements of the program. If there is an arc [math]\displaystyle{ \,(p,q) }[/math], then [math]\displaystyle{ \,p }[/math] is called a predecessor of [math]\displaystyle{ \,q }[/math] and [math]\displaystyle{ \,q }[/math] is called a successor of [math]\displaystyle{ \,p }[/math].

It is assumed that a control flow graph [math]\displaystyle{ \,G }[/math] is a proper one, i.e. [math]\displaystyle{ \,G }[/math] has a single initial node without predecessors and a single terminal node without successors, and every node of [math]\displaystyle{ \,G }[/math] lies on at least one of the paths from the initial node to the terminal node.

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.