Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में वर्टेक्स-टू-वर्टेक्स पहुंच योग्यता मैट्रिक्स की गणना करने का प्रोग्राम


मान लीजिए हमारे पास एक ग्राफ है जिसे एडजेसेंसी सूची के रूप में दर्शाया गया है, हमें 2D मैट्रिक्स M ढूंढना है जहां:

  • M[i, j] = 1 जब वर्टेक्स i और j के बीच कोई पथ हो।
  • M[i, j] = 0 अन्यथा।

उदाहरण के लिए, यदि इनपुट जैसा है: पायथन में वर्टेक्स-टू-वर्टेक्स पहुंच योग्यता मैट्रिक्स की गणना करने का प्रोग्राम तो आउटपुट होगा:

11111
01111
01111
01111
01111

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

  • ans := n x n आकार का 2D मैट्रिक्स, जहां n वर्टेक्स की संख्या है, 0 से भरा हुआ
  • i को 0 से n तक के लिए करें:
    • 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]]
  1. पायथन प्रोग्राम: मैट्रिक्स का ट्रांसपोज़ ढूंढें पायथन प्रोग्राम: मैट्रिक्स का ट्रांसपोज़ ढूंढें

    इस लेख में, हम दिए गए प्रॉब्लम स्टेटमेंट को हल करने के समाधान और दृष्टिकोण के बारे में सीखेंगे। प्रॉब्लम स्टेटमेंट एक मैट्रिक्स दिए जाने पर, हमें ट्रांसपोज़ को उसी मैट्रिक्स में स्टोर करना होगा और इसे प्रदर्शित करना होगा। मैट्रिक्स का ट्रांसपोज़ पंक्तियों को कॉलम में और कॉलम को पंक्तियों में बदलकर

  1. पायथन प्रोग्राम: चतुष्फलक (Tetrahedron) का क्षेत्रफल ज्ञात करें पायथन प्रोग्राम: चतुष्फलक (Tetrahedron) का क्षेत्रफल ज्ञात करें

    इस लेख में, हम दी गई समस्या के समाधान और दृष्टिकोण के बारे में जानेंगे।समस्या कथन - एक चतुष्फलक की भुजा दी गई है, हमें चतुष्फलक का क्षेत्रफल ज्ञात करना होगा।एक चतुष्फलक एक ज्यामितीय आकृति है जो त्रिकोणीय आधार वाले पिरामिड जैसा दिखता है। यह चार त्रिकोणीय फलकों वाला एक ठोस वस्तु है, तीन किनारों पर, एक

  1. - श्रृंखला n+nm+nmm...+n(m बार) की गणना के लिए पायथन प्रोग्राम

    समस्या विवरण यहां n दिया गया मान है जो धनात्मक संख्या है, m वह संख्या है जितनी बार श्रृंखला चलती है। हमारा कार्य इस श्रृंखला की गणना करना है। एल्गोरिदम n, m इनपुट करें। संख्या को स्ट्रिंग में बदलें। परिणाम को संख्या और स्ट्रिंग के रूप में आरंभ करें। शेष पद जोड़ें। स्ट्रिंग को जोड़कर n, nn, nnn...