資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：計算頂點到頂點的可達性矩陣
假設我們有一個圖，用鄰接表表示，我們需要找到一個二維矩陣M，其中
當頂點i和j之間存在路徑時，M[i, j] = 1。
否則，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的二維矩陣，其中n是頂點的數量，用0填充。
對於範圍從0到n的i，執行：
q:= 一個佇列，首先插入i。
當q不為空時，執行：
node:= q的第一個元素，並從q中刪除第一個元素。
如果ans[i, node]非零，則
進行下一次迭代。
ans[i, node]:= 1
neighbors:= graph[node]
對於neighbors中的每個n，執行：
將n插入到q的末尾。
返回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]] 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] ]
更新於：2020年10月7日
瀏覽量：273
廣告