शुरू करेंमुफ़्त में शुरू करें

Shortest Path I

आप नेटवर्क में पथ ढूँढने के लिए, पड़ोसियों को खोजने की अपनी जानकारी का उपयोग कर सकते हैं. दो नोड्स के बीच पथ खोजने के लिए एक एल्गोरिदम "breadth-first search" (BFS) है. BFS में, आप किसी चुने हुए नोड से शुरू करते हैं और उसके पड़ोसियों तथा उनके पड़ोसियों में क्रमिक रूप से खोज करते हैं, जब तक कि गंतव्य नोड न मिल जाए.

पाथफाइंडिंग एल्गोरिदम महत्त्वपूर्ण हैं क्योंकि वे नोड की महत्ता आँकने का एक और तरीका देते हैं; आप इसे आगे के एक अभ्यास में देखेंगे.

इन 3 अभ्यासों के सेट में, आप धीरे-धीरे आगे बढ़ते हुए अंतिम BFS एल्गोरिदम तक पहुँचेंगे. समस्या को 3 भागों में बाँटा गया है, जिन्हें क्रम से पूरा करने पर आप BFS एल्गोरिदम का एक प्रारंभिक इम्प्लीमेंटेशन बना लेंगे.

यह अभ्यास पाठ्यक्रम का हिस्सा है

Python में नेटवर्क विश्लेषण का परिचय

पाठ्यक्रम देखें

अभ्यास निर्देश

  • path_exists() नाम का एक फंक्शन बनाएँ जिसमें 3 पैरामीटर हों — G, node1, और node2 — और जो यह बताए कि इन दो नोड्स के बीच कोई पथ मौजूद है या नहीं.
  • विज़िट करने वाले नोड्स की queue को पहले नोड node1 से इनिशियलाइज़ करें. queue एक list होनी चाहिए.
  • queue में मौजूद नोड्स पर इटरेट करें.
  • ग्राफ G के .neighbors() मेथड का उपयोग करके उस नोड के पड़ोसी प्राप्त करें.
  • जाँच करें कि गंतव्य नोड node2, neighbors के सेट में है या नहीं. अगर है, तो 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
कोड संपादित करें और चलाएँ