পাইথনে গ্রাফে সোর্স থেকে k-এর চেয়ে বড় পথ আছে কিনা চেক করা

ধরা যাক একটি গ্রাফ, একটি সোর্স ভার্টেক্স এবং একটি সংখ্যা k দেওয়া আছে। k হলো পথের দৈর্ঘ্য। আমাদের চেক করতে হবে সোর্স থেকে শুরু করে কোনো সিম্পল পথ (সাইকেল ছাড়া) আছে কিনা যার দৈর্ঘ্য k-র চেয়ে বড়। গ্রাফ চিত্রে দেওয়া আছে।

ইনপুট: Source=0, k=64 → আউটপুট True (পথ: 0→7→1→2→8→6→5→3→4, দৈর্ঘ্য 68)।

সমাধানের ধাপসমূহ (DFS + ব্যাকট্র্যাকিং)

• Graph ক্লাস: অ্যাডজেসেন্সি লিস্ট, insert_edge মেথড
• solve(source, k, path) ফাংশন:
  • যদি k <= 0: return True
  • প্রতিটি সন্নিহিত নোড v, ওজন w জন্য:
    • যদি path[v] true: continue
    • যদি w >= k: return True
    • path[v]=True; যদি solve(v, k-w, path): return True; path[v]=False
• is_there_any_path(source, k): path অ্যারে তৈরি করে solve কল করুন।

উদাহরণ

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]: 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, edges as above, source=0, k=64

আউটপুট

True