在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
- 如果a和b相同,那么
现在从主函数中执行以下操作 –
- 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