পাইথনে আনডিরেক্টেড গ্রাফে দিয়ে गये আকারের ইনডিপেন্ডেন্ট সেট আছে কিনা চেক করা

ধরা যাক একটি আনডিরেক্টেড গ্রাফ দেওয়া আছে। আমাদের চেক করতে হবে সেটিতে আকার l-এর একটি ইনডিপেন্ডেন্ট সেট আছে কিনা। ইনডিপেন্ডেন্ট সেট মানে এমন একটি ভার্টেক্স সেট যারা একে অপরের সাথে সরাসরি কানেক্টেড নয়।

ইনপুট: L=4, গ্রাফ চিত্রে দেওয়া আছে → আউটপুট Yes।

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

• is_valid(graph, arr): অ্যারে arr-এর সব জোড়া চেক করুন graph[arr[i]][arr[j]] != 1 হলে True
• solve(graph, arr, k, index, sol): রিকারসিভ ব্যাকট্র্যাকিং
  • যদি k==0: is_valid হলে sol[0]=True; return
  • যদি index >= k: solve(arr+[index], k-1, index-1) OR solve(arr, k, index-1)
  • অন্যথায়: solve(arr+[index], k-1, index-1)

উদাহরণ

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):
            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