पायथन में वर्टेक्स-टू-वर्टेक्स रीचैब्लिटी मैट्रिक्स की गणना करने का कार्यक्रम

मान लीजिए कि हमारे पास एक आसन्न सूची प्रतिनिधित्व के रूप में एक ग्राफ है, हमें 2D मैट्रिक्स M ढूंढना होगा जहां

• M[i, j] =1 जब शीर्ष i और j के बीच पथ हो।

• एम [आई, जे] =0 अन्यथा।

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

तो आउटपुट होगा

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

• उत्तर:=आकार n x n का एक 2d मैट्रिक्स, जहां n शीर्षों की संख्या है, 0s ​​से भरें

• मेरे लिए 0 से n की सीमा में, करें

  • q:=एक कतार, और सबसे पहले i डालें

  • जबकि q खाली नहीं है, करें

    • नोड:=q का पहला तत्व, और q से पहला तत्व हटाएं

    • अगर उत्तर [i, नोड] शून्य नहीं है, तो

      • अगले पुनरावृत्ति के लिए जाएं

    • ans[i, नोड]:=1

    • पड़ोसी:=ग्राफ[नोड]

    • पड़ोसियों में प्रत्येक n के लिए, करें

      • q के अंत में n डालें

• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Solution:
   def solve(self, graph):
      ans=[[0 for _ in graph] for _ in graph]
      for i in range(len(graph)):
         q=[i]
         while q:
            node=q.pop(0)
            if ans[i][node]: continue
            ans[i][node]=1
            neighbors=graph[node]
            for n in neighbors:
               q.append(n)
      return ans
ob = Solution()
adj_list = [[1,2],[4],[4],[1,2],[3]]
priunt(ob.solve(adj_list))

इनपुट

[[1,2],[4],[4],[1,2],[3]]

आउटपुट

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