पायथन में कम से कम चक्र लंबाई होल्डिंग लक्ष्य खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक निर्देशित ग्राफ की आसन्नता सूची है, जहां सूचकांक i पर प्रत्येक सूची नोड i से जुड़े नोड्स का प्रतिनिधित्व करती है। हमारे पास एक लक्ष्य मूल्य भी है। हमें लक्ष्य वाले सबसे छोटे चक्र की लंबाई ज्ञात करनी है। अगर कोई समाधान नहीं है तो वापसी -1.

तो, अगर इनपुट पसंद है

लक्ष्य =3, तो आउटपुट 3 होगा, क्योंकि चक्र नोड्स 1 -> 2 -> 3 -> 1 है। ध्यान दें कि एक और चक्र 0 -> 1 -> 2 -> 3 -> 0 है, लेकिन यह है सबसे छोटा नहीं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

विज़िट किया :=एक नया सेट
l :=तत्व लक्ष्य वाली एक सूची।
लंबाई:=0
जबकि l खाली नहीं है, करें
- लंबाई:=लंबाई + 1
- nl:=एक नई सूची
- एल में प्रत्येक के लिए, करते हैं
  - ग्राफ में प्रत्येक वी के लिए[यू], करते हैं
    - यदि 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],[]]