Python程序：计算顶点到顶点的可达性矩阵

假设我们有一个图，用邻接表表示，我们需要找到一个二维矩阵M，其中

  • 当顶点i和j之间存在路径时，M[i, j] = 1。

  • 否则，M[i, j] = 0。

因此，如果输入如下所示：

则输出将为：

11111
01111
01111
01111
01111

为了解决这个问题，我们将遵循以下步骤：

  • 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

开启你的职业生涯

通过完成课程获得认证

开始学习
广告