【アルゴリズム】同じ頂点を通らず元の場所へ戻る！「閉路」｜情報処理問題1000本ノック
アルゴリズムや離散数学における「グラフ理論」。同じ頂点や枝を重複せずに一周して元に戻る「閉路（サイクル）」の定義と、閉路を持たない「木構造」との関係を攻略しましょう。
1. 【 問題 】：アルゴリズムとデータ構造（グラフ理論）
【 問題 】 グラフ理論における経路に関する記述です。グラフ上のある頂点から出発して枝をたどり、途中で同じ頂点を2度とおらずに、元の出発点に戻ってくるような経路（ループ）を何と呼ぶでしょうか？
（ア）閉路（Cycle）
（イ）木（Tree）
（ウ）道（Path）
（エ）次数（Degree）
2. 正解：
正解：（ア）閉路（Cycle）
3. 解説：「ぐるっと一周して戻る『環（リング）』の構造」
閉路（Cycle / サイクル）は、グラフ理論における基本概念の一つです。
例えば、頂点A ➔ 頂点B ➔ 頂点C ➔ 頂点A というように、途中の頂点（BやC）を重複して通ることなく一巡して元の頂点に戻る経路を指します。
有向グラフ（矢印の向きがあるグラフ）における閉路は「有向閉路（Directed Cycle）」と呼び、閉路が存在しない有向グラフは**DAG（Directed Acyclic Graph）**として処理の依存関係の表現などに重宝されます。
| グラフ構造 | 閉路（サイクル）の有無 | 特徴・ITでの応用例 |
|---|---|---|
| （ア）閉路を含むグラフ | 存在する | ネットワークの冗長化経路やSNSのコミュニティ分析など。 |
| （イ）木（Tree） | 存在しない（閉路がない連結グラフ） | 階層構造。ファイルシステム、B+木インデックス、構文解析木など。 |
1. 理解のコツ: 「山手線の路線図」に例えてみましょう。
・東京を出発して、品川 ➔ 渋谷 ➔ 新宿 ➔ 池袋 ➔ 上野 と巡り、同じ駅を通らずに再び「東京」に戻ってくる内回り・外回りのような循環路線が閉路（サイクル）です。
・一方で、終点（どん詰まり）があって折り返すしかない線路構造は「木（Tree）」であり、行き止まりにならず循環できるのが閉路の最大の特徴です。
2. 試験対策の視点: 基本情報技術者試験や応用情報技術者試験の「離散数学・アルゴリズム」で出題されます。
問題文に「出発点に戻る」「途中同じ頂点を2度通らない」「閉じた経路」といった記述があれば、即座に閉路（Cycle）を選びましょう。
また、「連結な無向グラフから閉路をすべて取り除いた（最小限の枝で全頂点をつないだ）部分グラフ」を全域木（Spanning Tree）と呼ぶなど、関連用語の発展問題にも注意しておきましょう！
4. まとめ
「途中で同じ頂点を重複して通らず、出発点にぐるりと戻ってくる経路」。これが閉路（Cycle）です。閉路を持たない「木（Tree）」構造との対比と合わせて覚えておきましょう！