मान लीजिए हमारे पास एक दिया गया अनिर्देशित ग्राफ है; हमें जांचना है कि क्या इसमें आकार l का एक स्वतंत्र सेट है। यदि आकार l का कोई स्वतंत्र सेट है तो Yes वापस करें अन्यथा No।
हमें इस बात का ध्यान रखना है कि एक ग्राफ में स्वतंत्र सेट को उन शीर्षों के समूह के रूप में परिभाषित किया गया है जो सीधे एक-दूसरे से जुड़े नहीं हैं।
तो, यदि इनपुट L = 4 है,
तो आउटपुट yes होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
एक फ़ंक्शन is_valid() परिभाषित करें। यह ग्राफ, arr लेगा
i के लिए 0 से arr के आकार की सीमा में, करें
j के लिए i + 1 से arr के आकार की सीमा में, करें
यदि graph[arr[i], arr[j]], 1 के समान है, तो
False वापस करें
True वापस करें
एक फ़ंक्शन solve() परिभाषित करें। यह ग्राफ, arr, k, index, sol लेगा
यदि k, 0 के समान है, तो
यदि is_valid(ग्राफ, arr) True के समान है, तो
sol[0] := True
वापस करें
अन्यथा,
यदि index >= k, तो
वापस करें (solve(ग्राफ, arr[इंडेक्स 0 से अंत तक] concatenate [index] के साथ सूची, k-1, index-1, sol) या solve(ग्राफ, arr[इंडेक्स 0 से अंत तक], k, index-1, sol))
अन्यथा,
वापस करें solve(ग्राफ, arr[इंडेक्स 0 से अंत तक] concatenate [index] के साथ सूची, k-1, index-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
