পাইথনে ভের্টেক্স-টু-ভের্টেক্স রিচেবিলিটি ম্যাট্রিক্স ক্যালকুলেট করার প্রোগ্রাম

মনে করুন একটি গ্রাফ এডজেসেন্সি লিস্ট রিপ্রেজেন্টেশন হিসেবে দেওয়া আছে, আমাদের একটি ২ডি ম্যাট্রিক্স M খুঁজে বের করতে হবে যেখানে:

• M[i, j] = 1 যখন ভের্টেক্স i এবং j-এর মধ্যে পথ থাকে।
• M[i, j] = 0 অন্যথায়।

ইনপুট গ্রাফ এবং আউটপুট ম্যাট্রিক্সের ছবি দেওয়া আছে।

সমাধানের ধাপসমূহ

• ans := n x n আকারের ২ডি ম্যাট্রিক্স, যেখানে n হল ভের্টেক্স সংখ্যা, 0 দিয়ে পূরিত
• i = 0 থেকে n-1 পর্যন্ত,
  • q := একটি কিউ, প্রথমে i যোগ করুন
  • যখন q খালি নয়,
    • node := q-এর প্রথম উপাদান, এবং q থেকে মুছে দিন
    • যদি ans[i][node] নন-জিরো হয়, তবে
      • পরবর্তী ইটারেশনে যান
    • ans[i][node] := 1
    • neighbors := graph[node]
    • প্রতিটি n neighbors-এ,
      • q-এর শেষে n যোগ করুন
• ans ফেরত দিন

উদাহরণ

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]]
print(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]]