找出边缘是否为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。

在线示例

让我们看下面的实现以更好地理解-

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