MulaiMulai sekarang secara gratis

Shortest Path I

Anda dapat memanfaatkan pengetahuan tentang cara menemukan tetangga untuk mencoba mencari jalur dalam sebuah jaringan. Salah satu algoritma untuk pencarian jalur antara dua simpul adalah algoritma "breadth-first search" (BFS). Dalam algoritma BFS, Anda mulai dari sebuah simpul tertentu dan secara iteratif menelusuri para tetangganya dan tetangga dari tetangganya hingga Anda menemukan simpul tujuan.

Algoritma pencarian jalur penting karena menyediakan cara lain untuk menilai pentingnya simpul; Anda akan melihat ini pada latihan berikutnya.

Dalam rangkaian 3 latihan ini, Anda akan membangunnya secara bertahap hingga mencapai algoritma BFS final. Masalahnya telah dipecah menjadi 3 bagian yang, jika Anda selesaikan berturut-turut, akan membawa Anda ke implementasi awal algoritma BFS.

Latihan ini adalah bagian dari kursus

Pengantar Analisis Jaringan di Python

Lihat Kursus

Petunjuk latihan

  • Buat fungsi bernama path_exists() yang memiliki 3 parameter — G, node1, dan node2 — dan mengembalikan apakah sebuah jalur ada atau tidak antara kedua simpul tersebut.
  • Inisialisasi antrian simpul yang akan dikunjungi dengan simpul pertama, node1. queue harus berupa list.
  • Lakukan iterasi atas simpul-simpul di queue.
  • Dapatkan tetangga dari simpul menggunakan metode .neighbors() dari graf G.
  • Periksa apakah simpul tujuan node2 ada dalam himpunan neighbors. Jika ada, kembalikan True.

Latihan interaktif praktis

Cobalah latihan ini dengan menyelesaikan kode contoh berikut.

# 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
Edit dan Jalankan Kode