Shortest Path I
近傍ノードの見つけ方を応用して、ネットワーク内で経路を探してみましょう。2つのノード間の経路探索アルゴリズムの1つに「幅優先探索（BFS）」があります。BFS では、特定のノードから開始し、その近傍ノード、さらにその近傍ノードへと順にたどって、目的地のノードが見つかるまで探索します。
経路探索アルゴリズムは、ノードの重要度を評価する別の視点を与えてくれるため重要です。この点は後の演習で確認します。
この3問の演習では、最終的な BFS アルゴリズムに向けて段階的に組み立てていきます。問題は3つのパートに分かれており、順に解いていくことで BFS の最初の実装に到達できます。
この演習はコースの一部です
Pythonで学ぶネットワーク分析入門
演習の手順
G、node1、node2の3つの引数を取り、2つのノード間に経路が存在するかどうかを返す関数path_exists()を作成します。- 訪問予定ノードのキューを、最初のノード
node1で初期化します。queueはリストにしてください。 queue内のノードを順に反復処理します。- グラフ
Gの.neighbors()メソッドを使って、そのノードの近傍ノードを取得します。 - 目的地のノード
node2がneighborsの集合に含まれているか確認し、含まれていればTrueを返します。
実践的なインタラクティブ演習
このサンプルコードを完成させて、この演習に挑戦してみましょう。
# Define path_exists()
def ____:
"""
This function checks whether a path exists between two nodes (node1, node2) in graph G.
"""
visited_nodes = set()
# Initialize the queue of nodes to visit with the first node: queue
queue = ____
# Iterate over the nodes in the queue
for node in ____:
# Get neighbors of the node
neighbors = ____
# Check to see if the destination node is in the set of neighbors
if node2 in ____:
print('Path exists between nodes {0} and {1}'.format(node1, node2))
return ____
break