Python程序：判断边是否属于最小生成树

假设我们有一个名为“edges”的二维矩阵，它表示一个无向图。矩阵“edges”中的每个项目都表示一条边，其形式为(u, v, w)。这意味着节点u和v相连，并且该边的权重为w。我们还有整数a和b，它们表示一条边(a,b)。我们必须找出边(a, b)是否属于最小生成树的一部分。

注意 - 图必须是连通的，并且边(a, b)存在于图中。

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

[[0, 2, 100],
[1, 2, 200],
[1, 3, 100],
[2, 3, 300]],
a = 0
b = 2,

则输出为True。

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

  • 定义函数findPath()。它将接收edges, a, b作为参数。

    • 如果a等于b，则

      • 返回True

    • 如果edges为空，则

      • 返回False

    • 对edges中的每个x进行迭代：

      • 如果x[2]等于-1，则

        • 继续迭代

      • new_a := -1

      • 如果x[0]等于a，则

        • new_a := x[1]

      • 否则，如果x[1]等于a，则

        • new_a := x[0]

      • 如果new_a不等于-1，则

        • 从edges中删除x

        • 如果findPath(edges, new_a, b)不为零，则

          • 返回True

        • 将x插入edges的末尾

      • 返回False

现在，从主函数执行以下操作：

  • weight := 从输入数组“edges”中获取边x的权重，如果

    • ((x[0]等于a且x[1]等于b)或(x[1]等于a且x[0]等于b))

  • edges := [从输入数组edges中获取边x，如果x[2] < weight]

  • 返回!findPath(edges, a, b)

示例

让我们来看下面的实现，以便更好地理解：

在线演示

class Solution:
   def findPath(self, edges, a, b):
      if a == b:
         return True
      if not edges:
         return False
      for x in edges:
         if x[2] == -1:
            continue
         new_a = -1
         if x[0] == a:
            new_a = x[1]
         elif x[1] == a:
            new_a = x[0]
         if new_a != -1:
            edges.remove(x)
            if self.findPath(edges, new_a, b):
               return True
            edges.append(x)
      return False
   def solve(self, edges, a, b):
      weight = next(x for x in edges if (x[0] == a and x[1] == b) or (x[1] == a and x[0] == b))[ 2 ]
      edges = [x for x in edges if x[2] < weight]
      return not self.findPath(edges, a, b)

ob = Solution()
print(ob.solve([
   [0, 2, 100],
   [1, 2, 200],
   [1, 3, 100],
   [2, 3, 300]
], 0, 2))

输入

[
[0, 2, 100],
[1, 2, 200],
[1, 3, 100],
[2, 3, 300]
], 0, 2

输出

True

更新于：2020-12-23

浏览量：358

开启您的职业生涯

完成课程获得认证

开始学习
广告