একটি প্রান্ত পাইথনে ন্যূনতম স্প্যানিং ট্রির একটি অংশ কিনা তা খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে 'এজস' নামে একটি 2D ম্যাট্রিক্স আছে, যা একটি অনির্দেশিত গ্রাফ উপস্থাপন করে। ম্যাট্রিক্স 'এজ'-এর প্রতিটি আইটেম একটি প্রান্তকে প্রতিনিধিত্ব করে এবং ফর্মের (u, v, w)। এর মানে u এবং v নোড সংযুক্ত এবং প্রান্তের ওজন w আছে। আমাদের কাছে a এবং b পূর্ণসংখ্যাও রয়েছে, যা একটি প্রান্ত (a, b) প্রতিনিধিত্ব করে। প্রান্তটি (a, b) একটি ন্যূনতম বিস্তৃত গাছের অংশ কিনা তা আমাদের খুঁজে বের করতে হবে৷

দ্রষ্টব্য − গ্রাফটিকে সংযুক্ত করতে হবে এবং গ্রাফে প্রান্ত (a, b) বিদ্যমান থাকে৷

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

[[0, 2, 100],
[1, 2, 200],
[1, 3, 100],
[2, 3, 300]],
a = 0
b = 2,

তাহলে আউটপুট হবে True।

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

• একটি ফাংশন findPath() সংজ্ঞায়িত করুন। এটি প্রান্ত, a, b

  লাগবে

  • a যদি b এর মত হয়, তাহলে

    • রিটার্ন ট্রু

  • যদি প্রান্তগুলি খালি থাকে, তাহলে

    • রিটার্ন ফলস

  • প্রতিটি x প্রান্তের জন্য, করুন

    • যদি x[2] -1 এর মত হয়, তাহলে

      • পুনরাবৃত্তি চালিয়ে যান

    • new_a :=-1

    • যদি x[0] a এর মত হয়, তাহলে

      • new_a :=x[1]

    • অন্যথায় যখন x[1] a এর মত হয়, তখন

      • new_a :=x[0>

    • যদি new_a -1 এর মত না হয়, তাহলে

      • প্রান্ত থেকে x মুছুন

      • যদি findPath(edges, new_a, b) অ-শূন্য হয়, তাহলে

        • রিটার্ন ট্রু

      • প্রান্তের শেষে x ঢোকান

    • রিটার্ন ফলস

এখন মূল ফাংশন থেকে, নিম্নলিখিতগুলি করুন -

• ওজন :=ইনপুট অ্যারে 'এজ' থেকে এজ x এর প্রান্তের ওজন, যদি

  • ((x[0] a এর মতো এবং x[1] b এর মতো) অথবা(x[1] a এর মতো এবং x[0] b এর মতো))

• প্রান্ত :=[এজ x ইনপুট অ্যারে প্রান্ত থেকে যদি x[2] <ওজন]

• ফিরে না FindPath(edges, a, b)

উদাহরণ

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

class Solution:
   def findPath(self, edges, a, b):
      if a == b:
         return True
      if not edges:
         return False
      for x in edges:
         if x[2] == -1:
            continue
         new_a = -1
         if x[0] == a:
            new_a = x[1]
         elif x[1] == a:
            new_a = x[0]
         if new_a != -1:
            edges.remove(x)
            if self.findPath(edges, new_a, b):
               return True
            edges.append(x)
      return False
   def solve(self, edges, a, b):
      weight = next(x for x in edges if (x[0] == a and x[1] == b) or (x[1] == a and x[0] == b))[ 2 ]
      edges = [x for x in edges if x[2] < weight]
      return not self.findPath(edges, a, b)

ob = Solution()
print(ob.solve([
   [0, 2, 100],
   [1, 2, 200],
   [1, 3, 100],
   [2, 3, 300]
], 0, 2))

ইনপুট

[
[0, 2, 100],
[1, 2, 200],
[1, 3, 100],
[2, 3, 300]
], 0, 2

আউটপুট

True