เริ่มต้นใช้งานเริ่มต้นใช้งานได้ฟรี

Shortest Path I

นำความรู้เรื่องการหา neighbors มาต่อยอดเพื่อค้นหาเส้นทางในเครือข่าย อัลกอริทึมหนึ่งที่ใช้หาเส้นทางระหว่างสองโหนดคือ "breadth-first search" (BFS) ซึ่งเริ่มต้นจากโหนดที่กำหนด แล้วค้นหาผ่าน neighbors และ neighbors ของ neighbors ไปเรื่อย ๆ จนกว่าจะพบโหนดปลายทาง

อัลกอริทึมการค้นหาเส้นทางมีความสำคัญ เพราะช่วยประเมินความสำคัญของโหนดในอีกรูปแบบหนึ่ง ซึ่งจะได้เห็นในแบบฝึกหัดถัดไป

ในชุดแบบฝึกหัด 3 ข้อนี้ จะค่อย ๆ สร้างอัลกอริทึม BFS ทีละขั้นตอน โดยแบ่งปัญหาออกเป็น 3 ส่วน หากทำครบทั้งหมดตามลำดับ จะได้ implementation เบื้องต้นของอัลกอริทึม BFS

แบบฝึกหัดนี้เป็นส่วนหนึ่งของหลักสูตร

การวิเคราะห์เครือข่ายเบื้องต้นด้วย Python

ดูคอร์ส

คำแนะนำการฝึกหัด

  • สร้างฟังก์ชันชื่อ path_exists() ที่รับ 3 พารามิเตอร์ ได้แก่ G, node1, และ node2 แล้ว return ว่ามีเส้นทางระหว่างสองโหนดนั้นหรือไม่
  • กำหนดค่าเริ่มต้นของ queue สำหรับโหนดที่จะเยี่ยมชมด้วยโหนดแรก node1 โดย queue ควรเป็น list
  • วนซ้ำผ่านโหนดใน queue
  • ดึง neighbors ของโหนดโดยใช้เมธอด .neighbors() ของกราฟ G
  • ตรวจสอบว่าโหนดปลายทาง node2 อยู่ใน neighbors หรือไม่ ถ้าใช่ให้ return 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
แก้ไขและรันโค้ด