最短路徑 I

你可以運用已知的「找出鄰居節點」的方法，來嘗試在網路中尋找路徑。兩個節點之間的路徑搜尋有一種演算法稱為「廣度優先搜尋」（breadth-first search，BFS）。在 BFS 中，你會從特定節點開始，反覆搜尋它的鄰居，以及鄰居的鄰居，直到找到目標節點為止。

路徑搜尋演算法很重要，因為它提供了另一種衡量節點重要性的方式；你會在後面的練習看到這點。

在這組共 3 個練習中，你會逐步建構，最後得到完整的 BFS 演算法。我們把問題拆成 3 個部分，只要依序完成，就能做出 BFS 的初版實作。

本練習屬於課程

Python 網路分析入門

檢視課程

練習說明

建立名為 path_exists() 的函式，包含 3 個參數：G、node1、node2，並回傳兩個節點之間是否存在路徑。
以第一個節點 node1 初始化待造訪節點的佇列。queue 應該是一個 list。
逐一迭代 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

編輯並執行程式碼