在Python中找出一条边是否属于最小生成树的程序

在Python中找出一条边是否属于最小生成树的程序

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

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

因此,如果输入类似于edges =

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

  • return not findPath(edges, a, b)

示例

让我们看下面的实现,以便更好地理解 –

class Solution:
   # 定义findPath函数
   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
   # 定义solve函数
   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)

# 实例化Solution对象
ob = Solution()
# 输出结果
print(ob.solve([
   [0, 2, 100],
   [1, 2, 200],
   [1, 3, 100],
   [2, 3, 300]
], 0, 2))

Input

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

Output

True

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程