मान लीजिए हमारे पास एक ग्राफ है, हमारे पास एक स्रोत शीर्ष और एक संख्या k भी है। k स्रोत से गंतव्य तक ग्राफ का पथ लंबाई है, हमें जांचना है कि क्या हम स्रोत से शुरू होने वाला और किसी अन्य शीर्ष (गंतव्य के रूप में) पर समाप्त होने वाला एक सरल पथ (बिना चक्र के) ढूंढ सकते हैं। ग्राफ निम्नलिखित में दिखाया गया है -
तो, यदि इनपुट स्रोत = 0, k = 64 की तरह है, तो आउटपुट True होगा क्योंकि एक सरल पथ 0 से 7 से 1 से 2 से 8 से 6 से 5 से 3 से 4 मौजूद है, इस पथ की कुल दूरी 68 है जो 64 से अधिक है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
आसन्न मैट्रिक्स adj का उपयोग करके ग्राफ को परिभाषित करें जिसका क्रम नोड्स x नोड्स हो और एज लागत से भरें
एक फ़ंक्शन solve() परिभाषित करें। यह स्रोत, k, पथ लेगा
यदि k <= 0, तो
True वापस करें
i := 0
जब तक i, adj[स्रोत] के आकार के समान नहीं है, करें
v := adj[स्रोत, i, 0]
w := adj[स्रोत, i, 1]
i := i + 1
यदि पथ[v] True है, तो
अगले पुनरावृत्ति के लिए जाएं
यदि w >= k, तो
True वापस करें
पथ[v] := True
यदि solve(v, k-w, पथ) true है, तो
True वापस करें
पथ[v] := False
False वापस करें
मुख्य विधि से, निम्नलिखित करें -
पथ := नोड्स के समान आकार की एक सूची, फिर गलत मानों से भरें
पथ[स्रोत] := 1
solve(स्रोत, k, पथ) वापस करें
उदाहरण
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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
