पता करें कि क्या पायथन में किसी स्रोत से k लंबाई से अधिक का पथ है

मान लीजिए कि हमारे पास एक ग्राफ है, हमारे पास एक स्रोत शीर्ष और एक संख्या k भी है। k स्रोत से गंतव्य के बीच ग्राफ की पथ लंबाई है, हमें यह जांचना होगा कि क्या हम स्रोत से शुरू होने और किसी अन्य शीर्ष (गंतव्य के रूप में) पर समाप्त होने वाला एक सरल पथ (चक्र के बिना) ढूंढ सकते हैं। ग्राफ निम्नलिखित में दिखाया गया है -

इसलिए, यदि इनपुट स्रोत =0, k =64 जैसा है, तो आउटपुट सही होगा क्योंकि 0 से 7 से 1 से 2 से 8 से 6 से 5 से 3 से 4 तक एक सरल पथ मौजूद है, इस पथ की लंबाई कुल है 68 की दूरी जो 64 से अधिक है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• ऑर्डर नोड्स x नोड्स के आसन्न मैट्रिक्स adj का उपयोग करके ग्राफ़ को परिभाषित करें और किनारे की लागत से भरें

• फ़ंक्शन को हल करें () परिभाषित करें। यह स्रोत, k, पथ लेगा

• अगर कश्मीर <=0, तो

  • सही लौटें

• मैं :=0

• जबकि मैं adj [स्रोत] के आकार के समान नहीं हूं, करें

  • v:=adj[स्रोत, i, 0]

  • w:=adj[स्रोत, i, 1]

  • मैं :=मैं + 1

  • यदि पथ [v] सत्य है, तो

    • अगले पुनरावृत्ति के लिए जाएं

  • अगर w>=k, तो

    • सही लौटें

  • पथ[v] :=सच

  • यदि हल (v, k-w, पथ) सत्य है, तो

    • सही लौटें

  • पथ[v] :=असत्य

• झूठी वापसी

• मुख्य विधि से, निम्न कार्य करें -

• पथ:=नोड्स के समान आकार की एक सूची, फिर झूठे मानों से भरें

• पथ [स्रोत] :=1

• वापसी हल (स्रोत, के, पथ)

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

class Graph:
   def __init__(self, nodes):
      self.nodes = nodes
      self.adj = [[] for i in range(nodes)]
   def insert_edge(self,u, v, w):
      self.adj[u].append([v, w])
      self.adj[v].append([u, w])
   def solve(self,source, k, path):
      if (k <= 0):
         return True
      i = 0
      while i != len(self.adj[source]):
         v = self.adj[source][i][0]
         w = self.adj[source][i][1]
         i += 1
         if (path[v] == True):
            continue
         if (w >= k):
            return True
         path[v] = True
         if (self.solve(v, k-w, path)):
            return True
         path[v] = False
      return False
   def is_there_any_path(self,source, k):
      path = [False]*self.nodes
      path[source] = 1
      return self.solve(source, k, path)

nodes = 9
g = Graph(nodes)
g.insert_edge(0, 1, 5)
g.insert_edge(0, 7, 9)
g.insert_edge(1, 2, 9)
g.insert_edge(1, 7, 12)
g.insert_edge(2, 3, 8)
g.insert_edge(2, 8, 3)
g.insert_edge(2, 5, 5)
g.insert_edge(3, 4, 10)
g.insert_edge(3, 5, 15)
g.insert_edge(4, 5, 11)
g.insert_edge(5, 6, 3)
g.insert_edge(6, 7, 2)
g.insert_edge(6, 8, 7)
g.insert_edge(7, 8, 8)
source = 0
k = 64
print(g.is_there_any_path(source, k))

इनपुट

nodes = 9
g = Graph(nodes)
g.insert_edge(0, 1, 5)
g.insert_edge(0, 7, 9)
g.insert_edge(1, 2, 9)
g.insert_edge(1, 7, 12)
g.insert_edge(2, 3, 8)
g.insert_edge(2, 8, 3)
g.insert_edge(2, 5, 5)
g.insert_edge(3, 4, 10)
g.insert_edge(3, 5, 15)
g.insert_edge(4, 5, 11)
g.insert_edge(5, 6, 3)
g.insert_edge(6, 7, 2)
g.insert_edge(6, 8, 7)
g.insert_edge(7, 8, 8)
source = 0
k = 64

आउटपुट

True