if 的理解

2024-08-31 16:56:30

1. if 实现集合的划分

比如著名的 Prim 算法（最小生成树），从某一确定的点出发，每次新加入的点，都是在已访问过的结点（u∈U）和未访问过（v∈V−U）的结点之间的边。这里的未被访问（V−U）该如何实现呢？

可以使用集合（set）及其各种操作，也可以简单地使用 if + 状态进行判断：

mst = [None]*vnum

                # mst 为 None 表示尚未被访问

count = 0

cands = PrioQueue([0, 0, 0])

while count < vnum and not cands.is_empty():

    w, u, v = cands.dequeue()

    if mst[v]:

        continue

    mst[v] = ((u, v), w)

    for vi, w in graph.out_edges(v):

        if !mst[vi]:

            cands.enqueue((w, v, vi))

最新文章

热门文章