假设给定一个图,其中包含 n 个顶点,编号为 0 到 n -1。该图是无向的,每条边都有一个权重。因此,给定图,我们必须找出图中 MST 中的关键边和伪关键边。如果删除该边导致 MST 权重增加,则该边称为临界边。伪临界边是可以出现在所有图 MST 中的边,但不是全部。给定图形作为输入,我们找出边的索引。
所以,如果输入像
顶点数为 5,则输出为 [[], [0, 1, 2, 3, 4]] 给定图中没有临界边,所有边都是伪临界的。由于所有边的权重相同,因此图中的任何 3 条边都将构成 MST。
让我们看看以下实现以更好地理解
from heapq import heappop, heappush def solve(num_vertices, edges): graph = dict() for u, v, w in edges: graph.setdefault(u, []).append((v, w)) graph.setdefault(v, []).append((u, w)) temp = find_mst(num_vertices, graph) c_edge, p_edge = [], [] for i in range(len(edges)): if find_mst(num_vertices, graph, exl = edges[i][:2]) > temp: c_edge.append(i) elif find_mst(num_vertices, graph, init = edges[i]) == temp: p_edge.append(i) return [c_edge, p_edge] def find_mst(num_vertices, graph, init = None, exl = None): def visit(u): k[u] = True for v, w in graph.get(u, []): if exl and u in exl and v in exl: continue if not k[v]: heappush(tmp, (w, u, v)) res = 0 k = [False] * num_vertices tmp = [] if init: u, v, w = init res += w k[u] = k[v] = True visit(u) or visit(v) else: visit(0) while tmp: w, u, v = heappop(tmp) if k[u] and k[v]: continue res += w if not k[u]: visit(u) if not k[v]: visit(v) return res if all(k) else inf print(solve(5, [[0,1,10],[1,2,10],[2,3,10],[3,4,10],[4,0,10]]))
5, [[0,1,10],[1,2,10],[2,3,10],[3,4,10],[4,0,10]]输出结果
[[], [0, 1, 2, 3, 4]]