একটি অনির্দেশিত গ্রাফে পাইথনে একটি প্রদত্ত আকারের একটি স্বাধীন সেট রয়েছে কিনা তা খুঁজুন

ধরুন আমাদের একটি প্রদত্ত অনির্দেশিত গ্রাফ আছে; আমাদের পরীক্ষা করতে হবে এটিতে l আকারের একটি স্বাধীন সেট রয়েছে কিনা। যদি l আকারের কোনো স্বাধীন সেট থাকে তাহলে হ্যাঁ ফিরুন অন্যথায় না।

আমাদের মনে রাখতে হবে যে একটি গ্রাফে একটি স্বাধীন সেটকে শীর্ষবিন্দুগুলির একটি সেট হিসাবে সংজ্ঞায়িত করা হয় যা একে অপরের সাথে সরাসরি সংযুক্ত নয়৷

সুতরাং, যদি ইনপুটটি L =4,

তাহলে আউটপুট হবে হ্যাঁ

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

• একটি ফাংশন is_valid() সংজ্ঞায়িত করুন। এটি গ্রাফ গ্রহণ করবে, আরার

• আমি 0 থেকে arr এর আকারের মধ্যে, কর

  • j রেঞ্জের জন্য i + 1 থেকে arr এর আকার, করুন

    • যদি গ্রাফ[arr[i], arr[j]] 1 এর মত হয়, তাহলে

      • রিটার্ন ফলস

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

• একটি ফাংশন সংজ্ঞায়িত করুন solve()। এটি গ্রাফ, arr, k, index, sol

  নেবে

• k যদি 0 এর সমান হয়, তাহলে

  • যদি is_valid(গ্রাফ, arr) True এর মত হয়, তাহলে

    • sol[0] :=সত্য

    • ফেরত

  • অন্যথায়,

    • যদি সূচক>=k, তাহলে

      • প্রত্যাবর্তন(সমাধান (গ্রাফ, আরআর[সূচী 0 থেকে শেষ পর্যন্ত] [সূচি], কে-1, সূচক-1, সল) সহ একটি তালিকা সংযুক্ত করুন বা সমাধান করুন(গ্রাফ, আরআর[সূচি 0 থেকে শেষ পর্যন্ত], কে, সূচক 1, sol))

    • অন্যথায়,

      • প্রত্যাবর্তন সমাধান

উদাহরণ

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

def is_valid(graph, arr):
   for i in range(len(arr)):
      for j in range(i + 1, len(arr)):
         if graph[arr[i]][arr[j]] == 1:
            return False
   return True
def solve(graph, arr, k, index, sol):
   if k == 0:
      if is_valid(graph, arr) == True:
         sol[0] = True
         return
      else:
         if index >= k:
            return (solve(graph, arr[:] + [index], k-1, index-1, sol) or solve(graph, arr[:], k, index-1, sol))
         else:
            return solve(graph, arr[:] + [index], k-1, index-1, sol)

graph = [
   [1, 1, 0, 0, 0],
   [1, 1, 1, 1, 1],
   [0, 1, 1, 0, 0],
   [0, 1, 0, 1, 0],
   [0, 1, 0, 0, 1]]
k = 4
arr = []
sol = [False]
solve(graph, arr[:], k, len(graph)-1, sol)
if sol[0]:
   print("Yes")
else:
   print("No")

ইনপুট

[[1, 1, 0, 0, 0],
[1, 1, 1, 1, 1],
[0, 1, 1, 0, 0],
[0, 1, 0, 1, 0],
[0, 1, 0, 0, 1]],
4

আউটপুট

Yes