ComenzarEmpieza gratis

Camino más corto I

Puedes aprovechar lo que sabes sobre cómo encontrar vecinos para intentar encontrar caminos en una red. Un algoritmo para buscar un camino entre dos nodos es el algoritmo de "búsqueda en anchura" (BFS). En un algoritmo BFS, comienzas desde un nodo concreto y buscas de forma iterativa entre sus vecinos y los vecinos de esos vecinos hasta encontrar el nodo de destino.

Los algoritmos de búsqueda de caminos son importantes porque ofrecen otra forma de evaluar la importancia de los nodos; lo verás en un ejercicio posterior.

En este conjunto de 3 ejercicios, vas a avanzar poco a poco hasta llegar al algoritmo BFS final. El problema se ha dividido en 3 partes que, si completas en secuencia, te llevarán a una primera implementación del algoritmo BFS.

Este ejercicio forma parte del curso

Introducción al análisis de redes en Python

Ver curso

Instrucciones del ejercicio

  • Crea una función llamada path_exists() que tenga 3 parámetros — G, node1 y node2 — y devuelva si existe o no un camino entre los dos nodos.
  • Inicializa la cola de nodos a visitar con el primer nodo, node1. queue debe ser una lista.
  • Itera sobre los nodos en queue.
  • Obtén los vecinos del nodo usando el método .neighbors() del grafo G.
  • Comprueba si el nodo de destino node2 está en el conjunto de neighbors. Si está, devuelve True.

Ejercicio interactivo práctico

Prueba este ejercicio y completa el código de muestra.

# 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 y ejecutar código