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

ग्राफ़ के लिए DFS इम्प्लिमेंट करना

इस अभ्यास में, आप एक ग्राफ़ को ट्रैवर्स करने के लिए depth first search एल्गोरिदम इम्प्लिमेंट करेंगे.

कदम याद करें:

  1. किसी भी वर्टेक्स से शुरू करें
  2. उस वर्टेक्स को visited vertices लिस्ट में जोड़ें
  3. हर current node के adjacent वर्टेक्स के लिए
    • अगर वह पहले से विज़िट हो चुका है -> उसे अनदेखा करें
    • अगर वह विज़िट नहीं हुआ है -> DFS को रिकर्सिवली चलाएँ

आपका कोड टेस्ट करने में मदद के लिए, नीचे दिया गया ग्राफ़ एक डिक्शनरी का उपयोग करके लोड किया गया है.

Graphical representation of a graph.

graph = {
  '0' : ['1','2'],
  '1' : ['0', '2', '3'],
  '2' : ['0', '1', '4'],
  '3' : ['1', '4'],
  '4' : ['2', '3']
}

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

Python में Data Structures और Algorithms

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

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

  • जाँचें कि current_vertex अभी तक विज़िट नहीं हुआ है.
  • current_vertex को visited_vertices में जोड़ें.
  • उपयुक्त मान पास करके dfs() को रिकर्सिव रूप से कॉल करें.

इंटरैक्टिव व्यावहारिक अभ्यास

इस अभ्यास को इस नमूना कोड को पूरा करके आज़माएँ।

def dfs(visited_vertices, graph, current_vertex):
    # Check if current_vertex hasn't been visited yet
    if current_vertex not in ____:
        print(current_vertex)
        # Add current_vertex to visited_vertices
        ____.add(____)
        for adjacent_vertex in graph[current_vertex]:
            # Call recursively with the appropriate values
            ____(____, ____, ____)
            
dfs(set(), graph, '0')
कोड संपादित करें और चलाएँ