Depth First Search (DFS)

Python में Data Structures और Algorithms

Miriam Antona

Software engineer

ट्री/ग्राफ ट्रैवर्सल

• सभी नोड्स को विज़िट करने की प्रक्रिया
• डेप्थ फर्स्ट सर्च (DFS)
• ब्रेड्थ फर्स्ट सर्च (BFS)

डेप्थ फर्स्ट सर्च - बाइनरी ट्री

• इन-ऑर्डर
• प्री-ऑर्डर
• पोस्ट-ऑर्डर

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल

• क्रम: Left -> Current -> Right

इन-ऑर्डर ट्रैवर्सल - इम्प्लीमेंटेशन

• क्रम: Left -> Current -> Right

def in_order(self, current_node):

  if current_node:

    self.in_order(current_node.left_child)

    print(current_node.data)

    self.in_order(current_node.right_child)


my_tree.in_order(my_tree.root)

10
20
22
65
68
70
75

• जटिलता: $O(n)$
  • $n$ -> नोड्स की संख्या

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल

• क्रम: Current -> Left -> Right

प्री-ऑर्डर ट्रैवर्सल - इम्प्लीमेंटेशन

• क्रम: Root -> Left -> Right

  def pre_order(self, current_node):
    if current_node:
      print(current_node.data)
      self.pre_order(current_node.left_child)
      self.pre_order(current_node.right_child)

my_tree.pre_order(my_tree.root)

65
20
10
22
70
68
75

• जटिलता: $O(n)$
  • $n$ -> नोड्स की संख्या

पोस्ट-ऑर्डर

• क्रम: Left

पोस्ट-ऑर्डर

• क्रम: Left -> Right

पोस्ट-ऑर्डर

• क्रम: Left -> Right -> Current

• जटिलता: $O(n)$

  • $n$ -> नोड्स की संख्या

इन-ऑर्डर, प्री-ऑर्डर, और पोस्ट-ऑर्डर कब उपयोग करें

• in-order

  • BST से नोड वैल्यूज को ascending ऑर्डर में पाने के लिए

• pre-order

  • ट्री की कॉपी बनाने के लिए
  • प्रीफ़िक्स एक्सप्रेशन पाने के लिए

• post-order

  • बाइनरी ट्री डिलीट करने के लिए
  • पोस्टफ़िक्स एक्सप्रेशन पाने के लिए

डेप्थ फर्स्ट सर्च - ग्राफ

• ग्राफ में cycles हो सकते हैं
  • विज़िट किए गए वर्टिसेज़ ट्रैक करने पड़ते हैं
• चरण:
  1. किसी भी वर्टेक्स से शुरू करें
  2. current वर्टेक्स को visited सूची में जोड़ें
  3. current नोड के हर adjacent वर्टेक्स के लिए
     • अगर पहले विज़िट किया है -> इग्नोर करें
     • नहीं किया है -> रिकर्सिवली DFS चलाएँ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - ग्राफ

डेप्थ फर्स्ट सर्च - इम्प्लीमेंटेशन

def dfs(visited_vertices, graph, current_vertex):
    if current_vertex not in visited_vertices:
        print(current_vertex)
        visited_vertices.add(current_vertex)
        for adjacent_vertex in graph[current_vertex]:
            dfs(visited_vertices, graph, adjacent_vertex)

• जटिलता: $O(V+E)$
  • $V$ -> वर्टिसेज़ की संख्या
  • $E$ -> एजेज़ की संख्या

अभ्यास करते हैं!

Python में Data Structures और Algorithms