开始使用免费开始使用

Shortest Path I

您可以利用已掌握的查找邻居的知识，来尝试在网络中寻找路径。用于在两个节点间寻找路径的一个算法是"广度优先搜索"（BFS）算法。在 BFS 中，您从某个节点出发，迭代地搜索它的邻居以及邻居的邻居，直到找到目标节点。

路径寻找算法很重要，因为它们提供了评估节点重要性的另一种方式；您将在后续练习中看到这一点。

在这一组共 3 个练习中，您将循序渐进地构建最终的 BFS 算法。我们把问题拆成了 3 个部分，按顺序完成后，您就能得到 BFS 算法的第一版实现。

本练习是课程的一部分

Python 网络分析入门

查看课程

练习说明

  • 创建一个名为 path_exists() 的函数，包含 3 个参数：G、node1 和 node2，用于返回这两个节点之间是否存在路径。
  • 用起始节点 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
编辑并运行代码