メインコンテンツへスキップ
見出し画像

木・グラフと幅優先探索

    用語の意味


    グラフは頂点と辺で関係を表します。木は連結で閉路のない無向グラフで、根を決めると親子関係を表せます。幅優先探索は始点に近い層から順に調べます。深さ優先探索は進める方向に進み、行き止まりで戻ります。


    使いどころと問題の見方


    幅優先探索ではキューに次の候補を入れます。全ての辺の重みが同じ場合、初めて到達した経路の辺数が最小です。頂点をキューに入れた時点で訪問済みと記録すると、複数の経路から同じ頂点を何度も追加するのを防げます。


    確認問題【オリジナル】


    辺の長さがすべて等しい地図で、出発点から通る辺の本数が最小の経路を探す方法はどれですか。


    ア.挿入ソート
    イ.二分探索
    ウ.連結リストの末尾への追加
    エ.幅優先探索


    正解と理由


    正解はエです。幅優先探索では、辺を1本でたどれる頂点から順に調べるためです。


    IPA 基本情報技術者試験シラバス

    この記事が参加している募集

     
     
    ITの知識ゼロから、基本情報技術者試験の勉強を始めました📚 わからなかった言葉や問題を、自分の言葉でまとめる備忘録です。 基礎からコツコツ学んで、いつかは応用情報にも挑戦したいです! 一緒に学んでいただけたらうれしいです🌱

    あなたへのおすすめ