Control Flow Graph (CFG)
Definition
A Control Flow Graph (CFG) is a graphical representation of all possible paths of execution through a program — nodes represent blocks of sequential statements (or single statements), and edges represent the flow of control between them (branches, loops).
Notation
| Element | Meaning |
|---|---|
| Node (circle/dot) | A block of sequential code (no branches) or a single statement |
| Edge (arrow) | Flow of control from one node to the next |
| Decision Node | A node with two or more outgoing edges (from if, while, for, case) |
| Predicate Node | Same as decision node — represents a condition being tested |
Constructing a CFG from Code
1: if (x > 0)
2: y = 1;
3: else
4: y = -1;
5: print(y);
Key Structures in a CFG
- Sequence — straight-line flow, one node leads directly to the next
- Selection (branch) — a decision node splits into two or more paths (if/else, switch)
- Iteration (loop) — a path loops back to a earlier node (while, for)
Purpose / Uses
- Basis for Cyclomatic Complexity — V(G) = E − N + 2, computed directly from the CFG
- Basis for Path Testing — independent paths through the CFG define test cases
- Helps visualize and analyze all possible execution paths, useful for identifying dead code or unreachable branches
Relationship to Other Topics
- Cyclomatic Complexity is calculated FROM the CFG
- Path Testing uses the CFG to identify all independent paths to test
Exam tip: Practice converting a small code snippet (with if-else and a loop) into its CFG, then compute Cyclomatic Complexity from it — this two-step question (draw CFG → compute V(G)) is a classic combined numerical/diagram question.