मान लीजिए हमारे पास एक ग्राफ है जिसे एडजेसेंसी सूची के रूप में दर्शाया गया है, हमें 2D मैट्रिक्स M ढूंढना है जहां:
- M[i, j] = 1 जब वर्टेक्स i और j के बीच कोई पथ हो।
- M[i, j] = 0 अन्यथा।
उदाहरण के लिए, यदि इनपुट जैसा है:
तो आउटपुट होगा:
| 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 |
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
- 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]]