在Python中找出一条边是否属于最小生成树的程序
假设我们有一个名为“edges”的二维矩阵,它表示一个无向图。矩阵“edges”中的每个项表示一条边,形式为(u, v, w)。这意味着节点u和v相连,边的权重为w。此外,我们有整数a和b,表示一条边(a, b)。我们必须找出边(a, b)是否是最小生成树的一部分。
注意 - 图必须是连通的,边(a,b)存在于图中。
因此,如果输入类似于edges =
那么输出将为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)
示例
让我们看下面的实现,以便更好地理解 –