在Python中找出图形中的关键边和虚关键边的程序
假设我们有一个包含从0到n-1编号的n个顶点的图形。该图是无向的,每条边都有一个权重。因此,给定图形后,我们必须找出图形的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
-
对于图形[u,空列表]中的每个v、w,执行以下操作:
- 如果exl和u在exl中,v也在,则
- 转到下一个迭代
- 如果not k[v] is True,则
- 将三元组(w,u,v)推入堆tmp中
- 如果exl和u在exl中,v也在,则
- 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不为空时,执行以下操作:
- 从堆tmp中弹出最小的项,w:= pop
-
从堆tmp中弹出最小的项,u:= pop
-
从堆tmp中弹出最小的项,v:= pop
-
如果k[u]和k[v]都不为零,则
- 转到下一个迭代
- res := res + w
-
如果not k[u] is True,则
- visit(u)
- 如果not k[v] is True,则
- visit(v)
- 如果k中所有值都为True,则返回res,否则返回无穷大
-
从主方法中执行以下操作:
-
graph :=给定图形
-
temp :=find_mst(num_vertices, graph)
-
c_edge :=一个新的列表
-
p_edge :=一个新的列表
-
对于i在范围0到边的大小之间,执行以下操作
- 如果find_mst(num_vertices, graph, exl = edges[i,index 2 to end]) > temp,则
- 在c_edge末尾插入i
- 否则,如果find_mst(num_vertices, graph, init = edges[i])与temp相同,则
- 在p_edge末尾插入i
- 如果find_mst(num_vertices, graph, exl = edges[i,index 2 to end]) > temp,则
- 返回[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]]