グラフアルゴリズム

イントロ

流れを順番に追う

基本情報技術者試験で扱う「グラフアルゴリズム」を、IT知識なしでも意味と使いどころから学べるように整理します。まず目的をつかみ、似た言葉や条件の違いを短く見分けます。

定義

とは、始点から近い階層の頂点を順に調べるグラフ探索です。
見分けるポイント: は、辺の重みが非負のグラフで最短経路を求める方法です。は、最初に格納した要素を最初に取り出すデータ構造です。は、最後に格納した要素を最初に取り出すデータ構造です。は、未探索の隣接頂点を優先して深く進むグラフ探索です。は、頂点間の経路のうち重みの合計が最小の経路を求める探索です。

手順

構造図

図では、グラフアルゴリズムの流れを順に整理しています。入力、処理、判断、結果のつながりを確認します。

例

場面: 駅の接続図で、幅優先探索が近い駅から調べる様子を見る例
順に考えると: まず深さ優先探索が何を表すかを確認します。次に幅優先探索との違いを、問題文の対象・条件・順序から分けます。ここでは深く進むのか、近い層から広げるのか、重み付き最短経路かを分ける。この順で読むと、初見の選択肢でも中心の考え方から外れた説明を除外しやすくなります。
ここが結論: この例では、深く進むのか、近い層から広げるのか、重み付き最短経路かを分けることが要点です。答えを選ぶときは、グラフを図形問題として見て、節点と辺のデータ構造として読まないという読み違いを避けます。

注意

確認

Q1

グラフアルゴリズムを問題で読むとき、最も適切な見方はどれですか。

まとめ