用 Python 编写程序，找出图中的关键边和伪关键边
假设，我们给定一个包含 n 个顶点的图，编号从 0 到 n -1。该图是无向的，每条边都有一个权重。因此，给定该图，我们必须找出图 MST 中的关键边和伪关键边。如果删除该边导致 MST 权重增加，则该边称为关键边。伪关键边是可以出现在所有图 MST 中的边，但不是全部。我们根据给定的图作为输入找出边的索引。
因此，如果输入如下
并且顶点数为 5，则输出将为 [[], [0, 1, 2, 3, 4]] 给定的图中没有关键边，所有边都是伪关键的。由于所有边都具有相同的权重，因此图中的任意 3 条边都将构成 MST。
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数 find_mst() 。这将需要 num_vertices、graph、init := null、exl := null
定义一个辅助函数 visit() 。这将需要 u
k[u] := True
对于 graph[u，一个空列表] 中的每个 v、w，执行
如果 exl 并且 u 在 exl 中并且 v 在 exl 中，则
进行下一次迭代
如果 k[v] 不为 True，则
将三元组 (w,u,v) 推送到堆 tmp 中
res := 0
k := 一个大小为 num_arrays 的新列表，其中包含值 False
tmp := 一个新的堆
如果 init 非空，则
u := init
v := init
w := init
res := res + w
k[u] := True
k[v] := True
visit(u) 或 visit(v)
否则，
visit(0)
当 tmp 不为空时，执行
w := 从堆 tmp 中弹出最小项
u := 从堆 tmp 中弹出最小项
v := 从堆 tmp 中弹出最小项
如果 k[u] 且 k[v] 非零，则
进行下一次迭代
res := res + w
如果 k[u] 不为 True，则
visit(u)
如果 k[v] 不为 True，则
visit(v)
如果所有 k 都为 True，则返回 res，否则返回无穷大
从主方法中，执行以下操作:
graph := 给定图
temp := find_mst(num_vertices, graph)
c_edge := 一个新列表
p_edge := 一个新列表
对于范围从 0 到边大小的 i，执行
如果 find_mst(num_vertices, graph, exl = edge[i, index 2 to end]) > temp，则
在 c_edge 末尾插入 i
否则，如果 find_mst(num_vertices, graph, init = edge[i]) 与 temp 相同，则
在 p_edge 末尾插入 i
返回 [c_edge, p_edge]
示例
让我们看看下面的实现以便更好地理解
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]]
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
