পাইথনে ক্ষুদ্রতম চক্রের দৈর্ঘ্য ধরে রাখার লক্ষ্য খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে একটি নির্দেশিত গ্রাফের সংলগ্ন তালিকা রয়েছে, যেখানে সূচী i-এ প্রতিটি তালিকা নোড i থেকে সংযুক্ত নোডগুলিকে উপস্থাপন করা হয়েছে। আমরা একটি লক্ষ্য মান আছে. আমাদের লক্ষ্য ধারণ করে একটি সংক্ষিপ্ত চক্রের দৈর্ঘ্য খুঁজে বের করতে হবে। যদি কোন সমাধান না হয় -1 রিটার্ন।

সুতরাং, যদি ইনপুট মত হয়

টার্গেট =3., তাহলে আউটপুট 3 হবে, যেহেতু চক্রটি নোড 1 -> 2 -> 3 -> 1। উল্লেখ্য আরেকটি চক্র আছে 0 -> 1 -> 2 -> 3 -> 0, তবে এটি হল সংক্ষিপ্ত নয়।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

পরিদর্শন করেছেন :=একটি নতুন সেট
l :=এলিমেন্ট টার্গেট সহ একটি তালিকা।
দৈর্ঘ্য :=0
যখন l অ-খালি, কর
- দৈর্ঘ্য :=দৈর্ঘ্য + 1
- nl :=একটি নতুন তালিকা
- l-এ প্রতিটি u-এর জন্য, কর
  - গ্রাফে প্রতিটি v-এর জন্য[u], করুন
    - যদি v টার্গেটের সমান হয়, তাহলে
      - রিটার্ন দৈর্ঘ্য
    - যদি v পরিদর্শন করা হয়, তাহলে
      - পরবর্তী পুনরাবৃত্তির জন্য যান
    - ভিকে ভিজিট করা হিসেবে চিহ্নিত করুন
    - nl-এর শেষে v ঢোকান
- l :=nl
রিটার্ন -1

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি -

উদাহরণ

class Solution:
   def solve(self, graph, target):
      visited = set()
      l = [target]
      length = 0

      while l:
         length += 1
         nl = []
         for u in l:
            for v in graph[u]:
               if v == target:
                  return length
               if v in visited:
                  continue
               visited.add(v)
               nl.append(v)
         l = nl

      return -1

ob = Solution()
graph = [[1, 4],[2],[3],[0, 1],[]]
target = 3
print(ob.solve(graph, target))

ইনপুট

[[1, 4],[2],[3],[0, 1],[]]