BaşlayınÜcretsiz başlayın

En Kısa Yol I

Ağda yollar bulmayı denemek için komşuları bulma bilgisinden yararlanabilirsin. İki düğüm arasındaki yol bulma algoritmalarından biri "breadth-first search" (BFS) algoritmasıdır. BFS algoritmasında belirli bir düğümden başlar ve hedef düğümü bulana kadar bu düğümün komşularını ve komşularının komşularını yinelemeli olarak ararsın.

Yol bulma algoritmaları önemlidir çünkü düğüm önemini değerlendirmek için başka bir yol sağlar; bunu ilerideki bir egzersizde göreceksin.

Bu 3 egzersizlik sette, nihai BFS algoritmasına yavaş yavaş ulaşacaksın. Sorun, art arda tamamladığında BFS algoritmasının ilk sürümünü elde edeceğin 3 parçaya bölündü.

Bu egzersiz, kursun bir parçasıdır

Python ile Ağ Analizine Giriş

Kursa Göz Atın

Egzersiz talimatları

  • G, node1 ve node2 olmak üzere 3 parametre alan ve iki düğüm arasında bir yol olup olmadığını döndüren path_exists() adlı bir fonksiyon oluştur.
  • Ziyaret edilecek düğümlerin kuyruğunu ilk düğüm olan node1 ile başlat. queue bir liste olmalı.
  • queue içindeki düğümler üzerinde yinele.
  • Graf G'nin .neighbors() metodunu kullanarak düğümün komşularını al.
  • Hedef düğüm node2'nin neighbors kümesinde olup olmadığını kontrol et. Eğer varsa True döndür.

Uygulamalı etkileşimli egzersiz

Bu egzersizi bu örnek kodu tamamlayarak deneyin.

# 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
Kodu Düzenle ve Çalıştır