1. Uczyć się
    2. /
  2. Courses
    3. /
  3. Pythonで学ぶネットワーク分析入門
Connected

Exercise

Shortest Path I

近傍ノードの見つけ方を応用して、ネットワーク内で経路を探してみましょう。2つのノード間の経路探索アルゴリズムの1つに「幅優先探索（BFS）」があります。BFS では、特定のノードから開始し、その近傍ノード、さらにその近傍ノードへと順にたどって、目的地のノードが見つかるまで探索します。

経路探索アルゴリズムは、ノードの重要度を評価する別の視点を与えてくれるため重要です。この点は後の演習で確認します。

この3問の演習では、最終的な BFS アルゴリズムに向けて段階的に組み立てていきます。問題は3つのパートに分かれており、順に解いていくことで BFS の最初の実装に到達できます。

Instrukcje

100 XP
  • G、node1、node2 の3つの引数を取り、2つのノード間に経路が存在するかどうかを返す関数 path_exists() を作成します。
  • 訪問予定ノードのキューを、最初のノード node1 で初期化します。queue はリストにしてください。
  • queue 内のノードを順に反復処理します。
  • グラフ G の .neighbors() メソッドを使って、そのノードの近傍ノードを取得します。
  • 目的地のノード node2 が neighbors の集合に含まれているか確認し、含まれていれば True を返します。