システムアーキテクト 2025年 午前2 問08

サイクロマティック複雑度の計算【午前2 解説】

要点まとめ

• 結論→正解は イ：与えられたグラフのノード数とエッジ数を代入するとサイクロマティック複雑度は $7-5+2=4$ です。
• 根拠→サイクロマティック複雑度は制御フローグラフのエッジ数 $e$ とノード数 $n$ に対して $e-n+2$ で定義されるため、この定義をそのまま用います。
• 差がつくポイント→ノードやエッジを正確に数えること（重複辺や結合成分を見落とさない）と、別の定義（判定点数＋1や $E-N+2P$）で整合性を取る確認が重要です。

正解の理由

よくある誤解（2〜3 行）

• ノードとエッジのどちらかを数え間違えて異なる値を出してしまうことが多いです。
• 複数の辺や分離したサブグラフ（結合成分 P）を意識せずに計算する誤りもあります。

解法ステップ

1. 問題図からノードを数える（A,B,C,D,E → $n=5$）。
2. 矢印（有向エッジ）を1本ずつ数える（列挙された 7 本 → $e=7$）。
3. 与えられた公式 $e-n+2$ に代入して計算する：$7-5+2=4$。
4. 必要なら別の見方（判定点数＋1、あるいは $E-N+2P$）で結果が一致するか確認する。

選択肢別の誤答解説

• ア: 3 — これはエッジ数を 6 と数えて $6-5+2=3$ とした場合の誤答です。どの辺を見落としたかを確認してください。
• イ: イ（4） — 正解。ノード5、エッジ7 より $7-5+2=4$ になります。
• ウ: 5 — これはエッジを 8 本と誤って数えた場合（またはノードを 4 と誤認した場合）に生じる典型的なミスです。図の各矢印を一つずつ数え直してください。
• エ: 7 — 公式を誤って $e+n+2$ のように扱ったり、各分岐を過剰にカウントした場合に出る大きな誤答です。原理を確認しましょう。

補足コラム（関連知識など）

• 一般式は連結成分（独立した入口）を考慮して $M=E-N+2P$（P は入口の数）と表されます。通常の単一関数の CFG では $P=1$ なので $E-N+2$ です。
• 別の直感的な求め方として「判定点（if, while, for, case 等）の数 D に対して $M=D+1$」という方法があります。ただし switch/case はケース数に応じた調整が必要です（例：k 分岐なら k−1 と数える）。
• 実務ではサイクロマティック複雑度は独立経路数＝テストケースの下限にもなるため、複雑度が高い関数はテストコストや保守性リスクが高いと判断されます。一般目安として 10 を超えると注意が必要です。
• 例（簡単なコードと計算）:

def f(x):
    if x > 0:
        if x % 2 == 0:
            return 1
        else:
            return 2
    else:
        return 3
# 判定点 D = 2 (外側 if と内側 if) → M = D + 1 = 3

FAQ