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

假设我们有一个图作为邻接列表表示，我们必须找到 2D 矩阵 M，其中

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

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

因此，如果输入如下

那么输出将是

为了解决这个问题，我们将遵循这些步骤 −

• ans:= 一个大小为 n x n 的二维矩阵，其中 n 是顶点数，用 0 填充

• 对于范围在 0 到 n 内的 i，执行

  • q:= 一个队列，并将 i 插入到队列的开头

  • 当 q 不为空时，执行

    • node:= q 的第一个元素，并从 q 中删除第一个元素

    • 如果 ans[i, node] 非零，则

      • 进行下一次迭代

    • ans[i, node]:= 1

    • 邻居:= graph[node]

    • 对于邻居中的每个 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]
  ]
  

  ---

  相关文章

  • 用 Python 编写程序，求出排序列表中每对数字的绝对差之和
  • 用 Python 编写程序，查找使列表元素相等的最小总成本
  • 用 Python 编写的程序，通过使用左子树和右子树本身的值来更新值，从而找到一棵树
  • 用 Python 中的字符串字符计算我们可以生成的唯一回文数的程序
  • 用 Python 计算顶点到顶点可达性矩阵的程序
  • 用 Python 编写程序来计算投掷 n 个骰子的方法数
  • 使用 C++ 对矩阵的每个对角线元素按升序排序的程序
  • 用 Python 编写的程序，用于查找赢得删除重复整数游戏所需的移动次数
  • 用 Python 编写一个程序，通过从第一个或最后一个字符中删除并再次插入来制作目标
  • 用 Python 编写的程序，用于从二叉树中删除所有具有偶数值的叶子

  ---

  打印 下一节 ❯❮ 上一节