ब्रेड्थ फ़र्स्ट सर्च (BFS)

Python में Data Structures और Algorithms

Miriam Antona

Software engineer

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

  • रूट से शुरू होता है
  • हर लेवल के हर नोड को विजिट करता है

बाइनरी सर्च ट्री पर ब्रेड्थ फ़र्स्ट सर्च का ग्राफिकल प्रतिनिधित्व.

Python में Data Structures और Algorithms

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

  def bfs(self):

    if self.root:

      visited_nodes = []

      bfs_queue = queue.SimpleQueue()

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes:
  • bfs_queue:
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)

      while not bfs_queue.empty():

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes:
  • bfs_queue: 65
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes:
  • bfs_queue:
  • current_node: 65
Python में Data Structures और Algorithms

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

  def bfs(self):

    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)

        if current_node.left:

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65
  • bfs_queue:
  • current_node: 65
Python में Data Structures और Algorithms

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

  def bfs(self):

    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65
  • bfs_queue: 20
  • current_node: 65
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65
  • bfs_queue: 20, 70
  • current_node: 65
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65
  • bfs_queue: 70
  • current_node: 20
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65, 20
  • bfs_queue: 70
  • current_node: 20
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65, 20
  • bfs_queue: 70, 10
  • current_node: 20
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65, 20
  • bfs_queue: 70, 10, 22
  • current_node: 20
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65, 20
  • bfs_queue: 10, 22
  • current_node: 70
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65, 20, 70
  • bfs_queue: 10, 22
  • current_node: 70
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65, 20, 70
  • bfs_queue: 10, 22, 68
  • current_node: 70
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65, 20, 70
  • bfs_queue: 10, 22, 68, 75
  • current_node: 70
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65, 20, 70, 10
  • bfs_queue: 22, 68, 75
  • current_node: 10
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65, 20, 70, 10
  • bfs_queue: 68, 75
  • current_node: 22
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65, 20, 70, 10, 22
  • bfs_queue: 68, 75
  • current_node: 22
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65, 20, 70, 10, 22, 68
  • bfs_queue: 75
  • current_node: 68
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65, 20, 70, 10, 22, 68
  • bfs_queue:
  • current_node: 75
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65, 20, 70, 10, 22, 68, 75
  • bfs_queue:
  • current_node: 75
Python में Data Structures और Algorithms

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

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)
    return visited_nodes
  • जटिलता: $O(n)$

बाइनरी सर्च ट्री का ग्राफिकल प्रतिनिधित्व.

  • visited_nodes: 65, 20, 70, 10, 22, 68, 75
  • bfs_queue:
  • current_node: 75
Python में Data Structures और Algorithms

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

  • ग्राफ़ में साइकल हो सकते हैं
    • जाँच करनी होगी कि वर्टेक्स पहले से विजिट हुए हैं या नहीं
Python में Data Structures और Algorithms

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

def bfs(graph, initial_vertex):

  visited_vertices = []

  bfs_queue = queue.SimpleQueue()

  bfs_queue.put(initial_vertex)

  visited_vertices.append(initial_vertex)

  while not bfs_queue.empty():

    current_vertex = bfs_queue.get()

    for adjacent_vertex in graph[current_vertex]:

      if adjacent_vertex not in visited_vertices:

        visited_vertices.append(adjacent_vertex)

        bfs_queue.put(adjacent_vertex)

  return visited_vertices
  • जटिलता: $O(V+E)$
    • $V$ -> वर्टेक्स की संख्या
    • $E$ -> एज की संख्या
Python में Data Structures और Algorithms

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

ग्राफ़ पर ब्रेड्थ फ़र्स्ट सर्च का ग्राफिकल प्रतिनिधित्व.

Python में Data Structures और Algorithms

BFS बनाम DFS

BFS

  • लक्ष्य स्टार्टिंग वर्टेक्स के पास हो
  • उपयोग:
    • वेब क्रॉलिंग
    • अनवेटेड ग्राफ़ में सबसे छोटा रास्ता ढूँढना
    • GPS से कनेक्टेड लोकेशंस खोजना
    • जटिल एल्गोरिदम के हिस्से के रूप में उपयोग

DFS

  • लक्ष्य स्टार्टिंग वर्टेक्स से दूर हो
  • उपयोग:
    • एकमात्र हल वाली पहेलियाँ सुलझाना (जैसे, भूलभुलैया)
    • ग्राफ़ में साइकल डिटेक्ट करना
    • वेटेड ग्राफ़ में सबसे छोटा रास्ता ढूँढना
    • जटिल एल्गोरिदम के हिस्से के रूप में उपयोग
Python में Data Structures और Algorithms

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

Python में Data Structures और Algorithms

Preparing Video For Download...