ComeçarComece de graça

Shortest Path I

Você pode aproveitar o que já sabe sobre como encontrar vizinhos para tentar encontrar caminhos em uma rede. Um algoritmo para encontrar caminho entre dois nós é o algoritmo de "busca em largura" (BFS). No BFS, você parte de um nó específico e pesquisa iterativamente seus vizinhos e os vizinhos dos vizinhos até encontrar o nó de destino.

Algoritmos de busca de caminhos são importantes porque oferecem outra forma de avaliar a importância dos nós; você verá isso em um exercício mais adiante.

Neste conjunto de 3 exercícios, você vai construir aos poucos até chegar ao algoritmo final de BFS. O problema foi dividido em 3 partes que, se você concluir em sequência, levarão a uma primeira implementação do algoritmo de BFS.

Este exercício faz parte do curso

Introdução à Análise de Redes em Python

Ver curso

Instruções do exercício

  • Crie uma função chamada path_exists() com 3 parâmetros — G, node1 e node2 — que retorna se existe ou não um caminho entre os dois nós.
  • Inicialize a fila de nós a visitar com o primeiro nó, node1. queue deve ser uma lista.
  • Itere sobre os nós em queue.
  • Obtenha os vizinhos do nó usando o método .neighbors() do grafo G.
  • Verifique se o nó de destino node2 está no conjunto de neighbors. Se estiver, retorne True.

Exercício interativo prático

Experimente este exercício completando este código de exemplo.

# 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
Editar e executar o código