ネットワークスペシャリスト 2024年 午前2 問05

スパニングツリーの隣接ノード判定【午前2 解説】

要点まとめ

• 結論：ルートノードAを起点としたスパニングツリー上で隣接するノードは「DとE」である。
• 根拠：スパニングツリーは全ノードを最小コストで連結し、かつ閉路を作らない木構造であるため、最小コストの辺を優先して選ぶ。
• 差がつくポイント：単に辺の重みが小さいだけでなく、ルートからの経路上で隣接関係が成立するかを正確に理解することが重要。

正解の理由

よくある誤解

• 「ルートノードAと直接つながるノードが隣接」と誤解しやすい。
• 最小コストの辺だけを選べばよいと考え、全体の木構造を無視する誤りが多い。

解法ステップ

1. 各辺の重みを確認し、最小コストの辺から順に選択する。
2. ルートノードAからの経路を意識し、閉路を作らないように辺を追加する。
3. 全ノードが連結されるまで辺を選び、スパニングツリーを完成させる。
4. 完成したスパニングツリー上で隣接するノードの組み合わせを確認する。
5. 問題の選択肢と照らし合わせて正解を特定する。

選択肢別の誤答解説

• ア: AとE
  AとEは直接つながるが、スパニングツリーの最小コスト経路ではA–B–Eの方が優先されるため、隣接とは言えない。
• イ: BとC
  BとCは辺でつながっているが、スパニングツリーの構築過程で他の経路が優先され、隣接とはならない。
• ウ: CとD
  CとDも辺は存在するが、コストの観点からE–Dの方が優先されるため隣接ではない。
• エ: DとE
  E–Dの辺はコスト3で、スパニングツリー上で隣接する正しい組み合わせである。

補足コラム

FAQ