用 Python 反转有向图的程序

假设我们有一个有向图，我们需要找到它的逆图，也就是说，如果一条边从 u 指向 v，那么现在它从 v 指向 u。这里的输入将是邻接表，如果有 n 个节点，那么节点将是 (0, 1, ..., n-1)。

所以，如果输入如下

那么输出将是

要解决这个问题，我们将按照以下步骤进行 −

  • ans := 一个包含 n 个不同列表的列表，其中 n 是顶点的数量
  • 对于图中的每个索引 i 和邻接列表 l，执行
    • 对于列表中的每个 x，执行
      • 在 ans[x] 的末尾插入 i
  • 返回 ans

让我们看看以下实现来加深理解 −

示例

 在线演示

class Solution:
   def solve(self, graph):
      ans = [[] for _ in graph]
      for i, l in enumerate(graph):
         for x in l:
            ans[x].append(i)
      return ans
ob = Solution()
graph = [[1,2],[4],[4],[1,2],[3]]
print(ob.solve(graph))

输入

[[1,2],[4],[4],[1,2],[3]]

输出

[[], [0, 3], [0, 3], [4], [1, 2]]

更新于：20-Oct-2020

1000+ 浏览

开启你的职业生涯

完成课程即可获得认证

开始学习
广告