在ht[1]~ht[n]的范围内选择两个parent为0且weight最小的结点,其序号赋值给s1,s2
时间: 2023-06-14 19:05:52 浏览: 48
以下是一个可能的实现方式:
```python
s1 = s2 = -1 # 初始化为无效值
min_weight1 = min_weight2 = float('inf') # 初始化为正无穷
for i in range(1, n+1):
if parent[i] == 0 and weight[i] < min_weight1:
s2 = s1
min_weight2 = min_weight1
s1 = i
min_weight1 = weight[i]
elif parent[i] == 0 and weight[i] < min_weight2:
s2 = i
min_weight2 = weight[i]
```
解释一下:
- 首先将 s1 和 s2 都初始化为 -1,表示它们是无效的。
- 然后将 min_weight1 和 min_weight2 都初始化为正无穷,表示当前还没有找到合适的结点。
- 接下来遍历所有结点,如果当前结点的 parent 为 0(即当前结点没有被选中),并且其 weight 比当前的最小值 min_weight1 还小,那么将原来的 s1 和 min_weight1 赋值给 s2 和 min_weight2,然后将当前结点的序号和 weight 赋值给 s1 和 min_weight1。
- 如果当前结点的 weight 比 min_weight1 大但比 min_weight2 小,那么将当前结点的序号和 weight 赋值给 s2 和 min_weight2。
- 最后遍历完所有结点后,s1 和 s2 就是最小的两个 weight,且它们的 parent 都为 0 的结点的序号。如果没有找到合适的结点,s1 和 s2 仍然是 -1。