在 Python 中找出图中的关键边和伪关键边的程序
假设给定一个图，其中包含 n 个顶点，编号为 0 到 n -1。该图是无向的，每条边都有一个权重。因此，给定图，我们必须找出图中 MST 中的关键边和伪关键边。如果删除该边导致 MST 权重增加，则该边称为临界边。伪临界边是可以出现在所有图 MST 中的边，但不是全部。给定图形作为输入，我们找出边的索引。
所以，如果输入像
顶点数为 5，则输出为 [[], [0, 1, 2, 3, 4]] 给定图中没有临界边，所有边都是伪临界的。由于所有边的权重相同，因此图中的任何 3 条边都将构成 MST。
示例
让我们看看以下实现以更好地理解
from heapq import heappop, heappushdef 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 中找出图中的关键边和伪关键边的程序 的全部内容， 来源链接： utcz.com/z/363231.html
