Python में Depth-First Search (DFS)
DFS recursion या explicit stack का उपयोग करता है।
में Depth-First Search (DFS) क्या है?
DFS recursion या explicit stack का उपयोग करता है।
Backtrack करने से पहले एक path में गहराई तक जाएँ।
इसका उपयोग कब करें?
- Algorithms और data structures की कार्यप्रणाली समझें।
- हर चरण देखें और edge cases जाँचें।
- समय और memory की जटिलता की तुलना करें।
Python में Depth-First Search (DFS) Visualizer
O(V+E)हर comparison और data movement देखने के लिए चलाएँ या अगला चरण दबाएँ।
उदाहरण कोड
main.py
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
def depth_first(node, visited=None):
visited = visited or set()
visited.add(node)
order = [node]
for neighbor in graph[node]:
if neighbor not in visited:
order.extend(depth_first(neighbor, visited))
return order
print(depth_first("A"))अपेक्षित आउटपुट
['A', 'B', 'D', 'C', 'E']यह कैसे काम करता है
हर vertex और edge अधिकतम एक बार process होता है: जटिलता O(V+E) है।
मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।
अभ्यास के कार्य
बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।
- खाली input, एक element और duplicate values जाँचें।
- हर चरण के बाद state दिखाएँ।
- Performance को दूसरे solution से तुलना करें।