Pythonで頂点から頂点への到達可能性マトリックスを計算するプログラム

隣接リスト表現としてグラフがあるとすると、2D行列Mを見つける必要があります。ここで

• 頂点iとjの間にパスがある場合、M [i、j]=1です。

• それ以外の場合はM[i、j]=0です。

したがって、入力が次のような場合

その場合、出力は次のようになります

これを解決するには、次の手順に従います-

• ans：=サイズn x nの2次元行列。ここで、nは頂点の数であり、0で埋めます

• 0からnの範囲のiの場合、実行

  • q：=キュー、最初にiを挿入

  • qが空でない間、実行します

    • node：=qの最初の要素、およびqから最初の要素を削除する

    • ans [i、node]がゼロ以外の場合、

      • 次のイテレーションに行く

    • ans [i、node]：=1

    • 隣人：=グラフ[ノード]

    • ネイバーのnごとに、実行します

      • 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]]
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]
]